Hey all, attached is a C file that finds prime numbers. Any comments, suggestions, ideas or critisisms would be welcome.
Hey all, attached is a C file that finds prime numbers. Any comments, suggestions, ideas or critisisms would be welcome.
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.
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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.
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.Originally Posted by dan724
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.
I believe that you are mistaken. This is merely an extension of the idea of skipping all the even numbers: now, you skip all the composites, which is even better.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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).
lol, I appreciate the concern. However the above link has absolutely no copyright assocated with it either, and is posted in hundreds of places across the internet, in source form, with no copyright or license. IANAL but I'm pretty sure that falls under public domain. I did manage to find a reference to it being under LGPL, so either way I'm not exactly worried.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.
Ahh! I get you, that can cut my time in half again. Thank you. The line is now "todivide += 2;"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.
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.
That the code has no explicit claim of copyright does not mean that it is in the public domain. If you just went up two directory levels you would see that: "All software and documentation in this archive is copyrighted and made available under the GNU Lesser General Public License (LGPL) version 2.1 (see file "COPYING")." Just because you have seen illegally copied code does not mean you should continue to propagate it that way.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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.
It doesnt seem to me that this sort of trade off would work out favorably most of the time. Seems like a large memory consumption for slightly less computation and when you factor in the time used managing that memory it would become a wash. Last I knew malloc()/free() were not the fastest things in the world.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.
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.
Last edited by tabstop; 12-14-2008 at 12:16 PM.
As far as I can tell, Mathomatic is not a GNU project, but that's besides the point - as a fellow software developer, you should act in good faith and avoid copyright infringement.
You can use a fixed size array and switch to less than optimal trial division when the array of primes is exhausted, though with intelligent dynamic memory allocation this range could be increased. Actually, if you are given the start and end points, you could use a modified version of the sieve of Eratosthenes as demonstrated in our recent prime number generator contest, assuming that the range is not too large.
Look up a C++ Reference and learn How To Ask Questions The Smart Way
> 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).
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
