Resolvendo problemas do Projeto Euler com J — Dois coelhos com um tiro

A proposta agora é resolver o problema 10.

O problema consiste em encontrar o somatório dos números primos menores que um determinado número. Os números primos menores que 10 são 2, 3, 5, 7. O somatório, portanto é 17 (2 + 3 + 5 + 7).

Vimos anteriormente que para somar os valores de um vetor podemos utilizar +/ . Resta agora encontrar os números primos. Para saber se um número é primo, basta ver se ele é divisível por 1 e ele mesmo. Podemos simplesmente pegar o número e tentar dividir por 2, 3, …. n-1. Se algum resultado não for um número natural (inteiro, positivo e maior que zero), o número não é primo. Mas não seria a melhor solução para valores grande, como por exemplo 2.000.000. Existem outros algoritmos mais eficientes para efetuar o cálculo mas, como a proposta é resolver com J, nada melhor do que usarmos os recursos da linguagem em vez de adaptar algoritmos.

Vendo o vocabulário da linguagem, descobrimos que existe o verbo prime. Então p: n retorna o enésimo número primo. Nos resta saber quantos números primos existem em uma determinada faixa de números naturais. Na mesma página temos que _1 p: y retorna a quantidade de números primos menores que y. Ok, nosso problema está resolvido. Basta saber quantos números primos existem, retorna-los e somá-los. Para o exemplo no início da entrada, que é 10, temos:

_1 p: 10 => 4

p: i.4 +> 2 3 5 7

+/ 2 3 5 7 => 17

Agora é só juntar tudo e fica:

+/ p: i.(_1 p: 10)

Uma solução n00b para o problema seria (estamos aprendendo, então não somos experts na linguagem ainda; depois das soluções simples buscamos soluções mais idiomáticas):

p10 =. 3 : '+/ p: i.(_1 p: y)'

p10 10 => 17

p10 2000000 => 1.42914e11

Mas se eu necessitar do resultado exato? Posso usar um número de precisão estendida (colocar um x no final do número) para o verbo que o resultado será compatível (também poderia codificar no verbo utilizando x: )

p10 2000000x => 142913828922

Ok, mais um problema resolvido facilmente.

Não, não esqueci do segundo coelho. O problema 7 pede para descobrir o enésimo número primo. Como vimos no início deste artigo, p: n retorna o enésimo número primo. O único detalhe é que o primeiro número primo possui o índice 0 e não 1. Para retornar 2 usamo p: 0. Então, para o enésimo devemos informa enésimo – 1. Como o problema pede o 10001 passamos o anterior que é 10000. Podemos utilizar o decremento <: (que casualmente é o contrário do incremento >: ). Fica:

p: <: 10001 ou p: 10000

Molezinha né?

Anúncios