Boas práticas de Desenvolvimento com Padrões Web

ELPI: Problema 5

Agora um com matemática. Quais os fatores primos do número 1321317089447443? Esse é o último par de ingressos para o ELPI no Rio de Janeiro. A partir de quinta-feira publico os problemas para o evento em Porto Alegre.

04/05/2008 por Elcio Ferreira

20 Comentários

Tecnologia e Tendências

Agora um com matemática. Quais os fatores primos do número 1321317089447443?

Esse é o último par de ingressos para o ELPI no Rio de Janeiro. A partir de quinta-feira publico os problemas para o evento em Porto Alegre.

Ian Liu Rodrigues 04/05/2008 às 21:45

Esse é fácil :S
Mas eu não posso ir!

Edgard 04/05/2008 às 22:25

Mais um fácil, mesmo pq existem sites que fazem a fatoração. Além de ser um dos primeiros problemas que todo programador aprende

Marvin 05/05/2008 às 00:47

Muito fácil!!

Mas como moro em Recife, nem seria lucro ganhar os ingressos.
heheh

Hélio Ricardo 05/05/2008 às 01:48

2147483647!

Err! Sou do Rio, onde pego os convites?

Vilmondes Eracton 05/05/2008 às 02:04

Caramba! Esse número é muito grande. Acho que poderia ter sido colocado um número menor, já que a idéia é a construção do algoritmo. Enfim, o negócio ta sendo calculado aqui. Vou dormir e amanhã vejo se retornou algo. hehehe.

Vlw!

Elcio Ferreira 05/05/2008 às 02:18

Hélio, não entendi sua resposta. Com certeza não é isso.

Vilmondes Eracton 05/05/2008 às 03:07

5
2
2
2
2
7
2
2
2
3
7
2
2
2
2
5
1031
170279

http://img80.imageshack.us/my.php?image=primoswc2.jpg

Edgard 05/05/2008 às 09:37

Putz, até agora ninguém acertou …

Vilmondes, nenhum fator está certo, pra ser divisível por 5 precisa terminar com 5 ou 0, e pra ser divisível por 2 tem que ser par. Logo 2 e 5 não são fatores, e pior, vc não acertou nenhum dos fatores.

O seu problema é que o php não consegue representar números maiores que 2147483647 como inteiros, logo o 1321317089447443 virou um float. Não sei que algoritmo de fatoração você está usando, mas os fatores crescendo e decrescendo está meio estranho.

Vilmondes Eracton 05/05/2008 às 09:50

Edgard, eu vi que o php n conseguiu trabalhar de maneira correta com esse numero. O primeiro fator deveria ter sido o 11. Ele ta retornando o resto de 1321317089447443 / 5 como 0. E quanto aos fatores ’2′, eles são em relação ao resultado da divisão anterior, ou seja, 1321317089447443 / fator primo divisivel | resultado / fator primo divisivel e assim sucessivamente. Só ficou errado porque ele retornou resto 0 na divisal do 1321317089447443 por 5.

Vou ver se tem como fazer com q o php trabalhe com esse número.

Abraço!

Edgard 05/05/2008 às 12:09

Vilmondes, para trabalhar com números de precisão arbitrária em php você tem que usar o GMP.

E pelo visto você está usando o algoritmo trivial, só uma dica pra melhorar o tempo, e você não esperar muito, depois de você achar um fator n, o próximo fator é sempre maior ou igual a n.

Logo se o primeiro fator é 11, o segundo não pode ser menor … Como uma dica o segundo fator é 17.

Mas já adiantando existem soluções mais simples, hehe