Project Euler Problem 10. Sum of all primes < 2mil

Question

I'm new to coding so I can't create complex code yet. I do as much as I can with fors and ifs, since while I know a bit about arrays and other topics, I am not familiar enough with them to apply them on my own. This code works, but if I tell it to go to 2 million in main the program never finishes; 200,000 took about a minute, while 20,000 took a few seconds.

I get that this code is unoptimized and does too many unnecessary checks and calculations. Is there a way to optimize the program with just loops and conditions?

#include<iostream>
int nopf(int k){
    int sn=0,b;
    for(b=2;b<k;b++){
        if(k%b==0)sn++;
    }
    return sn;
}

main(){
    int i,s=0;
    for(i=2;i<200000;i++){
        if(nopf(i)==0)s+=i;
    }

    cout<<s;

}

NB: nopf is a function to check if a number is prime or not.

Answer 1

Check if prime

int nopf(int k){
    int sn=0,b;
    for(b=2;b<k;b++){
        if(k%b==0)sn++;
    }
    return sn;
}

Consider instead calling this is_prime or isPrime, depending on the convention that you're following. I prefer snake_case, but camelCase is quite popular.

bool is_prime(int n) {

I also find n a more standard name than k. Also consider writing it out as something like candidate.

Returning a boolean value is simpler in this case, as we don't need to count all the prime divisors. We only need to know if there's at least one less than the number itself.

    if (n % 2 == 0 && n != 2) {
        return false;
    }

If you pull this out, then you never have to check an even number again. Note that we need to check that it's not equal to 2, as 2 is prime.

    for (int i = 3; i < n; i += 2) {
         if (n % i == 0) {
             return false;
         }
    }

    return true;
}

I prefer i to b for a loop variable unless b has special significance to the problem, which it doesn't here.

This only does half as many checks. You can further reduce this by getting rid of all numbers divisible by 3:

bool is_prime(int candidate) {
    if (2 == candidate || 3 == candidate) {
        return true;
    }

    if (candidate % 2 == 0 || candidate % 3 == 0) {
        return false;
    }

    // since we update increment before using it the first time
    // set it to 4 here to get 2 the first time it is used to update i
    int increment = 4;
    for (int i = 5; i * i <= candidate; i += increment) {
         if (candidate % i == 0) {
             return false;
         }

         increment = 6 - increment;
    }

    return true;
}

This works by observation that in every six numbers, three are even, two are divisible by three, and one is both. And these always appear in the same order. So starting with 5, we want to check

5, 7, 11, 13, 17, 19, 23, 25, ...

So we increment by 2 to get from 5 to 7 and then by 4 to get from 7 to 11. Then by 2 to get from 11 to 13 and by 4 to get from 13 to 17. Then we note that

$$ 6 - 4 = 2 $$

and

$$ 6 - 2 = 4 $$

As a final optimization in this function, we note that at least one prime factor must always be less than the square root of the number. So we only have to try up to the square root. It's faster to calculate i * i < candidate than i < sqrt(candidate). You could pull the square root calculation out of the loop, but for many numbers it won't matter.

main

    int i,s=0;
    for(i=2;i<200000;i++){
        if(nopf(i)==0)s+=i;
    }

I'd prefer sum to s. It saves me having to realize that s is an accumulated sum. So I'd start

unsigned long sum = 5;

I'm not sure an int is always large enough to hold the necessary sum.

Setting it to 5 instead of 0 is an optimization. It allows us to start the loop

// only works for values of N >= 3
const int N = 2000000;

// since we update increment before using it the first time
// set it to 4 here to get 2 the first time it is used to update i
int increment = 4;
for (int i = 5; i < N; i += increment) {

We don't have to check if 2 and 3 are prime, as they always are. So we just include them in the sum.

In C++, the convention for a for loop is to declare the looping variable in the loop itself. The exception would be if you use the looping variable outside the loop, but you don't do that here.

It's also generally preferred not to do multiple declarations if you are doing any assignments. It's too easy to overlook a declaration if another declaration plus assignment is taking up most of the line.

I prefer declaring a constant rather than just editing the loop itself to change the value. But obviously it will work either way.

     if (is_prime(i)) {
         sum += i;
     }

I find this variant easier to read than your original. I don't have to know what a return of 0 from nopf means. Nor do I need to remember that s is my summing variable. This reads naturally in English.

     increment = 6 - increment;
}

And we have to update increment as before--with the same logic.

This tests far fewer numbers to see if they're prime. Roughly a third.

With this version of main, you can create a version of is_prime that does not include the checks on 2 and 3 before doing the loop. You know that it will never be called for values less than 5. Perhaps we should rename it to is_prime_greater_than_three or something. That's also a slight performance improvement, although it would tend not to matter.

Answer 2

One of the fastest way to find primes is with a Sieve, which works like this:

_{(image courtesy of linked Wikipedia article)}

All you have to do is create an array with 2 million elements:

#define MAX 2000000

// ...

bool* getSieve()
{
    bool isPrimeArray[] = new bool[MAX + 1];

Then you perform the sieve to it:

    for (int i = 2; i <= n; i++) {
        isPrimeArray[i] = true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (isPrimeArray[i]) {
            for (int j = i; i * j <= n; j++) {
                isPrimeArray[i * j] = false;
            }
        }
    }

And sum it:

    int index = 0;
    long result = 0;
    for (boolean isPrime : isPrimeArray) {
        if (isPrime) {
            result += index;
        }
        index++;
    }
    return result;

Result:

#include <iostream>

#define MAX 2000000

bool* getSieve()
{
    bool isPrimeArray[] = new bool[MAX + 1];
    for (int i = 2; i <= n; i++) {
        isPrimeArray[i] = true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (isPrimeArray[i]) {
            for (int j = i; i * j <= n; j++) {
                isPrimeArray[i * j] = false;
            }
        }
    }
}

int sumAllPrimes()
{
    bool* isPrimeArray = getSieve();
    int index = 0;
    long result = 0;
    for (boolean isPrime : isPrimeArray) {
        if (isPrime) {
            result += index;
        }
        index++;
    }
    return result;
}

int main()
{
    cout << sumAllPrimes();
}

Answer 3

Well, you are checking for all of the prime numbers again for every iteration. To avoid this, you can keep a std::vector<int> containing already found primes, and check if a particular number is dividable from these first (which is similar to the Sieve of Eratosthenes technique).

Also even with your current implementation I see no point, why not breaking the loop as soon you hit the non prime condition, and just return either a bool result of false, or simply 0 immediately:

int nopf(int k){
    int sn=0;
    for(int b=2;b<k;b++) {
        if(k%b==0) return 0;
    }
    return 1;
}

You don't even use the returned value other than checking against 0.