C++ prime number handling. Please help…

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?

• Status: Open
• Question Views: 1360
• Answer Count: 7
• Vote Up 14 Vote Down

• Answer Accepted: Yes
• Question Category: C++

Best Answer by AngelOfTech

Go To Solution

Answered By AngelOfTech 5 points N/A #95324

C++ prime number handling. Please help…

Adams,

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

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By John Adams 140 points N/A #95325

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

About John Adams

Questions
2

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Best Answer

Best Answer

Answered By AngelOfTech 5 points N/A #95328

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.

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By John Adams 140 points N/A #95329

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

About John Adams

Questions
2

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By AngelOfTech 5 points N/A #95330

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.

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By John Adams 140 points N/A #95331

C++ prime number handling. Please help…

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

About John Adams

Questions
2

Answers
3

Best Answers
0

• Vote Up 0 Vote Down

• Posted on - 05/15/2011
• Question Category: C++

Answered By AngelOfTech 5 points N/A #95332

C++ prime number handling. Please help…

You are welcome.

About AngelOfTech

Questions
0

Answers
25

Best Answers
4

• Vote Up 0 Vote Down

• Posted on - 05/16/2011
• Question Category: C++