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

This looks useful:

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

BTW, all I did was google "primes algorithm".

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

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.

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.

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.

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.

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

Quote:

---

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.

Quote:

---

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.

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/

Quote:

---

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.

Quote:

---

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.

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.

Quote:

---

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.

Quote:

---

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

---

Oh, okay.

Quote:

---

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.

Quote:

---

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

Quote:

---

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.

Quote:

---

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

Quote:

---

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.

Quote:

---

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 laserlight

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.

---

Something along this line?

Code:

---

#include <stdio.h>
#include <float.h>

int main(void)
{
  double a = DBL_MAX, b = DBL_MAX - 1;
  printf("a = %g, b = %g\n", a, b);
  return 0;
}

/* my output
a = 1.79769e+308, b = 1.79769e+308
*/

---

Quote:

---

Originally Posted by laserlight

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.


Oh, okay.


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.


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.

---

I know I should have been a bit more polite, but post after post about using the slow way he is already using isn't going to help him either.

I think I was careful enough not to overstate the usefulness or functionality of those algorithms. It will determine if a number is definately composite, but will not determine if it is definately prime. This is still very useful because it is very fast.

I suggest downloading the libmp++ as it uses the Rabin-Miller test, but also actually fully determines if the number is prime, not just likely, iirc. It does other tests to make sure, and uses data types that can represent very large integers. Like 1024 bit integers etc. Floating point need not come into it here.

Quote:

---

Originally Posted by Dave_Sinkula

Something along this line?

Code:

---

#include <stdio.h>
#include <float.h>

int main(void)
{
  double a = DBL_MAX, b = DBL_MAX - 1;
  printf("a = %g, b = %g\n", a, b);
  return 0;
}

/* my output
a = 1.79769e+308, b = 1.79769e+308
*/

---

---

Given that a double has only 52+1 bits for it's mantissa, subtracting one from such a large number will have no effect. Inserting "assert(a == b);" before the return would not cause an assertion failure. Heck, you could even change it to subtract 1000000, with still no effect.

Floating point is not suitable for this application.

Quote:

---

Originally Posted by laserlight

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.

---

Which comes back to my original point: using floating point (and the standard sqrt() function) is not suitable for this application. We will get away with using floating point only if we are playing with smallish primes. As soon as we start playing with "largish" primes, floating point is not the way to go. And the problem is, the definition of "largish" can be within the range of what can be represented in an integral type.

There's a hole in the bucket, Dear Liza.....

Quote:

---

Originally Posted by iMalc

I know I should have been a bit more polite, but post after post about using the slow way he is already using isn't going to help him either.

---

I disagree with your claim that the posts could not help. The original post was about searching for primes, and the posts before yours addressed that (side debate about use of floating point aside).

Quote:

---

Originally Posted by iMalc

I think I was careful enough not to overstate the usefulness or functionality of those algorithms. It will determine if a number is definately composite, but will not determine if it is definately prime. This is still very useful because it is very fast.

---

Again, that depends on your application. Getting a fast probabilistic answer (of the form "may be prime") is not useful for all applications. You are assuming such an answer is always suitable. The OP gave no indication to suggest that such tests might be suitable.

Quote:

---

Originally Posted by iMalc

I suggest downloading the libmp++ as it uses the Rabin-Miller test, but also actually fully determines if the number is prime, not just likely, iirc. It does other tests to make sure, and uses data types that can represent very large integers. Like 1024 bit integers etc. Floating point need not come into it here.

---

Not sure offhand about libmp++, but the Rabin-Miller test is probabilistic. In fact it gives false positives: it will indicate that some composite numbers are prime.

When you actually start doing multiple probabilistic tests "to be sure" that a value is prime, you are essentially looking to eliminate numbers that one test determines is prime if another test determines it is composite. The result of that is still probabilistic, and there is still a non-zero probability of an incorrect result. While applying multiple tests can reduce the probability of a false result to near zero, such an approach can't actually offer a guarantee. And, when working with large values, application of multiple tests is not necessarily faster than more exhaustive approaches