Sum of cousins in a range in C

I was seeing 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;
}

No for(i = 0 ;numI <= numF; i++) o i must be equal to numI which in the 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, then:

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

How to do it?

Within the first for add another for like this:

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

After creating this loop you will compare the i that in the case is your number (that is being traversed from beginning to end) with your j that will go from 1 to itself to test if it has more some divider (if 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);


.
.
.

We can tackle the issue with a bit more math, so we can use other programming concepts. Here we are going to abuse the fact that pure functions might suffer memoing .

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 of functions that do not require side effects
• memo: learning in the simplest possible way; if I know f(a) = b after doing a heavy computation, then the next time I'm asked f(a) , return b without computing almost nothing; a pre-processing is not normally considered as memo

We're talking here about the pure function soma_primos_em_intervalo_fechado(início, fim) . However, the domain of this function is large (in the order of o(n^2) , with n being the largest possible entry ). So this function does not interest me to memoise.

However, this function can be decomposed into a subtraction of a pure function for two distinct arguments:

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

  

I'm going to owe the demo, but it's easy

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

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

So we can define the function 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 you never enter negative values in this function, I'm sure, for any value, acumulado_primos_desde_0(n) >= 0 . So I can initialize my memoization vector with -1 which, as I guarantee it does not belong to the counterdomain, then means that my cache is not loaded with a valid value, so I should do heavy computation.

The definition of the function, using the memoization in the most efficient way that 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);
  }
}

  

Get your favorite version of primability detection, such as @Lacobus response .

Note that the cache value is always updated after a cache miss (except non-positive parameters). So, given your 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);
}

First, you'll need a routine that can determine if 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 cousins contained within 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 at Ideone.com

EDIT: As mentioned by @Jefferson Quesado , the function to determine if a prime number 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 at Ideone.com

We can tackle the issue with a bit more math, so we can use other programming concepts. In this one, let's take advantage of the fact that it is possible (and efficient) to precompute the cousins. A bit of preprocessing in an initial set can make a future computation much faster, especially when it's done over and over again.

  

Normally, in competitive programming issues, the program runs only once and is tested against a range of possible inputs. An example of this is the model of the ACM Programming Marathon. OBI, in my memory, has been this way too, but for a while it has changed the approach so that each execution of the program is one per entry; so, we would have it run 15 times if it were 15 test cases.

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

It starts with a Boolean list. A priori, every number has the potential to be prime, but if you find a prime number of truth, all of its multiples must be marked as non-prime. You can optimize the execution of it to decrease memory by half, the expenditure of a little more calculation (plus a 3, 4 arithmetic operations per access position in the vector). You can also optimize for, for each found cousin, only doing o(n/p - p) "cousin potential override" operations. See more details on the algorithm in this answer .

I do not recall the runtime of the sieve, but it is something larger than linear and less than quadratic. And you have the advantage of only running once and you can save the results forever.

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

Let us assume that the variable filled with the cousins obtained by the Eratosthenes sieve is called primos , and the total number of primes found is called qnt_primos . If you want to sum all cousins in the closed range [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 is still easy to consider a binary search algorithm to find the index j of the lowest available prime, which is primos[j] <= numI .