Sum of primes in a range in C

Question

My problem says to add the primes in a user-given range, including the ranges if these are primes. Example:

• ENTRANCE: 2 and 10

• EXIT: 17

I managed to do that:

#include <stdio.h>

int main()
{
    int numI, numF, primos = 0;

    scanf("%d %d", &numI, &numF);

    int i;
    for(i = 0 ;numI <= numF; i++){
        if((numI%2 == 0) && (numF%2 == 0))
            primos += i;
    }
    printf("%d", primos);
    return 0;
}

But it’s showing nothing after the two entries.

Answer 1

We can tackle the issue with a little more mathematics, so we can use other concepts of programming. In this one, let’s abuse the fact that pure functions may suffer memoisation.

In short:

• pure function: given a pure function f, if you pass the argument a, then the value of f(a) is always the same; it is said that functions do not require side effects
• memoization: learning in the simplest possible way; if I know that f(a) = b after doing a heavy computation, then the next time I am asked f(a), return b without computing almost anything; normally it is not considered to be a preprocessing memoization

We’re talking here about pure function soma_primos_em_intervalo_fechado(início, fim). However, the domain of this function is large (in order of o(n^2), being n as much input as possible). So, this function does not interest me.

However, this function can be decomposed into a subtraction from a pure function to two distinct arguments:

soma_primos_em_intervalo_fechado(início, fim):
    acumulado_primos_desde_0(fim) - acumulado_primos_desde_0(início - 1)

I’ll owe you the demonstration, but it’s easy

So, this other pure function has domain over the order of o(n), is already subject to memoization. So now our problem is just define and write this function acumulado_primos_desde_0(n), using memoization to optimize any repeated queries.

This function will return the sum of all prime numbers to the positive value n. So if n is not cousin, acumulado_primos_desde_0(n) = acumulado_primos_desde_0(n-1). However, if n for cousin, so we have to acumulado_primos_desde_0(n) = n + acumulado_primos_desde_0(n-1).

So we can define the function in this way:

acumulado_primos_desde_0(n):
    0, se n <= 0 # caso de falha/caso base
    acumulado_primos_desde_0(n-1), se n não for primo
    n + acumulado_primos_desde_0(n-1), se n for primo 

Since negative values are never inserted in this function, I’m sure that for any value, acumulado_primos_desde_0(n) >= 0. Then I can initialize my memoization vector with -1 which, as I guarantee does not belong to the counter-domain, then means that my cache is not loaded with a valid value, so I must do the heavy computation.

The definition of function, using memoization in the most efficient way I can imagine, would look like this:

int cache[]; // magicamente inicializou com -1
int acumulado_primos_desde_0(int n) {
  if (cache[n] != -1) {
    return 0;
  }

  if (n <= 0) {
    return 0;
  } else {
   return cache[n] = (eh_primo(n)? n: 0) + acumulado_primos_desde(n-1);
  }
}

Grab your favorite version of primality detection, such as the options from reply from @Lacobus.

Note that the cache value is always updated after a miss cache (except non-positive parameters). Therefore, given its favorite variant of eh_primo, the following functions address the problem:

int cache[]; // magicamente inicializou com -1
int acumulado_primos_desde_0(int n) {
  if (cache[n] != -1) {
    return 0;
  }

  if (n <= 0) {
    return 0;
  } else {
   return cache[n] = (eh_primo(n)? n: 0) + acumulado_primos_desde(n-1);
  }
}

int soma_primos_intervalo_fechado(int ini, int fim) {
  return acumulado_primos_desde_0(fim) - acumulado_primos_desde_0(ini-1);
}

Answer 2

I was looking at your code:

#include <stdio.h>

int main()
{
    int numI, numF, primos = 0;

    scanf("%d %d", &numI, &numF);

    int i;
    for(i = 0 ;numI <= numF; i++){
        if((numI%2 == 0) && (numF%2 == 0))
            primos += i;
    }
    printf("%d", primos);
    return 0;
}

In the for(i = 0 ;numI <= numF; i++) the i must be equal to numI which in case would be 2. Example:

for(i = numI ; i< numF; i++)

It is known that prime numbers are uniquely divisible by 1 and by itself, so:

Here if((numI%2 == 0) && (numF%2 == 0)) you are only testing whether the starting number and the ending are divisible by 2, so it is incorrect.

How to do?

Within the first for add another for thus:

for(j=1;j<i;j++)...

After creating this loop you will compare the i which in case is your number (which is being covered from start to finish) with your j that will run from 1 up to itself to test if it has any more splitter (if it has it is not prime);

Example:

.
.
.
.
int divisor,aux=0;
for(i = numI ; i< numF; i++){
    divisor=0;
    for(j=1;j<=i;j++){
        if(i%j==0)
        {
            divisor++;
        }

    }
       if(divisor==2)
        {
            aux=aux+i;
        }
}
printf("\nA soma dos primos eh:%d",aux);


.
.
.

Answer 3

First, you will need a routine capable of determining whether a number is prime:

int eh_primo( unsigned int n )
{
    unsigned int i = 0;

    if( n <= 1 )
        return 0;

    if( (n % 2 == 0) && (n > 2) )
        return 0;

    for( i = 3; i < n / 2; i += 2 )
        if( n % i == 0 )
            return 0;

    return 1;
}

To sum the primes contained in a given range:

int somar_primos( unsigned int inicio, unsigned int fim )
{
    unsigned int i = 0;
    unsigned int soma = 0;

    for( i = inicio; i < fim; i++ )
        if( eh_primo(i) )
            soma += i;

    return soma;
}

Testing:

int main( void )
{
    unsigned int numI, numF;
    scanf("%d %d", &numI, &numF);
    printf( "%d\n", somar_primos( numI, numF ) );
    return 0;
}

See working on Ideone.com

EDIT: As mentioned by @Jefferson Quesado, function to determine if a number is prime can have its search optimized by its square root, see:

int eh_primo( unsigned int n )
{
    unsigned int i = 0;

    if( n <= 1 )
        return 0;

    for( i = 2; i * i <= n; i++ )
        if( n % i == 0 )
            return 0;

    return 1;
}

See Working on Ideone.com

Answer 4

We can tackle the issue with a little more mathematics, so we can use other concepts of programming. In this one, let’s take advantage of the fact that it is possible (and efficient) to pre-compute the primes. A little pre-processing in an initial set can make a future computation much faster, even more so when it is done over and over again.

Normally, in matters of competitive programming, the program runs only once and is tested against a range of possible inputs. An example of this is the ACM Programming Marathon model. The OBI, as I recall, was once the same, but for a while it changed the approach so that each execution of the program would be one per input; so it has to run the program 15 times if there were 15 test cases.

To do this preprocessing, I will use an algorithm known since the time of the ancient Greeks: the sieve of Eratosthenes.

It starts with a boolean list. A priori, every number has the potential to be prime, but when finding a truth prime number, all multiples of it must be marked as non-prime. You can optimize the execution of it to halve the memory, the expenditure of a little more calculation (plus a 3, 4 arithmetic operations by accessing position in the vector). You can also optimize to, for each cousin found, do only o(n/p - p) "prime potential override" operations. See more details of the algorithm in this answer.

I do not remember the time of execution of the sieve, but it is something larger than linear and smaller than quadratic. And it has the advantage of only running once and you can keep the results forever.

The "return" of this function is a list of existing primes, and the argument is either the desired number of primes (Anderson Carlos Woss response) or the maximum size of the largest cousin. I think for your case we should pass 10000 (ten thousand) that we must have some safety margin. I can’t say for sure, you haven’t put the entry restrictions to your problem.

Let’s assume that the variable filled with the primes obtained by the Eratosthenes sieve is called primos, and the total amount of cousins found is called qnt_primos. If all primes are to be added at the closed interval [numI, numF], then just do the following:

int i;
int soma = 0;
int numero_iterado;

// ... faz os primos, faz as leituras necessárias

for (i = 0; i < qnt_primos; i++) {
  numero_iterado = primos[i];

  if (numero_iterado < numI) {
    continue; // volte para o começo do laço, ainda nem cheguei no mínimo 
  } else if (numero_iterado > numF) {
    break; // achei um primo que vai além do valor final, posso parar
  }
  soma += numero_iterado; // primo no intervalo, deve somar
}
printf("%d", soma);

If you want, it’s still easy to consider a binary search algorithm to find the index j of the smallest available prime, which is primos[j] <= numI.