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);
}
for(i = 0 ;numI <= numF; i++)
- thefor
will perform whilenumI
is less thannumF
. Since their values are 2 and 10 and are never changed, you have created an infinite loop (never leaves thefor
).– hkotsubo