Esta é uma solução em C# para o problema PRIME 1 no SPOJ que consiste em calcular todos os números primos dentro de certos intervalos (mais info. http://spoj.pl/problems/PRIME1).Resolvi com um crivo de erastótenes levemente modificado, já com primos tabelados até 31627 (menor inteiro que é >= raiz quadrada de 1.000.000.000), já pulando os números pares e checando na tabela só até a raiz de N, para cada N no intervalo passado ao programa. Ainda há uma tentativa de paralelizar a operação, mas que não surtiu efeito no SPOJ, provavelmente o sistema deles roda a aplicação em uma CPU somente. Tentei procurar o mínimo possível na net de forma a botar a cuca pra funfar, a única coisa que utilizei da internet foi o teoreminha da raiz quadrada de N. O próximo passo será tentar acelerar o cálculo utilizando testes estatísticos de primalidade, mas para isso precisarei implementar um modulozinho de matemática de precisão arbitrária, o que já é mtos outros posts 😉 Execução no SPOJ levou 2,75 segundos e 25MB de memória. (A maior parte da memória é o runtime, gordo, que usa.)

Continue lendo