Podemos atacar a questão com um pouco mais de matemática, para então podermos usar outros conceitos de programação. Nesta daqui, vamos abusar do fato de funções puras poderem sofrer memoização.
Resumindo:
- função pura: dada uma função pura
f
, se você passar o argumento a
, então o valor de f(a)
é sempre o mesmo; diz-se de funções que não necessitam de efeitos colaterais
- memoização: aprendizado na maneira mais simples possível; se eu sei que
f(a) = b
após fazer una computação pesada, então da próxima vez que me for pedido f(a)
, retorno b
sem computar quase nada; normalmente não é considerado memoização um pré-processamento
Estamos falando aqui da função pura soma_primos_em_intervalo_fechado(início, fim)
. Porém, o domínio dessa função é grande (na ordem de o(n^2)
, sendo n
a maior entrada possível). Então, essa função não me interessa memoizar.
Porém, essa função pode ser decomposta em uma subtração de uma função pura para dois argumentos distintos:
soma_primos_em_intervalo_fechado(início, fim):
acumulado_primos_desde_0(fim) - acumulado_primos_desde_0(início - 1)
Vou ficar devendo a demonstração, mas ela é fácil
Então, essa outra função pura tem domínio da ordem de o(n)
, já é sujeito a memoização. Então, agora nosso problema é apenas definir e escrever essa função acumulado_primos_desde_0(n)
, usando memoização para otimizar eventuais consultas repetidas.
Essa função vai retornar a soma de todos os números primos até o valor positivo n
. Então, se n
não é primo, acumulado_primos_desde_0(n) = acumulado_primos_desde_0(n-1)
. Entretanto, se n
for primo, então temos que acumulado_primos_desde_0(n) = n + acumulado_primos_desde_0(n-1)
.
Assim, podemos definir a função dessa maneira:
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
Como nunca se insere valores negativos nessa função, eu tenho certeza que, para qualquer valor, acumulado_primos_desde_0(n) >= 0
. Então posso inicializar meu vetor de memoização com -1
que, como eu garanto que não pertence ao contra-domínio, então significa que meu cache não está carregado com um valor válido, portanto devo fazer a computação pesada.
A definição da função, usando a memoização da maneira mais eficiente que eu consigo imaginar, ficaria assim:
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);
}
}
Pegue sua versão favorita de detecção de primabilidade, como as opções da resposta do @Lacobus.
Note que o valor do cache é sempre atualizado após um cache miss (exceto parâmetros não-positivos). Portanto, dado a sua variante favorita de eh_primo
, as seguintes funções tratam o problema:
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++)
- ofor
vai executar enquantonumI
for menor quenumF
. Como os valores deles são 2 e 10 e nunca são mudados, você criou um loop infinito (nunca sai dofor
).