Posts Tagged ‘primes’

Problem 10 of PE’s website says:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Note: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. (From Wikipedia)

And here is the C code. This time the unique remarkable fact is the fastness of the program:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int esPrimo (unsigned long long int num);
/* Returns 1 if "num" is a prime number. 
Otherwise it returns 0 */

unsigned long long int sumPrimes (unsigned int below_n);
/* Returns the summation of all prime 
numbers below the number "below_n" */

int esPrimo (unsigned long long int num){
    
    int retorno = 1;
    unsigned long long int i = 5LL;
    unsigned long long int r;

    if (num == 1){
		retorno = 0LL; /* 1 is not considered a prime number */
    } else if (num < 4) {
		retorno = 1;
    } else if (num % 2 == 0) {
		retorno = 0;
    } else if (num < 9){
		retorno = 1;
    } else if (num % 3 == 0) {
		retorno = 0;
    } else {
		r = (unsigned long long int) sqrt ((double) num);
		i = 5LL;
		while (i <= r){
			if (num % i == 0){
				retorno = 0;
				break;
			}
			if (num % (i + 2) == 0){
				retorno = 0;
				break;
			}
			i = i + 6LL;
		}
    }
    
    return retorno;
}

unsigned long long int sumPrimes (unsigned int below_n){

    unsigned long long int result = 0;
    unsigned int i = 0;
    
    for (i = 0; i < below_n; i++){
		if (esPrimo (i)){
			result += i;
		}
	}

    return result;
}


int main (int argc, char *argv[]){

    unsigned int below_number = (unsigned int) atoi (argv[1]);

    printf ("%llu\n", sumPrimes (below_number));
    
    return 0;
}

This time I will execute the program with the Unix time command, which displays the system resource usage of a program during its execution time:

$ (gcc -Wall -Wconversion prob10.c) && time ./a.out 2000000
142913828922

real 0m1.002s
user 0m1.000s
sys 0m0.000s

It took only one second to perform the summation of all prime numbers below two million! Take a moment to think about the significance of this fact. What makes this program fast is the efficiency of the algorithm that evaluates whether a number is prime.
Compare it now with the first version of the algorithm I wrote:

int esPrimo (unsigned long long int num){
    
    int retorno = 1;
    unsigned long long int i = 2LL;
    
    for (i = 2LL; i <= sqrt ((double) num); i++){
      if (num % i == 0){
         retorno = 0;
         break;
      }
    }
    
    if (num == 0){
      retorno = 0;
    }
    
    return retorno;
}

This one is a more straightforward one, because it just implements the primitive definition of prime number. But this is also an inconvenience, because it doesn’t even care about some implications of the definition. For example, the fact that if 2 is not a divisor of, let’s say, 17, implies that nor 4 neither 6 will be divisors of it, because they can be decomposed by a product where there is at least a 2. The first algorithm just skips all the composite numbers of the ones evaluated before, and that gives its efficiency.

Let’s measure now the time which this “not optimized” version of the same program spends during its execution time:

(gcc -Wall -Wconversion prob10.c -lm) && time ./a.out 2000000
142913828922

real 0m10.278s
user 0m10.269s
sys 0m0.004s

10x times slower. No more words are needed.