Posts Tagged ‘number’

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.

I’m actually working out the problems proposed in Project Euler’s website and I thought that it could be useful for many people if I post here my solutions for some of them. 

The problem 4 says: 

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I just generalized this problem by writing out a modular program, in C, that finds the largest Palindrome for any number of digits given in the command line.

The program may seem larger than necessary, but that’s because I used some general functions I defined a while ago for other purposes, so they work fine with any (valid) input (so at the far end that made me easier to structure the program 🙂 ).

#include <stdio.h>
#include <stdlib.h>
 
double exponenciar (double base, int exponent); 
/* Returns the result of (base ^ exponent) */
 
int calculaXifres (int n);
/* Returns the number of digits of the number "n". */
 
long int aIntegerstoInteger (long int array_de_integers[], 
                             int longitud); 
/* Maps each element of the array of integers
 "array_de_integers", of "longitud" elements, 
to each digit of an integer, and returns it back. 
For instance,
 
aIntegerstoInteger ({2, 1, 5}, 3) 
 
will return 215. I will only use this function once, 
just for making easier the inversion of a number. */
 
long int invertirNumero (long int num); 
/* Returns the number "num" inverted */
 
long int maxValueNdigits (int num_digits); 
/* Returns the maximum value that a number with 
"num_digits" digits can reach. For example, 
maxValueNdigits (4) would return 9999. */
 
long int largestPalindrome (int num_digits); 
/* Returns the answer of this problem when 
num_digits = 3. */
 
 
double exponenciar (double base, int exponent){
 
    double retorna;
 
    if (exponent == 0){
      retorna = 1;
    } else {
      retorna = base * exponenciar (base, exponent - 1);
    }
 
    return retorna;
}
 
int calculaXifres (int n){
 
    int quocient = n;
    int comptador = 0;
 
    while (quocient > 0){
      quocient = quocient / 10;
      comptador++;
    }
 
    return comptador;
}
 
long int aIntegerstoInteger (long int array_de_integers[], 
                             int longitud){
     
    int num_elements = longitud;
    int i = 0;
    long int integer = 0;
 
    for (i = 0; i < num_elements; i++){
      integer += array_de_integers[i] * 
                 (int) exponenciar (10, num_elements - (i + 1));
    }
 
    return integer;
}
 
long int invertirNumero (long int num){
     
    int longitud = calculaXifres (num);
    long int num_invertit[longitud];
    long int numero_invertit;
    int i = 0;
     
    for (i = 0; i < longitud; i++){
      num_invertit[i] = num % 10;
      num = num / 10;
    }
 
    numero_invertit = aIntegerstoInteger (num_invertit, longitud);
 
    return numero_invertit;
}
 
 
long int maxValueNdigits (int num_digits){
     
    int i = 0;
    long int max_value = 0;
 
    for (i = 0; i < num_digits; i++){
       max_value = max_value + (int) exponenciar (10, i);
    }
 
    max_value = 9*max_value;
 
    return max_value;
}
 
 
long int largestPalindrome (int num_digits){
     
    long int starting = (long int) exponenciar (10, num_digits - 1);
    long int ending = maxValueNdigits(num_digits);
    long int i = starting;
    long int j = i;
    long int largest_palindrome = 0L;
 
    for (i = starting; i <= ending; i++){
      for (j = starting; j <= ending; j++){
         if (i * j == invertirNumero (i * j) &&
            i * j >= largest_palindrome){
            largest_palindrome = i * j;
         }
      }
    }
 
    return largest_palindrome;
}
 
 
int main (int argc, char *argv[]){
 
    int num_digits = atoi (argv[1]);
 
    printf ("%ld\n", largestPalindrome (num_digits));
     
    return 0;
}

Time to compile and to execute the program:

$ (gcc -Wall -Wconversion prob4.c) && ./a.out 3
906609

And the three-digit factors are 993 and 913, it is to say, 993 \times 913 = 906609.