Finding Prime Numbers

This is a discussion on Finding Prime Numbers within the C Programming forums, part of the General Programming Boards category; Hey all, attached is a C file that finds prime numbers. Any comments, suggestions, ideas or critisisms would be welcome....

  1. #1
    Registered User
    Join Date
    Dec 2008
    Posts
    4

    Finding Prime Numbers

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

  2. #2
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    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.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,447
    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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    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.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,420
    Quote Originally Posted by dan724
    The lsqrt function is shamelessly lifted from there.
    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 Originally Posted by dan724
    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.
    ...
    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.
    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.

    Quote Originally Posted by dan724
    I see what you are getting at, but that doesnt let you start at an arbitrary value like mine does.
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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).

  7. #7
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    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.
    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.

    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.
    Ahh! I get you, that can cut my time in half again. Thank you. The line is now "todivide += 2;"

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,420
    Quote Originally Posted by tabstop
    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).
    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.

    Quote Originally Posted by dan724
    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.
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Dec 2008
    Posts
    4
    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.

    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.
    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.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by dan724 View Post

    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.
    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 11:16 AM.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,420
    Quote Originally Posted by dan724
    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.
    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.

    Quote Originally Posted by dan724
    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.
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,447
    > 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.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime numbers
    By Imbellis in forum C Programming
    Replies: 25
    Last Post: 11-27-2008, 05:37 AM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Prime Numbers and Array...
    By Deux in forum C Programming
    Replies: 12
    Last Post: 12-20-2004, 03:12 PM
  4. prime numbers code compile error
    By Tony654321 in forum C Programming
    Replies: 5
    Last Post: 10-10-2004, 10:13 AM
  5. prime numbers
    By Unregistered in forum C Programming
    Replies: 17
    Last Post: 08-20-2002, 08:57 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21