fredericopissarra Posted November 2, 2019 at 02:06 PM Share Posted November 2, 2019 at 02:06 PM 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 to comment Share on other sites More sharing options...
fredericopissarra Posted November 2, 2019 at 02:10 PM Author Share Posted November 2, 2019 at 02:10 PM 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 to comment Share on other sites More sharing options...
trevizan Posted November 4, 2019 at 02:32 AM Share Posted November 4, 2019 at 02:32 AM 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 to comment Share on other sites More sharing options...
bratergames Posted November 4, 2019 at 09:40 AM Share Posted November 4, 2019 at 09:40 AM 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 to comment Share on other sites More sharing options...
fredericopissarra Posted November 4, 2019 at 12:30 PM Author Share Posted November 4, 2019 at 12:30 PM 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 to comment Share on other sites More sharing options...
trevizan Posted November 4, 2019 at 11:42 PM Share Posted November 4, 2019 at 11:42 PM 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 to comment Share on other sites More sharing options...
fredericopissarra Posted November 5, 2019 at 01:58 AM Author Share Posted November 5, 2019 at 01:58 AM 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 to comment Share on other sites More sharing options...
trevizan Posted November 5, 2019 at 02:37 AM Share Posted November 5, 2019 at 02:37 AM 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 to comment Share on other sites More sharing options...
fredericopissarra Posted November 5, 2019 at 01:17 PM Author Share Posted November 5, 2019 at 01:17 PM 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 to comment Share on other sites More sharing options...
jweyrich Posted December 19, 2019 at 11:19 PM Share Posted December 19, 2019 at 11:19 PM 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 to comment Share on other sites More sharing options...
fredericopissarra Posted December 22, 2019 at 12:35 AM Author Share Posted December 22, 2019 at 12:35 AM 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 to comment Share on other sites More sharing options...
Recommended Posts
Archived
This topic is now archived and is closed to further replies.