Asked By 140 points N/A Posted on -

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?

SHARE
Answered By 0 points N/A #95324

Please post the definition of the function isprime(). I shall see if I can minimize it.

Answered By 140 points N/A #95325

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;
}

Answered By 0 points N/A #95328

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.

Answered By 140 points N/A #95329

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

Answered By 0 points N/A #95330

Actually you have a much better option in the (not lost) history of Greece! The legendary 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.

Answered By 140 points N/A #95331