Asked By
John Adams
140 points
N/A
Posted on - 05/15/2011
Hi,
I am doing some analytical program in C++ involving a lot of prime numbers. I don't think checking a number every time, whether it is prime or not would be a good idea.
So I just thought that if I could pre generate all the prime numbers in a list.
But it is taking too much. Time.
vector<int>Â prmn;
For (int i=2; I<100000; ++i)
If (isprime (I)) {
prmn.push_back(i);
}
Almost 4-5 second. I hate to find it upto 1000,000.
Is there any better way?
C++ prime number handling. Please help…
Adams,
Please post the definition of the function isprime(). I shall see if I can minimize it.
C++ prime number handling. Please help…
Thanks for the reply. Here is the isprime() function:
bool isprime(int a)
{
    For (int j=2; j<a; ++j)
   {
        If (a%j==0) return false;
   }
    Return true;
}
C++ prime number handling. Please help…
You don't have to check the loop till a. You can do it till root(a) as there won't be any divisor of number 'a' if there aren't any divisor smaller than 'a'.
The largest divisor of 'a' would be simply root(a). So you can shorten the isprime() by using:
bool isprime(int a)
{
    For (int j=2; j*j<=a; ++j)
   {
        If (a%j==0) return false;
   }
    Return true;
}
It would reduce the runtime by a 99%. On my PC it takes 1 Sec to generate all till 1000000.
C++ prime number handling. Please help…
Thanks very much. Yes, that was really a good observation. It will help me very much. Now it seems that I don't need to pre – generate the primes for faster program. As it is almost identical time required to find a number in a vector or just call isprime().
C++ prime number handling. Please help…
Actually you have a much better option in the (not lost) history of Greece! The legendary Sieve of Eratosthenes.
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
And if you want more improvements here are some more –
bool isprime (int a)
{
   If (a==2) return true;
   Else if (a%2==0) return false;
   Else
    For (int j=3; j*j<=a; j+=2) //reduces half the calc
   {
        If (a%j==0) return false;
   }
   Return true;
}
Observation: You can skip all the even numbers except 2 they are not prime. So don't loop for them.
C++ prime number handling. Please help…
You must be kidding! I am absolutely stunned! Thanks Angel. You rock!
