Thread: Finding primes

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    4

    Finding primes

    So i have been working on finding prime numbers using c++ programs for a while now. Here is my question does anyone know of an effeicent way of finding them. I have been using the % function and just dividing by every possible number up to the current number but as most of you know when you hit 1 billion you are talking a few days before it has finished. I am a math major but not really that far into it all the efficeint ways I know of work great on paper but when you try to program them infinity gets in the way and the program tells you bad things and dies.

    Thanks in advance,
    starripper

  2. #2
    Registered User
    Join Date
    Aug 2002
    Location
    Hermosa Beach, CA
    Posts
    446
    This looks useful:

    http://www.cs.cmu.edu/~scandal/cacm/node8.html

    BTW, all I did was google "primes algorithm".
    The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.

  3. #3
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    Well, this is my favorite way borrowed from R. Sedgewick:
    Code:
    #include <iostream>
    
    using namespace std;
    
    int main ( ) 
    {
    	int N = 20;
    	bool* a = new bool[N];
    	int i;
    	for ( i = 2; i < N; i++ ) 
    	{
    		a[i] = true; 
    	}
    	for ( i = 2; i < N; i++ ) 
    	{
    		if ( a[i] != false ) 
    		{
    			for ( int j = i; j*i < N; j++ ) 
    			{
    				a[i * j] = false; 
    			}
    		}
    	}
    	
    	for ( i = 2; i < N; i++ ) 
    	{
    		if ( a[i] )
    		{
    			cout<< i <<" ";
    		}
    	}
            delete [] a;
    	return 0;
    }
    This prints prime numbers less than N;

    Hope this helps

    - Micko
    Last edited by Micko; 01-12-2006 at 01:18 PM.
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  4. #4
    Registered User
    Join Date
    Jan 2006
    Posts
    14
    here you go, I just wrote very efficient method to find primes for ya
    Code:
    bool IsPrime(int n) {
      
    if (n<=2)
    return true;
    
    if(n%2 == 0)
    return false;
    
     for(i = 3; i <= sqrt((double) n); i+=2){
      if(n % i == 0){
       return false;
      }
    }
    return true;
    }
    u can check a number if it is prime by calling function with a argument that could by any number within int range!
    you can even check a range of numbers, by using a simple loop as for ex.
    Code:
    for(int i = 0; i<10000; i++){
      if(IsPrime(i)) cout << "Prime:"<<i<<endl;
    }
    I apologize for any syntax error, I'm java programer but the logic is very important therefore this is very fast algorithm to find primes.
    Last edited by fiska; 01-12-2006 at 03:33 PM.

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Look up "sieve of erastothenes" for a reasonably efficient approach.

    Incidentally, fiska, comparing i against sqrt((double) n) every time through the loop is not particularly efficient, and would introduce rounding errors for large n, that may result in false positives or false negatives against the loop condition.

  6. #6
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49

    Wink

    I have an exact function as fiska for calculating primes, except I used a double variable to contain the root instead of multiple calls, I wrote it when I was learning C++. It works. Rounding does not matter because if i is greater than the root of the number then it's fairly obvious that the number is not a prime since root*root equals to the number. So the prime can be found without going through every possibility.

    On the other hand, one problem I had with this function is that it goes through all the odd numbers even through 9%3 == 0, 15%3 == 0, 65%5 == 0 etc. etc. I haven't got a solution to this problem though.

    I have also used the sieve of erastothenes, this function stores all the found prime numbers in an array, and it checks whether the number is evenly divisible by all the elements of the array, it if isn't then it is a prime since all non-prime numbers are divisible by the prime.

    Both methods are not efficient enough for me, so I'm still going around trying to find a better way.

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by Frost Drake
    I have an exact function as fiska for calculating primes, except I used a double variable to contain the root instead of multiple calls, I wrote it when I was learning C++. It works. Rounding does not matter because if i is greater than the root of the number then it's fairly obvious that the number is not a prime since root*root equals to the number.
    It is only obvious if you assume that computing the sqrt of a floating point number is exact, and also assume that all values of an int (or whatever integral type you work with) can be stored exactly in a floating point variable. You can get lucky on some machines, but there is no universal guarantee.
    Quote Originally Posted by Frost Drake
    So the prime can be found without going through every possibility.
    That is the intent of most attempts to speed up finding of primes.
    Quote Originally Posted by Frost Drake
    On the other hand, one problem I had with this function is that it goes through all the odd numbers even through 9%3 == 0, 15%3 == 0, 65%5 == 0 etc. etc. I haven't got a solution to this problem though.
    We know that the first few primes are 2, 3, and 5. 2*3*5 = 30. Now the values between 30*n and 30*(n+1) that are guaranteed to be composite will be 30*n + {2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26, 27,29}. (the bold curly braces intended to be conventional set theory notation). Which means that the only values between 30*n and 30*(n+1) that we need to test 30*n+ any in set of {1,7,11,13,17,19,23,29} as they might be prime. Which means we only need to check 8 values between 30*n and 30*(n+1) to see if they are prime. Note that the set includes 1 and all primes (other than 2,3, and 5) that are < 30.

    That approach can be generalised using values that are the product of all primes up to a given value. For example, we might use an interval based on 2*3*5*7 = 210 and find that less than 1/5 of all values between 210*n and 210*(n+1) only needed to be tested to see if they are prime.

    Quote Originally Posted by Frost Drake
    I have also used the sieve of erastothenes, this function stores all the found prime numbers in an array, and it checks whether the number is evenly divisible by all the elements of the array, it if isn't then it is a prime since all non-prime numbers are divisible by the prime.

    Both methods are not efficient enough for me, so I'm still going around trying to find a better way.
    To test if a value is prime, it is necessary to determine if it is divisible by ALL primes that, when multiplied by themselves, do not exceed the value. The sieve of erastothenes does that, and you can't get around it (unless you are willing to accept some values being reported as prime when they aren't). But you can do some tricks about systematically picking what values you test, such as the one I described above. Again, the trick is to ensure coverage: ensure you don't eliminate values from consideration that might actually be prime.

    But, no matter what happens, finding of very large primes (let's say values with more than a few hundred digits) will always involve a lot of work.
    Last edited by grumpy; 01-13-2006 at 05:41 PM.

  8. #8
    Registered User
    Join Date
    Jan 2006
    Posts
    14
    Quote Originally Posted by grumpy
    Look up "sieve of erastothenes" for a reasonably efficient approach.

    Incidentally, fiska, comparing i against sqrt((double) n) every time through the loop is not particularly efficient, and would introduce rounding errors for large n, that may result in false positives or false negatives against the loop condition.
    my metyhond would work fine with int data types and is efficeint, you see it first check wether the number is divisible by 2 n%2 if so it does not let you go further so the time factor is reduced here a lot, therefore the loop starts from no. 3 and adds up as odd number ingnoring all even numbers so here we gain even more time, so far I haven't see other algorthims that does find primes faster.

    As I said I'm java programer so I dont know C++ very well (well Im learning it and being honest I love it) so I'm using sqrt with double numeral thats the only reason.
    In java I would have done it a bit different, I would find sqrt of the given input (only after it has passed the two conditions that I have in the beginning)
    check this out how would look like in JAva:
    Code:
    bool IsPrime(int n) {
      
    if (n<=2)
    return true;
    
    if(n%2 == 0)
    return false;
    
    int t =(int) Math.sqrt(n);
     for(int i = 3; i <= t; i+=2){
      if(n % i == 0){
       return false;
      }
    }
    return true;
    }
    it is a slightly different.

    as it concenrs negative numbers you don't input negative numbers (where did u see negative primes?), but we could eleminate that qiut easily with only one condition. if(n < 0) return false; but this is not a big deal.

    When it comes to a big number really big one, we in java use BigInteger and there are built in mechanisim that would find for u a prime quit easily.

    But if u know any better method I would be very happy to learn it from you, I'm CS student basically all I do is learn :-)

    Fiska
    Last edited by fiska; 01-13-2006 at 07:15 AM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    my metyhond would work fine with int data types and is efficeint, you see it first check wether the number is divisible by 2 n%2 if so it does not let you go further so the time factor is reduced here a lot, therefore the loop starts from no. 3 and adds up as odd number ingnoring all even numbers so here we gain even more time, so far I haven't see other algorthims that does find primes faster.
    The sieve of Eratosthenes should find primes faster than your method, but then it can only be used to find the first n primes, rather than test if a given integer is prime. Using such a method to obtain a seed array of primes, and then using that seed array for brute force primality testing will also be faster (in the long run) than your method, since your method also tests for divisibility with composite numbers, when one only needs to test with prime numbers.

    In java I would have done it a bit different, I would find sqrt of the given input (only after it has passed the two conditions that I have in the beginning)
    I think grumpy's point is that you should have stored the result of sqrt() in a variable (as per your Java example) instead of repeating it for each iteration, though I suspect a good optimising compiler might be able to do that for you.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318

    iMalc

    Gees are you guys clueless or what? He doesn't want the sieve of Eratosthenes, or the worse version without using extra memory. Those are awful.

    Here's a few links to some of the more advanced methods of quickly determining if a number is composite:

    http://en.wikipedia.org/wiki/Fermat_primality_test
    http://en.wikipedia.org/wiki/Solovay...primality_test
    http://en.wikipedia.org/wiki/Miller-...primality_test

    libmp++ conveniently already implements the Miller-Rabin test (IIRC) in it's big number library for primality testing, so I'd use that:
    http://libmp.sourceforge.net/

  11. #11
    Slave MadCow257's Avatar
    Join Date
    Jan 2005
    Posts
    735
    Gees are you guys clueless or what? He doesn't want the sieve of Eratosthenes, or the worse version without using extra memory. Those are awful.
    Whoa whoa, that's a bit strong to come on. First of all, your algorithms are probabilistic, not deterministic which you should have mentioned. In many applications, that could be a problem. Second, the way people have interpreted the op's question is that he wants more of a search functionality, not a test for individual numbers. They could be wrong, but then again the original poster has not even responded.

    though I suspect a good optimising compiler might be able to do that for you.
    We tested this a while back, all compilers that have any respect do.

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by laserlight
    I think grumpy's point is that you should have stored the result of sqrt() in a variable (as per your Java example) instead of repeating it for each iteration, though I suspect a good optimising compiler might be able to do that for you.
    That was not my point. The point is that the C or C++ standards do not make many guarantees that values that can be stored in integers can also be stored in a floating point type. Add the issue of numerical precision into the mix, and it is quite possible to get a result of 13425.99999 when the result (if calculated exactly) would have been 13426.

    The post I responded to claimed that using sqrt() would guarantee correct behaviour (finding every prime). That claim was incorrect. It might be guaranteed in Java (because Java uses specific representations of int, float, double, etc) and it might work with some compilers and target platforms with C++ (because of the representations of integer and floating point types used by specific compilers and hardware) but is not guaranteed to work in general.

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Here's a few links to some of the more advanced methods of quickly determining if a number is composite
    What you fail to mention, as MadCow257 has pointed out, is that these algorithms determine if a given number is composite or probably prime, not if they are composite or prime. That said, I havent been doing much reading up on this topic lately, and it appears that there's a certain AKS primality test that is deterministic and yet runs in polynomial time.

    We tested this a while back, all compilers that have any respect do.
    Oh, okay.

    The point is that the C or C++ standards do not make many guarantees that values that can be stored in integers can also be stored in a floating point type.
    hmm... many or any?
    Clearly the C++ Standard provides for floating point to integer (and vice versa) conversions, though I suppose you mean that there will be problems (e.g. undefined behaviour) if the integral value is larger than what the floating point type can hold in the conversion attempted.

    Add the issue of numerical precision into the mix, and it is quite possible to get a result of 13425.99999 when the result (if calculated exactly) would have been 13426.
    I agree, but then this can be avoided by an addition of 1 since the result is used for the upper boundary of a range, so it need not be exact, merely large enough.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Jun 2005
    Posts
    6,815
    Quote Originally Posted by laserlight
    hmm... many or any?
    Some guarantees are implied, as integral types are required to support certain ranges, and floating point types are required to support others. Unfortunately, the extent of overlap and interaction between the types is not specified.
    Quote Originally Posted by laserlight
    Clearly the C++ Standard provides for floating point to integer (and vice versa) conversions, though I suppose you mean that there will be problems (e.g. undefined behaviour) if the integral value is larger than what the floating point type can hold in the conversion attempted.
    As a matter of fact, it falls in the range of implementation defined behaviour, not undefined behaviour. In some cases (particularly with conversion of negative values) it falls in the domain of unspecified behaviour. It does not typically involve undefined behaviour. That may be splitting hairs, but those terms (unspecified, implementation defined, undefined) have specific meanings in the standards.

    Quote Originally Posted by laserlight
    I agree, but then this can be avoided by an addition of 1 since the result is used for the upper boundary of a range, so it need not be exact, merely large enough.
    As a matter of fact it can't. For a floating point variable x there is not necessarily a guarantee that x+1 will test non-equal to x, particularly when larger values are stored in x. There is no guarantee that the maximum value that can be stored in an int does not exceed the threshold where such effect occur.

    That aside, what we're debating is related to the common (and incorrect) assumption that floating point types can represent any real value when, in reality, floating point variables can only represent a finite (albeit large) set of real values, and any values that are between two values that can be represented will be stored as one the two nearest values to it. And, unfortunately, problems associated with this tend to come in when mixing operations involving integral and floating point types --- particularly when the values involved get large. And, when you're talking about testing moderate to large primes .......
    Last edited by grumpy; 01-14-2006 at 01:19 AM.

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Some guarantees are implied, as integral types are required to support certain ranges, and floating point types are required to support others. Unfortunately, the extent of overlap and interaction between the types is not specified.
    Ah, okay, I see what you mean. I had the impression that you were only referring to the short <= int <= long and float <= double <= long double specifications.

    As a matter of fact, it falls in the range of implementation defined behaviour, not undefined behaviour. In some cases (particularly with conversion of negative values) it falls in the domain of unspecified behaviour. It does not typically involve undefined behaviour.
    I checked the C++ Standard, and yes, I agree that my example isnt accurate for the wording used. On the other hand, such conversions may involve undefined behaviour. From the C++ Standard, section 4.9:
    "An rvalue of a floating point type can be converted to an rvalue of an integer type. The conversion truncates; that is, the fractional part is discarded. The behavior is undefined if the truncated value cannot be represented in the destination type."

    As a matter of fact it can't. For a floating point variable x there is not necessarily a guarantee that x+1 will test non-equal to x, particularly when larger values are stored in x. There is no guarantee that the maximum value that can be stored in an int does not exceed the threshold where such effect occur.
    Since one has to check if the range of integral values required can fit into the floating point variable in question on a given platform, I dont see why one cannot do a similiar check to ensure that a point where x+1 doesnt test non-equal to x is never reached.

    And, when you're talking about testing moderate to large primes .......
    heh, I suspect that if the OP comes back he/she will end up using a bignum library of some kind, so the whole issue would be avoided by a custom implementation of a square root function for the bignum.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. tools for finding memory leaks
    By stanlvw in forum C++ Programming
    Replies: 4
    Last Post: 04-03-2009, 11:41 AM
  2. Finding primes
    By scwizzo in forum C++ Programming
    Replies: 11
    Last Post: 09-10-2008, 06:15 PM
  3. MFC :: Finding Child Window of a CWnd* Object?
    By SyntaxBubble in forum Windows Programming
    Replies: 2
    Last Post: 09-06-2003, 09:06 AM
  4. a program that writes the primes
    By Geo-Fry in forum C++ Programming
    Replies: 8
    Last Post: 03-29-2003, 06:37 PM
  5. Finding primes...
    By ER in forum C++ Programming
    Replies: 2
    Last Post: 12-08-2001, 04:15 PM