Hey all, attached is a C file that finds prime numbers. Any comments, suggestions, ideas or critisisms would be welcome.

Printable View

- 12-14-2008dan724Finding Prime Numbers
Hey all, attached is a C file that finds prime numbers. Any comments, suggestions, ideas or critisisms would be welcome.

- 12-14-2008Brafil
It looks good. Since Ive done something before, I suggest you to do this:

Have a (prime) array of 1 element (which is 2, the smallest prime number)

Then, for each number smaller than the limit, if it can't be divided by any of the primes in the array, push it onto the array. That's it. - 12-14-2008Salem
How much is your code?

http://www.panix.com/~gesslein/matho...primes/lsqrt.c

> todivide += 1;

Thinking backwards, if it is divisible by 4, was it divisible by 2?

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

todivide should be the next known prime, not the next number. - 12-14-2008dan724
The lsqrt function is shamelessly lifted from there. The rest is mine. The standard library sqrt() were all quite slow and didnt work with unsigned long longs.

"Thinking backwards, if it is divisible by 4, was it divisible by 2?"

I'm not quite sure I see what you are getting at. If it was divisible by 2, we wouldnt ever be testing it because I skip all even numbers.

"todivide should be the next known prime, not the next number. "

Again, I'm not sure I follow. todivide is the number I am currently dividing the variable prime by to see if it is, in fact, a prime number.

"Have a (prime) array of 1 element (which is 2, the smallest prime number)

Then, for each number smaller than the limit, if it can't be divided by any of the primes in the array, push it onto the array. That's it."

I see what you are getting at, but that doesnt let you start at an arbitrary value like mine does. - 12-14-2008laserlightQuote:

Originally Posted by**dan724**

Quote:

Originally Posted by**dan724**

Quote:

Originally Posted by**dan724**

- 12-14-2008tabstop
To make the point a little clearer, it's not enough to just increment prime by 2 each time.

The sieve method works for your desired case as well; you just have to do a little extra work at the beginning (finding primes less than your target start point) for the payoff at the end (making finding those large primes easier). - 12-14-2008dan724Quote:

In that case you should "conspicuously and appropriately publish ... an appropriate copyright notice and disclaimer of warranty" etc, or you may be considered as guilty of copyright infringement.

Quote:

You are not skipping all the even numbers at the moment since you only increment todivide by 1. If you increment it by 2, then you would indeed skip all the even numbers greater than 2.

- 12-14-2008laserlightQuote:

Originally Posted by**tabstop**

Quote:

Originally Posted by**dan724**

- 12-14-2008dan724
I see now, and you are right. However given the nature of the license, the nature of what I'm using this for, and the nature in which I copied a small portion of the work, I'm still not concerned. I seriously doubt that the GNU project is going to sue me for copyright infringment for this sort of thing. Again, I am not worried about such a problem.

Quote:

Actually, I think that the primes must be found based on the target end point, but because that appears to be optional, this could be a little tricky. It also becomes problematic if the numbers are near to the end of the possible range since the sieve would require a huge amount of space. I guess a trade-off must be made somewhere such that after a certain point the program will resort to trial division with some odd composites instead of primes only.

- 12-14-2008tabstop
Well, division isn't that far behind. Based on a silly little test I just did of 1000000 malloc + frees and 1000000 divisions, it appears that 1 malloc+free = 17 divisions. (Consistent 0.086s for malloc+free, 0.005s for division.) So if you can do one malloc and save yourself at least 18 divisions, you did good. (And of course you could malloc space for more than one int at a time....)

Edit: And I forgot that you were using long long (thanks Salem!). Changing the divisions to long long meant they took 0.026s, so now you only need to save four divisions to come out ahead. - 12-14-2008laserlightQuote:

Originally Posted by**dan724**

Quote:

Originally Posted by**dan724**

- 12-14-2008Salem
> It doesnt seem to me that this sort of trade off would work out favorably most of the time.

Well if you were only going from 1000000000 to 1000000010 say, then I might agree with that.

But my guess is that you're after a lot more than that.

But unless you're working on a 64-bit processor, then modulo division of two 'long long' is going to involve a fair amount of code.

If you're using gcc, then try using the "-S" option, and study the generated prog.s file.

> Last I knew malloc()/free() were not the fastest things in the world.

Considering how I could only see you calling them once, I don't see this as a reason.

The square root of a 64-bit number is always a 32-bit number

You only need a single bit to store the 'isPrime' result, and small amount of simple bit-twiddling code.

Storing all possible test primes in this bit-array would need 1/2GB of memory. A lot for sure, but not infeasible to store the whole thing in a file for repeated use.

Even just maintaining a cache of small primes (say <1E6) would be a big win. After trivially rejecting all the even numbers, you're going to reject a lot more by dividing by 3, 5, 7 etc than by say finding that 999983 (largest prime <1E6).