C++ prime number handling. Please help…

Asked By 140 points N/A Posted on -
qa-featured

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
Best Answer by AngelOfTech
Answered By 0 points N/A #95324

C++ prime number handling. Please help…

qa-featured

Adams,

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

Answered By 140 points N/A #95325

C++ prime number handling. Please help…

qa-featured

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

Best Answer
Best Answer
Answered By 0 points N/A #95328

C++ prime number handling. Please help…

qa-featured

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

C++ prime number handling. Please help…

qa-featured

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

C++ prime number handling. Please help…

qa-featured

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.

Answered By 140 points N/A #95331

C++ prime number handling. Please help…

qa-featured

You must be kidding! I am absolutely stunned! Thanks Angel. You rock!

Answered By 0 points N/A #95332

C++ prime number handling. Please help…

qa-featured

You are welcome.

Login/Register to Answer

Related Questions