Project Euler #7 10001st prime in C++

Question

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

How can I optimize this code?

#include <iostream>
bool is_prime(int num)
{
 for (int i = 2; i <= num/2; ++i)
 {
 if (num % i == 0)
 {
 return false;
 }
 }
 return true;
}
int main()
{
 int count = 2;
 for (int i = 5; ; i = i+2)
 {
 if (is_prime(i))
 {
 count++;
 }
 if (count == 10001)
 {
 std::cout << i;
 return 0;
 }
 }
}

• Justin: Try this - codereview.stackexchange.com/questions/136328/…
• Loki Astari: This is all about using a better algorithm. en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 1

Use better algorithms: Sieve_of_Eratosthenes

You used a brute force algorithm. But even this can be highly improved.

You increment by 2 each loop.

 for (int i = 5; ; i = i+2) {

So you have noticed that all even numbers are not prime. You can improve on this. By incrementing by 2 then 4 then 2 then 4. This removes all multiples of 2 and 3 automatically.

 int inc = 2;
 for (int i = 5; ; i += inc, inc = 6 - inc) {

The brute force check runs up to num/2

 for (int i = 2; i <= num/2; ++i)

Actually you can do better than that you only need to run up to the sqrt(num) anything larger than this will not divide into num exactly.

 int limit = sqrt(num);
 for (int i = 2; i <= limit; ++i)

Actually we can take this a step further. There is no need to divide by every number lower than num. Any number that is divisible by a prime is already checked by a prime smaller than it.

For example there is no need to check 4. You already checked 2 and all numbers divisible by 4 are also divisible by 2, so need to do that check. In fact you can skip all numbers that are not prime.

bool is_prime(int num)
{
 int limit = sqrt(num);
 for (auto const& prime: primes) {
 {
 if (prime > limit) {
 return true;
 }
 if (num % prime == 0) {
 return false;
 }
 }
 return true;
}

• Thomas Weller: How large shall the SoE array be to find the 10001st prime?
• Loki Astari: @ThomasWeller : codereview.stackexchange.com/q/221678/507
• TrebledJ: I usually do for (int i = 2; i*i <= n; ++i) instead of for (int i = 2; i <= sqrt(n); ++i). Not sure if the former offers any performance benefits... but I heard that multiplication is pretty fast out there.
• Konrad Rudolph: You pulled a fast one there in your last step: Your code doesn’t define primes, and defining it efficiently isn’t trivial. Well. Yes, it is. But then you end up with the sieve of Eratosthenes.
• Loki Astari: @KonradRudolph. Not really. The is_prime() using the list of primes is perfectly good for brute force finding of primes. You just start from 2 and work up. So the above function fits squarely with the OP brute force attack he just needs to edit his code to record each new prime as it is discovered.

Answer 2

You really need a better algorithm. Look into Sieve of Eratosthenes for a good first prime sieve to implement. That avoids (expensive) division, using instead only addition and simple multiplications (I'm including % as "division" here).

In is_prime, you really only need to try dividing by the previously discovered primes, rather than by all numbers. If you don't want to store the discovered primes, you can still reduce to testing against only odd numbers, since you only ever call it with odd num argument. Also, there's no need to test all the way up to num / 2 - if you've not found a factor before std::sqrt(num), you won't find any.

In main(), I recommend ending the output with a newline:

 std::cout << i << '\n';

• Thomas Weller: How large shall the SoE array be to find the 10001st prime?
• Lemon Drop: @ThomasWeller Well considering that is the problem trying to be solved (the array size should be the the value of the 10001st prime) the only practical approach is to make it dynamic, though you could always just guess a sufficiently large number.
• peterh: @ThomasWeller The probability that a number "n" is a prime, is around log(n). The integral of the logarithm is n*log(n)-n . Thus, we have around n*log(n)-n primes until n.
• Thomas Weller: @LemonDrop: I really dislike guessing in a tag:performance review. I'm interested in the dynamic array approach. How do you cross out the multiples after increasing the size of the array?
• Lemon Drop: @ThomasWeller The dynamic approach for the sieve though I'd imagine would be to expand the array, copy the old contents to the first part and then mark off in the new portion until you get back to the value where it stopped to expand. Though as peterh mentioned, there is actually a good approximation for how big the array needs to be, and as this answer says, there is actually a safe upper bound of M * (log M + log log M) which can be used. Additionally there are segmented sieving algorithms which do it with much less memory in a dynamic way.