Ué, não tem nada demais. Vc está simplesmente tentando dividir o dado número n por todos os valores inteiros entre 3 e sqrt(n).
Pq vc pode parar em sqrt(n)? Oras, digamos que n seja divisivel por a, a > sqrt(n). Então seja b = n / a, que é inteiro. b = n / a ab = n ab = sqrt(n) sqrt(n) b = sqrt(n) * sqrt(n)/a Mas a > sqrt(n) ==> sqrt(n)/a < 1 Logo b < sqrt(n). Conclusão: se n tem um divisor maior que sqrt(n), então ele tem necessariamente um divisor correspondente, este menor que sqrt(n). Por isso que vc pode testar só entre 3 e sqrt(n). Isso dito, esse algoritmo não tem absolutamente nada de especial em questões de performance. De imediato, vc já pode deixar seu algoritmo 2 vezes mais rápido: se vc verificar que n é ímpar, vc não precisa mais testar as divisões por pares. Veja o artigo sobre "primality test" na wikipedia, tem informações interessantes. Tem vários algoritmos probabilísticos, em que a resposta é incerta, mas a incerteza é controlada. Mais interessante, há algorítmos que se dizem que um número é composto, então ele é certamente composto, mas se diz que é primo, ele pode ter se enganado. Há algorítmos que se comportam da maneira oposta (se disse que é primo, então é primo, mas se disser que é composto, pode ter se enganado). Esses algoritmos probabilísticos trocam o determinismo por um aumento violento de performance. Há também outros algorítmos deterministas muito mais rápidos que o seu, mas a maior parte depende de hipóteses não provadas em teoria dos números. Abraço Bruno -- Bruno FRANÇA DOS REIS msn: [email protected] skype: brunoreis666 tel: +33 (0)6 28 43 42 16 http://brunoreis.com GPG Key: http://brunoreis.com/bruno-public.key e^(pi*i)+1=0 2010/1/12 Marcelo Gomes <[email protected]> > Olá pessoal da lista, boa noite. > > Meu grupo de estudo estava tentando montar um algortmo mais enxuto, com uma > menor carga computacional para se calcular os primos até 12 dígitos. > Pesquisando na net, vi que existe uma propriedade matemática da raiz > quadrada dos primos. > > Digamos que possua "n" como candidato a primo (n>2) então calculo sua raiz > quadrada , uso a parte inteira desta raiz e opero as divisões de "n" por > esta parte inteira e em seguida pala parte inteira menos 1, depois pela > parte inteira menos 2 sucessivamente até chegar no número 3. Se o resultado > destas divisões de "n" pela parte inteira da raiz, e seus antecessores > inteiros até 3 for diferente de Zero, então não preciso calcular os outros > inteiros pós raiz. Com apenas o primeiro calculo já saberei que o "n" é > primo. > > No algoritmo isto funcionou perfeitamente e o programa ficou bem rápido. > > Entretanto, não consegui ver ainda como provar esta propriedade matemática. > Se alguém tiver um tempinho e puder mostrar isto, seria bem interessante > para mim. > > Desde já agradeço muito a atenção e ajuda, > > Abração a todos, Marcelo. >
