saramgsilva Posted May 18, 2006 at 02:05 PM Report #28055 Posted May 18, 2006 at 02:05 PM Como consequência de vários tópicos que falarem na procura de números primos, venho falar num método muito simples para encontrar números primos O Crivo de Eratosthenes O algoritmo do Crivo de Eratosthenes possui um único argumento k, que é um número inteiro. Ao final de sua execução obtemos uma lista com todos os números primos inferiores ou igual a k é retornada. Sequencialmente, escreve-se todos os inteiros de 2 até k. Risca-se então todos os números maiores que 2 que são divisíveis por 2. No próximo passo, selecciona-se (de entre os números não riscados) o menor número que é superior a 2. Neste caso, esse número é o 3. Assim, risca-se todos os números maiores que 3 que são por ele divisíveis. O processo então recomeça, desta vez o menor número maior que 3 e não riscado é o 5. Portanto, risca-se todos os inteiros maiores que 5 que são por ele divisíveis. Continua-se a fazer este procedimento até que todos os números divisíveis por tenham sido riscados. Os números restantes que não foram riscados são todos primos: 2, 3, 5, 7, 11, 13,… Visualização do crivo: Pode obter mais informações em : Wikipedia PT -Crivo de Eratosthenes projetozk -Crivo de Eratóstenes Criptografia - CRIVO DE ERASTÓTENES E DIVISÃO POR TENTATIVA Números Primos [Artigo no Wiki] www.saramgsilva.com As minhas apps no WP7 Marketplace Youtube : Galinho - Windows Phone 7.5
UnKnowN Posted May 18, 2006 at 04:45 PM Report #28097 Posted May 18, 2006 at 04:45 PM Muito Obrigado Tofas já percebi 👍
Triton Posted May 18, 2006 at 04:49 PM Report #28100 Posted May 18, 2006 at 04:49 PM Quem quiser pesquisar, tem aqui um link para o Crivo de Atkin, uma técnica mais eficiente ainda. http://en.wikipedia.org/wiki/Sieve_of_Atkin <3 life
brink@ero Posted May 18, 2006 at 05:21 PM Report #28104 Posted May 18, 2006 at 05:21 PM O algoritmo do Crivo de Eratosthenes Muito bom, não conhecia. Mas sendo isto um algoritmo, vai para a secção dos algoritmos 😛 Cumpr. brink@ero 👍
mogers Posted May 18, 2006 at 06:29 PM Report #28119 Posted May 18, 2006 at 06:29 PM é um algoritmo muito útil. Eu por acaso antes de o conhecer criei-o... pensei na mesma coisa... só é problematico quando são números muito grandes e não temos memória para o usar (no caso de um concurso de programação ou outra coisa qualquer, onde a memória do programa é limitada). "What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.
vbmaster Posted May 18, 2006 at 06:39 PM Report #28121 Posted May 18, 2006 at 06:39 PM Deve ser uma maneira muito mais rápida e eficiente de achar número primos que o meu programazinho da baba em c++.... 👍 Hei de tentar implementá-lo e comparar tempos... 😛
Warrior Posted May 18, 2006 at 07:47 PM Report #28136 Posted May 18, 2006 at 07:47 PM é um algoritmo muito útil. Eu por acaso antes de o conhecer criei-o... pensei na mesma coisa... só é problematico quando são números muito grandes e não temos memória para o usar (no caso de um concurso de programação ou outra coisa qualquer, onde a memória do programa é limitada). Até pelo contrário, em concursos de programação eles dão-te sempre intervalos para trabalhar (raramente são superiores a 1.000.000) e o método do crivo demora menos de 1 segundo a calcular todos os primos nesse intervalo, e a memória ocupada não é por aí alem (1.90MB se usares um inteiro normal de C, 0.95MB um short int, 0.12MB se usares booleans (C++/Pascal). Qualquer dos valores é aceitável para um concurso. Se fores pelo método "normal", aí sim, tás com problemas devido ao tempo de execução. Obtens um "Runtime Error"
mogers Posted May 18, 2006 at 08:56 PM Report #28159 Posted May 18, 2006 at 08:56 PM Até pelo contrário, em concursos de programação eles dão-te sempre intervalos para trabalhar (raramente são superiores a 1.000.000) falaste bem ... "raramente" 👍 ... ja vi exercicios em k usar o crivo nao era viavel (pk os numeros eram bem maiores que 1M)... por acaso já foi há um tempo.. já não sei onde foi. cumps "What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.
Warrior Posted May 18, 2006 at 09:00 PM Report #28163 Posted May 18, 2006 at 09:00 PM Mas se não usares um crivo (seja o de Erastótenes, seja o de Atkin (foi a primeira vez que ouvi falar)) o que usas? Não resolver não é uma opção.
Triton Posted May 18, 2006 at 09:12 PM Report #28169 Posted May 18, 2006 at 09:12 PM Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe! 👍 <3 life
saramgsilva Posted May 19, 2006 at 08:33 AM Author Report #28220 Posted May 19, 2006 at 08:33 AM Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe! 😛 ya vou pesquisar sobre isso... não conhecia 😉 www.saramgsilva.com As minhas apps no WP7 Marketplace Youtube : Galinho - Windows Phone 7.5
José Oliveira Posted June 20, 2006 at 08:40 PM Report #33992 Posted June 20, 2006 at 08:40 PM Mais um exemplo: http://www.win.tue.nl/~ida/demo/c1s4ja.html José Oliveira Educação, Matemática e Tecnologias
Gurzi Posted May 23, 2007 at 05:03 PM Report #102349 Posted May 23, 2007 at 05:03 PM Bem, ontem decidi brincar com isto e pus-me a aprender java os básicos aplicando este conceito.. Gostava que analizassem o código e verificassem se existia alguma forma de melhorar ou incrementar a perfomance do programa.. class Primes{ int[] primos; public Primes(int quantidade) { primos = new int[quantidade]; } public void isPrime(int[] numeros) { // using Sieve of Eratosthenes for(int i = 2; i < (numeros.length / 2 ); i++) { for(int y = 1; y < numeros.length; y++) { if( numeros[y] % i == 0 && numeros[y] != i) { numeros[y] = 0; } } } showPrimes(numeros); } public void start(int maxNumber) { for(int i = 0,k= 2;i < maxNumber-1; i++,k++) { this.primos[i] = k; } isPrime(this.primos); } public void showPrimes(int[] value) { for(int j = 0; j < value.length ; j++) { if(value[j] != 0) System.out.println("Numero Primo : " + value[j] + "\n"); } } public static void main(String[] args) { Primes Pi = new Primes(150); Pi.start(150); } } Algumas dúvidas que podem surgir, inicei a 2 porque sei que o primeiro numero primo é 2( o 1 não é porque é necessário 4 divisores inteiros) e iniciei o for do array na posição 1 porque o 0 é do 2.. Uma coisa que me fez confusão foi a ordenação do vector, gostava que me esclarecessem se é melhor fazer como fiz, ou seja, colocar 0 onde não são numeros primos, ou apagar os 0 e deixar o arrray só com os numeros primos.. Abraços
Warrior Posted May 23, 2007 at 07:06 PM Report #102369 Posted May 23, 2007 at 07:06 PM Podes avançar o ciclo do y de i em i, e podes inicia-lo em i*i (desta forma também removes o if, pois todos os números onde ele calha são números para remover). O i não precisa de ir até ao numeros/2, basta-lhe ir até à raiz quadrado do numeros.length. Só entras no ciclo j, se o número i for primo (podes verificar no vector), caso contrário é desnecessário pois os números já foram todos cortados anteriormente. Isto para um crivo "normal", é o que se costuma fazer. Já vais ter um aumento de velocidade enorme se fizeres isto. Se quiseres mais melhorias.. Podes primeiro remover os pares, e depois avançar o i de 2 em 2, pois não vale a pena verificar todos os outros. Ou então repara que todos os primos são da forma 6k-1 ou 6k+1 (tirando o 2 e o 3), podes testar só esses..
JC1 Posted May 23, 2007 at 09:19 PM Report #102391 Posted May 23, 2007 at 09:19 PM Utilizar um bit para cada número, em vez de um byte.
shumy Posted May 23, 2007 at 09:32 PM Report #102395 Posted May 23, 2007 at 09:32 PM Trabalha ao contrario. Uma versão desse algoritmo. E usa listas não arrays. Ao contrário é: Começas com uma lista vazia (melhor logo com o 2), e um contador a 3. Vaz incrementando o contador e dividindo por todos os elementos da lista, se é primo não é divisivel por nenhum da lista, então inseres na lista. Chegas ao fim com a lista de números primos e não gastas memória desnecessária. Basicamente esqueci dizer que isto se apoia no metodo de factorização aprendido no ciclo. Porque todos os números não primos são uma multiplicação de um conjunto de números primos. Aqui há coisa de 2 anos fazia umas malhas de croché, depois fartei-me e fui para informática!
Warrior Posted May 23, 2007 at 09:56 PM Report #102400 Posted May 23, 2007 at 09:56 PM Esse método é mais lento, e não recorre ao crivo de Eratóstenes (o que ele pretendia inicialmente)
djthyrax Posted May 23, 2007 at 10:03 PM Report #102403 Posted May 23, 2007 at 10:03 PM Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe! 👍 C: http://cr.yp.to/primegen.htmlPython: http://krenzel.info/?p=83 Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!
Triton Posted May 23, 2007 at 10:05 PM Report #102404 Posted May 23, 2007 at 10:05 PM Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe! 👍 C: http://cr.yp.to/primegen.htmlPython: http://krenzel.info/?p=83 Por acaso já tinha visto hoje, fui ao site da Wikipedia e reparei... mas obrigado na mesma. 😉 <3 life
djthyrax Posted May 23, 2007 at 10:06 PM Report #102405 Posted May 23, 2007 at 10:06 PM Se alguém descobrir um exemplo do Crivo de Atkin em funcionamento era fixe! 👍 C: http://cr.yp.to/primegen.htmlPython: http://krenzel.info/?p=83 Por acaso já tinha visto hoje, fui ao site da Wikipedia e reparei... mas obrigado na mesma. 😉 Foi onde eu vi também 😉 Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now