[quote=davidbuzatto]Quer um código mais performático?
Olha esse aqui que eu fiz
[code]public boolean ehPrimo( int n ) {
int c = 0;
// é menor que 2? não é primo
if ( n < 2 )
return false;
// itera de 1 até n / 2
for ( int i = 1; i < n / 2; i++ )
if ( n % i == 0 ) // n é divisível por i?
if ( ++c > 1 ) // se sim, incrementa c. se c incrementado for maior que 1, não é primo
return false;
// ufa... é primo
return true;
}[/code][/quote]
muito bom david, vlw a ajuda cara. Cada dia que passa a lógica vai me parecendo mais simples
mas se eu acrescentar o 11 na minha lógica acima, acredito que o problema será resolvido.
certo?[/quote]
Não. Os números primos são infinitos, você não pode inferir que usar os primeiros primos para verificar a divisibilidade vai retornar se um número é primo ou não. Veja o código que postei ou então dê uma olhada na implementação dos métodos relacionados a números primos da classe BigInteger. Os métodos da BigInteger trabalham com a “probabilidade” de um número ser primo. Já aviso que a implementação na classe BigInteger não é algo muito simples
Quer mais um exemplo? 1849 não é primo e passaria pelo seu algorítmo, mesmo inserindo o teste para o 11.
[quote=davidbuzatto]Quer um código mais performático?
Olha esse aqui que eu fiz
[code]public boolean ehPrimo( int n ) {
int c = 0;
// é menor que 2? não é primo
if ( n < 2 )
return false;
// itera de 1 até n / 2
for ( int i = 1; i < n / 2; i++ )
if ( n % i == 0 ) // n é divisível por i?
if ( ++c > 1 ) // se sim, incrementa c. se c incrementado for maior que 1, não é primo
return false;
// ufa... é primo
return true;
}[/code][/quote]
Só mais uma pergunta boba :D.
que programa vc usa para compilar o codigo, eu to vendo que vc postou ai e ta numerada as linhas, eu uso o blueJ, mas ñ gosto muito.
[quote=Rudy][quote=davidbuzatto]Quer um código mais performático?
Olha esse aqui que eu fiz
[code]public boolean ehPrimo( int n ) {
int c = 0;
// é menor que 2? não é primo
if ( n < 2 )
return false;
// itera de 1 até n / 2
for ( int i = 1; i < n / 2; i++ )
if ( n % i == 0 ) // n é divisível por i?
if ( ++c > 1 ) // se sim, incrementa c. se c incrementado for maior que 1, não é primo
return false;
// ufa... é primo
return true;
}[/code][/quote]
Só mais uma pergunta boba :D.
que programa vc usa para compilar o codigo, eu to vendo que vc postou ai e ta numerada as linhas, eu uso o blueJ, mas ñ gosto muito.[/quote]
Essa numeração é colocada automaticamente quando vc posta algum trecho de código fonte e insere as tags [code ] aqui do fórum. Dá uma olhada na barrinha acima da caixa de texto quando vc vai postar algo.
[quote=Allan_BSO]agora sim…
valeu velho pelo toque…
as vezes tem que admitir o erro!!! e tentar arrumar…
saca soh:
[code]
public class IsPrimo {
public boolean isPrimo(int intNumero){
boolean isPrimo;
int totalDeDivisores=0;
for(int i=1; i<=(intNumero/2);i++){
if(intNumero%i==0){
totalDeDivisores++;
}
}
if (totalDeDivisores>1){
isPrimo=false;
}else{
isPrimo=true;
}
return isPrimo;
}
}[/code]
funcionou!!! 11, 121, 169, 1849…
[/quote]
Vc percebe onde seu código pode se tornar mais rápido? Olha no for. Vc concorda que, quando vc encontrar mais de um divisor, vc não precisa continuar o for? No seu código vc vai de 1 até n/2. Você ainda pode fazer ele parar quando achar mais de 1 divisor, ou seja, não precisa continuar fazendo testes desnecessários. Olha o código que eu postei.
Se isso for um programa exato para teste de primalidade, os testes são computacionalmente difíceis, então para números muito grandes pode ser que os métodos de teste primo-a-primo e o Crivo de Eratóstenes sejam pouco eficientes. Tem algoritmos que testam deterministicamente ( procure por teste de primalidade AKS ) e outros que testam probabilisticamente ( esse tem vários ). Se a sua necessidade for de descobrir se o número não é primo e com uma boa margem de acerto ( não é 100%, mas se testado várias vezes pode ser mais rápido do que descobrir deterministicamente ), podes tentar o teste de Fermat ( o PGP usa ).
Crie uma variavel para acumular valores concatenados (cont = 0). Faça a divisão do valor o qual vc quer verificar se é primo por 1 até 5. Colocando o resto da divisaão em uma variavel, verifique se o resto da divisao é == 0. Se for igual a zero o numero foi dividido por x sem deixar resto, então cont recebe +1 (cont = cont+1). Quando acabar as divisões, se cont <= 2 o Número é Primo. Senão o Número não é Primo.
vlw[/quote]
[color=red]Cuidado… Para ter uma “garantia” que um número é primo vc precisa dividir ele pelos números no intervalo de [1,n/2]. Se nesse intervalo houverem mais de dois divisores o número não é primo.[/color]
EDITADO:
[color=blue]Cuidado… Para ter uma “garantia” que um número é primo vc precisa dividir ele pelos números no intervalo de [1,n/2]. Se nesse intervalo houver mais de 1 divisor o número não é primo.[/color][/quote]
eu tenho impressao que voce soh precisa dividir do intervalo [2, sqrt(n)] … ou estou errado?
Voce esta correto, para verificar se um numero é primo deve-se verficar se algum numero menor que a raiz quadrada do numero em questão o dividi, mas preste muita atenção, tem que testar todos os numeros.
Só para esclarecimento, até hoje não existe uma generalização dos numeros primos, ou seja até hoje não existe uma formula para gerar numeros primos consequentemente não existe uma formula para descobrir se o mesmo é primo ou não, por isso a verificação de todos os numeros até a raiz quadrada.
Voce esta correto, para verificar se um numero é primo deve-se verficar se algum numero menor que a raiz quadrada do numero em questão o dividi, mas preste muita atenção, tem que testar todos os numeros.
Só para esclarecimento, até hoje não existe uma generalização dos numeros primos, ou seja até hoje não existe uma formula para gerar numeros primos consequentemente não existe uma formula para descobrir se o mesmo é primo ou não, por isso a verificação de todos os numeros até a raiz quadrada.
[/quote]
Estás parcialmente correto. Não existe uma fórmula de primos que ou garanta que todos os gerados são primos ou que percorra todos os primos, mas há fórmulas que fazem primos ou prováveis primos com uma boa margem. Há sim métodos determinísticos que resolvem em tempo polinomial o teste de primalidade e que não precisam percorrer todos os primos abaixo da raiz do número. Digo que dá para verificar se é primo ou não, e não que é possível saber quais são os fatores deles ( que é um problema que acreditam ser NP ). Caso seja preciso um método mais rápido do que um método determinístico ( que é algo perto de ( log n )^4ou5 ), pode ser usado algum método probabilístico que já mostrei que não são tão inúteis assim. Caso haja alguma dúvida, sugiro a leitura de http://en.wikipedia.org/wiki/Primality_test, http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving, http://en.wikipedia.org/wiki/AKS_primality_test e http://en.wikipedia.org/wiki/Fermat_primality_test.
