fredericopissarra Postado Novembro 2, 2019 em 14:06 Compartilhar Postado Novembro 2, 2019 em 14:06 Artigo original: https://is.gd/sDQ7Oa Esse é um dos exercícios mais comuns na área acadêmica: Dizer se um número é primo ou não. Existe a maneira tradicional, a maneira rápida e a maneira super rápida… As duas primeiras eram minhas velhas conhecidas e já falei delas aqui, eis um resumão: O método tradicional é dividir todos os valores inferiores ao número n, sob teste, até chegarmos a 2 e se o resto de qualquer uma das divisões der zero, isso indica uma divisibilidade e, portanto, o valor não é primo: int isPrime( unsigned int n ) { unsigned int i; // casos especiais... 3 e 2 são primos, mas 1 e 0 não são! if ( n <= 3 ) return ! ( n < 2 ); for ( i = 2; i < n; i++ ) if ( ( n % i ) == 0 ) return 0; return 1; } O método rápido reduz o a quantidade de iterações do loop porque só precisamos verificar a divisibilidade de valores inferiores ou iguais à raiz quadrada de n. Isso é baseado na propriedade comutativa e do princípio fundamental da aritmética: 2*3 é a msma coisa que 3*2, então não precisamos testar os dois casos. Ainda, qualquer valor pode ser fatorado em primos… Outro detalhe importante para o teste é que só existe um valor par primo: 2, todos os demais são ímpares: int isPrime( unsigned int x ) { unsigned int i, s; if ( n <= 3 ) return ! ( n < 2 ); // Apenas 2 é um valor par primo! if ( n % 2 == 0 ) return 0; // Só precisaremos testart até a raiz quadrada... s = sqrt(n); // Não precisamos testar a divisibilidade por nenhum valor par. for ( i = 3; i <= s; i += 2 ) if ( ( n % i ) == 0 ) return 0; return 1; } Quando você acha que achou o código mais rápido possível algum detalhe te supreende. O código acima pode ser acelerado um bocado se pensamos que se o valor n é divisível por 6, então ele é divisível por 3 e por 2 e, portanto, não é primo. De outro modo, podemos retirar valores que, divididos por 6, resultam em restos 2, 3 ou 4, já que, com toda certeza, eles não são primos (ou são divisíveis por 2 ou 3): int isPrime(unsigned int n) { unsigned int i, s; if (n <= 3) return ! ( n < 2 ); // Mais um caso especial... Se for divisível por 2 ou 3, não é primo! if ( ( n % 2 ) == 0 || ( n % 3 ) == 0) return 0; s = sqrt(n); for ( i = 5; i <= s; i += 4 ) { if ( ( n % i ) == 0) return 0; i += 2 if ( ( n % i ) == 0) return 0; } return 1; } O código acima executa o loop cerca de 3 vezes mais rápido que o código anterior e é matematicamente correto. Claro, existe o problema de que duas divisões são feitas no loop, mas o compilador tende a otimizar isso… PS: Lembrando que existe um outro método, rápido, mas que consome muita memória: Trata-se do “Crivo de Eastótenes” que encontra os valores primos tentando as divisões com os valores primos anteriormente encontrados (até a raiz quadrada de n, como acima)… O “Crivo” é o método mais rápido, mas como eu disse, tem o potencial de consumir MUITA memória, porque precisamos manter um array com os valores previamente encontrados. Link para o comentário Compartilhar em outros sites More sharing options...
fredericopissarra Postado Novembro 2, 2019 em 14:10 Autor Compartilhar Postado Novembro 2, 2019 em 14:10 PS: Eu não pensei nesse terceiro método. Ele me foi apresentado num forum, onde duvidei bastante da "correção" matemática dele. Mas, acaba que o troço tá certo mesmo... Vivendo e aprendendo... Link para o comentário Compartilhar em outros sites More sharing options...
trevizan Postado Novembro 4, 2019 em 02:32 Compartilhar Postado Novembro 4, 2019 em 02:32 Em 02/11/2019 em 11:10, fredericopissarra disse: PS: Eu não pensei nesse terceiro método. Ele me foi apresentado num forum, onde duvidei bastante da "correção" matemática dele. Mas, acaba que o troço tá certo mesmo... Vivendo e aprendendo... Muito interessante, acho que consigo explicar como funciona de uma forma complementar. Esse algoritmo pula os ímpares múltiplos de três no momento que incrementa quatro no contador (i+=4) , a partir do número nove, visto que a divisibilidade por três já foi testada. Desta forma: testa o 5; // valor inicial testa o 7; //após incrementar i+=2 pula o 9; //ao incrementar i+=4 testa o 11; //após incrementar i+=4 testa o 13; //após incrementar i+=2 pula o 15; //ao incrementa i+=4 testa o 17; //após incrementar i+=4 testa o 19; //após incrementar i+=2 pula o 21; //ao incrementa i+=4 ... e assim por diante. Note que comparado a abordagem que você descreveu anteriormente, em um ciclo de três testes (if ( ( n % i ) == 0) ) um teste é eliminado . Assim, é possível eliminar 1/3 dos testes a serem executados. Link para o comentário Compartilhar em outros sites More sharing options...
bratergames Postado Novembro 4, 2019 em 09:40 Compartilhar Postado Novembro 4, 2019 em 09:40 Poxa eu achei o Tio Fred de novo...eu tava no grupo do facebook dele e voltei a estuar comp esse semestre agora estou apenas nos mips da vida. Muito bom te achar aqui tio fred. Link para o comentário Compartilhar em outros sites More sharing options...
fredericopissarra Postado Novembro 4, 2019 em 12:30 Autor Compartilhar Postado Novembro 4, 2019 em 12:30 Já eu, @bratergames, nunca parei de estudar e estou com os ARM da vida, mas não "apenas"... ? Tio Fred só sumiu do facebook (nunca mais entro naquela bosta) e do discord do mente binária... Link para o comentário Compartilhar em outros sites More sharing options...
trevizan Postado Novembro 4, 2019 em 23:42 Compartilhar Postado Novembro 4, 2019 em 23:42 Olás! Fiquei pensando como seria estender a estratégia de eliminar os testes de ímpares múltiplos de três para também eliminar os testes dos múltiplos de cinco. Cheguei ao seguinte algoritmo. Este executa cerca de 13% mais rápido que o algoritmo anterior e cerca de 47% mais rápido que o algoritmo que só considera a raiz quadrada. int isPrime(unsigned int n) { unsigned int i, s; if (n <= 5) return (n == 2 || n == 3 || n == 5); // Mais um caso especial... Se for divisível por 2, ou por 3, ou por 5, não é primo! if ( ( n % 2 ) == 0 || ( n % 3 ) == 0 || ( n % 5 ) == 0) return 0; s = sqrt(n); for ( i = 7; i <= s; i += 6 ) { if ( ( n % i ) == 0) return 0; i += 4; if ( ( n % i ) == 0) return 0; i += 2; if ( ( n % i ) == 0) return 0; i += 4; if ( ( n % i ) == 0) return 0; i += 2; if ( ( n % i ) == 0) return 0; i += 4; if ( ( n % i ) == 0) return 0; i += 6; if ( ( n % i ) == 0) return 0; i += 2; if ( ( n % i ) == 0) return 0; } return 1; } Link para o comentário Compartilhar em outros sites More sharing options...
fredericopissarra Postado Novembro 5, 2019 em 01:58 Autor Compartilhar Postado Novembro 5, 2019 em 01:58 Well... Talvez, temos que verificar (a validade do algoritmo anterior é um cadinho mais complicada do que eu postei - desse ai, eu não sei)... Mas, de qualquer maneira, temos que parar em algum lugar, não? Senão o algoritmo degenera para o crivo de Erastótenes. Link para o comentário Compartilhar em outros sites More sharing options...
trevizan Postado Novembro 5, 2019 em 02:37 Compartilhar Postado Novembro 5, 2019 em 02:37 Basicamente eu vi quais valores precisavam ser testados (os que não eram múltiplos de 2, 3 ou 5) a partir do número 7 e notei que essa sequência de incremento se repetia (como um padrão): 4, 2, 4, 2, 4, 6, 2 e 6. Validei os resultados de 2 a pouco mais de 32 mil e não apresentou nenhum retorno incorreto para o intervalo. Enfim, o problema é que a complexidade de todos esses algoritmos ainda é da ordem de grandeza de raiz quadrada de n, ou seja, ainda é alta. Eu preciso estudar melhor o crivo de Erastótenes para opinar, mas a primeira vista a abordagem me parece bem diferente e o ganho de desempenho não compensa a limitação de valor máximo que pode ser testado. Daí talvez seja mais interessante brincar com coisas mais sérias, como o teste de Fermat ou AKS, que apresentam complexidade logarítmica. Link para o comentário Compartilhar em outros sites More sharing options...
fredericopissarra Postado Novembro 5, 2019 em 13:17 Autor Compartilhar Postado Novembro 5, 2019 em 13:17 Não estou dizendo que sua aproximação está errada ou que seja ruim. Só o que estou dizendo é que, talvez, ela possa falhar em algum momento. Limitar os testes a uma faixa que "dá certo" não quer dizer que o algoritmo vai funcionar para toda a faixa... A otimização que postei (que não foi minha, vi num forum e achei interessante) funciona para qualquer valor N, inteiro, de qualquer precisão... O sujeito que bolou isso percebeu que quando um valor é primo e é maior que 4, ele pode ser expresso por 6n+/-k (onde k={0..5}, ou seja, k=n mod 6)... mas, k não pode ser 0, 2, 3 ou 4 (senão teremos valor par [k=0,2,4] ou divisível por 3 [k=3]). Assim, k só pode ser 1 ou 5. Agora, tomemos n=1 e obteremos 5 (6*1-1) e 7 (6*1+1), e 1 (6*1-5) e 11 (6*1+5). Esses são candidatos a primazia... Se você fizer n=2 (n+1), teremos 11 (6*2-1), 13 (6*2+1), 7 (6*2-5) e 17 (6*2+5). Claramente (e podemos comprovar isso por congruência) testes com k=5 são cobertos pelos mesmos testes onde k=1 e podemos descartar k=5. Dai, o testes de primazia só precisam ser feitos com 6n-1 e 6n+1. Por isso o loop começa em 5, avançamos k em 2 unidades (de -1 para +1), testamos o próximo e testamos de novo... avançamos 4 unidades (por causa do 6n) e fazemos tudo de novo... O que descrevi acima é uma prova por "indução matemática" e é garantido que o resultado seja o mesmo para qualquer N... Teríamos que provar, de maneira semelhante, que sua aproximação é válida para qualquer N inteiro positivo e é isso que eu não tenho certeza (porque não pensei à respeito) que esteja correto. Quanto ao crivo de Erastótenes. Basicamente ele realiza as divisões apenas com os valores prímos previamente encontrados, no loop, mas precisa armazená-los num grande array. Esse é o método mais "rápido" (e um pouquinho mais complicado), mas potencialemente usa muita memória para isso. No caso, mesmo não usando arrays, a cadeia de testes ficaria muito grande e é bom lembrar que cada divisão é LENTA. Uma rotina com 2 divisões não é cria lá grande perda de velocidade, mas uma com 8 divisões dentro do loop tem o potencial de ser bem lenta. [[]]ão Fred Link para o comentário Compartilhar em outros sites More sharing options...
jweyrich Postado Dezembro 19, 2019 em 23:19 Compartilhar Postado Dezembro 19, 2019 em 23:19 Pra quem gosta desse desafio, recomendo dar uma olhada (ou estudada) num algoritmo chamado "Sieve of Eratosthenes". Acho que ainda é a implementação mais rápida para teste de primalidade. Ele usa essa a técnica descrita pelo Fred e expande com algumas outras. Bastante teoria dos números e fatoração! Dei uma leve estudada nesse algoritmo quando precisei estudar (quebra de) criptografia e "de quebra" acabei em fatoração pesada, gcd, etc. Cheguei a sonhar com uma idéia de quebrar os certificados digitais gerados pela openssl. Aí eu acordei! haha :D No mês seguinte publicaram um bug no OpenSSH relacionado à constante RSA_F4 :O De qualquer forma os insights foram muito valiosos. Link para o comentário Compartilhar em outros sites More sharing options...
fredericopissarra Postado Dezembro 22, 2019 em 00:35 Autor Compartilhar Postado Dezembro 22, 2019 em 00:35 O "crivo de Erastótenes" é um dos mais antigos algoritmos para teste primazia (século II A.E.C.). O teste anterior, diferente do crivo, não exige armazenamento temporário (array). O uso de um array é ruim para testes com valores muito altos. Claro, estou falando do algoritmo original. Link para o comentário Compartilhar em outros sites More sharing options...
Posts Recomendados
Arquivado
Este tópico foi arquivado e está fechado para novas respostas.