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?
- Login or Signup Now to post comments
Adams,
Please post the definition of the function isprime(). I shall see if i can minimize it.
___/|_____/|____/|____
I am good in being me!
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;
}
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%. In my PC it takes 1 sec to generate all till 1000000.
___/|_____/|____/|____
I am good in being me!
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().
Actually you have a much better option in the (not lost) history of Greece! The legendary Sieve of Eratosthenes.
http://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.
___/|_____/|____/|____
I am good in being me!
You must be kidding!!
I am absolutely stunned! Thanks Angel. You rock!
You are welcome.
___/|_____/|____/|____
I am good in being me!