10
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ You could also have look at existing questions about PE #10. Most advice about efficient algorithms is language independent. \$\endgroup\$ – Martin R Dec 16 '15 at 19:33
  • 1
    \$\begingroup\$ Since all the primes below 2,000,000 are well known. You could just pre-compute the answer. primes.utm.edu/lists/small/millions/primes1.zip \$\endgroup\$ – Martin York Dec 16 '15 at 21:06
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ By the way, you don't have to check all the way up to n$when you are checking for primality. The ceiling of the square root of n will do. \$\endgroup\$ – Juho Dec 17 '15 at 15:09
  • \$\begingroup\$ eliminating the even factors helped tons. nopf (no. of factors except 1 and the no. itself) if =0 would mean it is prime. Also using integer or long gave the wrong answer i had to use long long now it does execute it within seconds. The key was breaking out from the loop if the number passed divisibility checks \$\endgroup\$ – T3snake Dec 18 '15 at 4:29
8
\$\begingroup\$

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

Animated display of how the Sieve generates primes up to 120
(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();
}
\$\endgroup\$
  • \$\begingroup\$ bool isPrimeArray[] = new bool[MAX + 1];!!!!! \$\endgroup\$ – Martin York Dec 16 '15 at 21:02
  • 1
    \$\begingroup\$ You should submit this answer as a question for code review. \$\endgroup\$ – Martin York Dec 16 '15 at 21:10
  • \$\begingroup\$ @Deduplicator. If you were going for more than 2,000,000 maybe. But that's only 2M of memory. I would use bytes. The extra cost (for code and developer) of working out and accessing bit positions is not worth it. \$\endgroup\$ – Martin York Dec 16 '15 at 21:13
  • \$\begingroup\$ "The fastest way to find primes is with a Sieve..." is quite bold of a statement. It is just one approach. \$\endgroup\$ – Juho Dec 17 '15 at 15:11
  • \$\begingroup\$ I wasnt familiar with the method. Will try applying it. \$\endgroup\$ – T3snake Dec 18 '15 at 4:33
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Small nitpicking: What you describe in the first paragraph is not the Sieve of Erasthotenes. That algorithm does not do any divisibility checks, even not against a smaller list of primes. \$\endgroup\$ – Martin R Dec 16 '15 at 19:36
  • \$\begingroup\$ @MartinR But as mentioned, could be changed easily into this direction to be optimized. May be I misunderstood what the SoE actually was good for. \$\endgroup\$ – πάντα ῥεῖ Dec 16 '15 at 19:39
  • \$\begingroup\$ I don't deny that what you described is an optimization. I am only stating that it is not the "Sieve of Eratosthenes". \$\endgroup\$ – Martin R Dec 16 '15 at 19:41
  • \$\begingroup\$ I was calculating the number of factors except 1 and the number itself.... if it was = 0 the number would be prime. using breal basically solved everything... now it executes within seconds \$\endgroup\$ – T3snake Dec 18 '15 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.