ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

This is one of my first C projects. It is a prime number generator that can run indefinitely, and outputs to a log.
I've gotten it to a stable state, i.e. I haven't been able to crash it and it works beautifully.

What I'd like is for a more seasoned programmer to look over this and perhaps give some tips on improving it, such as more efficient coding practices, perhaps a better algorithm, or maybe more efficient libraries, such as for parsing command line arguments.

Note that in order to compile it you need to have the GMP library installed, and compile it with the gcc flag -lgmp.

I don't know if this will help you, but this is a function I use to check if a number is prime. Its very efficent, and quite diffrent from what your doing. Its a code snippet I have, but I can't remember now eactly where I got it from ( but it is from a PD source I'm sure. )

Code:

bool isPrime(long value)
{
long j, r, rold, rnew;
r = 0;
rnew = 1;
do
{
rold = r;
r = rnew;
rnew = ( r + ( value / r ) );
rnew >>= 1;
}
while( rold != rnew );
for (j = 2; ( j <= rnew ); ++j)
{
if ( value % j == 0 )
return false;
}
return true;
}

Its been a while since I used C, so I wouldn't feel able to comment on the rest really.

Anyway, thanks. I tried out just checking through all numbers less than the sqrt, and it now goes considerably faster than just checking through my primes list. I suppose my earlier method was a holdover from when I wrote this in perl and used arrays. So now, instead of

Code:

prime = fopen("/asdf/primelog","r");
while(gmp_fscanf(prime,"%Zd",&test) != EOF && mpz_cmp(test,root) <= 0 &&
flag == 0){
mpz_mod(mod,thisnum,test);
if (mpz_cmp_si(mod,0) == 0)
flag = 1;
}
fclose(prime);

I have

Code:

mpz_set_ui(test,3);
while(mpz_cmp(test,root) <= 0 && flag ==0){
mpz_mod(mod,thisnum,test);
if(mpz_cmp_si(mod,0)==0)
flag = 1;
mpz_add_ui(test,test,2);
}

I think I'd like to be able to use arrays, or at least toggle between using arrays and brute forcing, but I'd also like to use a minimal amount of memory, as there's no way this could hope to compete with the existing logs, and is really just a curiosity.

From what I've read, that seems to get me various sequences, none of which will contain all primes. And it is not my goal to find a ton of primes really quickly. My goal is pretty much to have primes scroll across the left side of my desktop in order.

Yes, but you're still testing each number to see if it's prime.

It's far more efficient than a brute force algorithm, and works for most numbers save the odd strange one (look up Carmichael numbers to see what I mean).

Generating all of the primes between 1 and 1,000,000,000 would be much much faster using FLT. Your algorithm is an exponential time one - the FLT algorithm is somewhere between polynomial time and exponential time.

How high do you mean to search for primes? You can store numbers up to about 18 quintillion in an unsigned long long, making GMP unnecessary for numbers lower than that.

If you're low on ram and swap space, you could mmap the array into a file or try to play games with throwing out or writing to disk parts of the array you're not using.

Aluser, I'm not trying to find all of the primes in a certain range, I'm continuously expanding my list. So even if I had the RAM of Jesus, I couldn't very well use the sieve of Erasthones. Also, I realize that at this point (around 4B), the GMP library's not necessary. However, I don't want to have to rewrite my program once I add a few more decimal places on. I'd rather work on the fun bits than redoing the base program.

I think I've decided on not using arrays at all, simply because *eventually* I will be using up a fuck-ton of memory.

Rustynailz, thanks for that link. If I get around to it, I'll try to implement a more elegant primality test than I've got, but other things have come up, and this isn't a priority. But eventually (read: within the next semester) I'll play with that, and I'll update you on how it went.

By the way, today my log exceeded maximum file size, so I'm going to end up making lists of 100M primes in primelog.n . So this should be pretty neat.

My ultimate goal for this project is to be able to have a base log somewhere and be able to dole out processing cycles to people who have this program. So as long as I'm still in school, I should have a hall's worth of free processing devoted to making numbers fly along the left of my desktop.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.