Informa se inteiro é primo ou ñ

nada

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

Rudy:

Aloha pessoa com estão?
Pessoal estou começando a mexer com progrmação, já tenho algumas noçoes basicas de java (orientada com objetos) tenho que resolver uma pequena questão da facu e ñ estou conseguindo alguem pode me ajudar?

Tenho que solicitar um numero e informa se ele é primo ou ñ. Já li alguns topicos sobre o assunto, mas mesmo assim ñ me ficou muito claro, meu codigo esta assim…

[b] public void Resusltado()

{

if ( numero < 2 || numero > 2 && numero%2==0){

System.out.println (“não é primo”);

}

int cont=2;</blockquote>

primeiramente vc não precisa desse 1º ‘if’, tente refazer o código usando apenas o while. Vc não precisa dividir o valor por todos os seus antecessores. Basta dividir por 1, 2, 3, 4 e 5, pois todos os números não-primo são divisiveis por no minimo 3 desses valores. Ex: 31 é divisivel so por 1, já o 30, é por 1, 2,3 e por 5. 11, so é dividido por 1.

uma dica:

int i = 1;
int cont = 0;
int mod;
        
        while (i <= 5) {
        
               (...)

        }

if (cont <= 2)
            System.out.println("Verificando... " + valor+ " � PRIMO");
else
            System.out.println("Verificando... " +valor+ " N�O � PRIMO");

Eu acho que fica mais facil assim:
Saca soh!! :D

public class IsPrimo {
	public boolean isPrimo(int intNumero1){
		
		boolean isPrimo;
		
		if
		(((intNumero1%2==0)||(intNumero1%3==0)||(intNumero1%5==0)||(intNumero1%7==0))
		&&
		((intNumero1!=2)&&(intNumero1!=3)&&(intNumero1!=5)&&(intNumero1!=7))){
			isPrimo = false;			
		}else{
			isPrimo = true;
		}
		
		return isPrimo;
	}
}

Qqr coisa, posta ai!

:wink:

leobr84:

nada

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

[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]

Allan_BSO:

Eu acho que fica mais facil assim: Saca soh!! :D

public class IsPrimo {
	public boolean isPrimo(int intNumero1){
		
		boolean isPrimo;
		
		if
		(((intNumero1%2==0)||(intNumero1%3==0)||(intNumero1%5==0)||(intNumero1%7==0))
		&&
		((intNumero1!=2)&&(intNumero1!=3)&&(intNumero1!=5)&&(intNumero1!=7))){
			isPrimo = false;			
		}else{
			isPrimo = true;
		}
		
		return isPrimo;
	}
}

Qqr coisa, posta ai!

:wink:

A é?

E 11?
E 13?
E 17?
E.......?????

davidbuzatto:

leobr84:

nada

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

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.

porque intervalo de 1 a n/2? não saquei. Se eu fizer multipilcação com 1,2,3,4, vou gerar qualquer número não primo. Então basta dividir por esses valores, inclusive pelo proprio valor que se deseja verificar. Até pq, para gerar um numero primo atravez de multiplicação, so é possivel quando ele for multipiicado por 1. Logo ele so vai ser dividido por 1 e por ele mesmo.

esta duvidando velho? try to compile :shock:

minha garantia é 100%

deu tudo certo…

a logica eh a seguinte:

• se o numero for divisivel por 2,3,5 ou 7 entaum nao eh primo caso não eh primo.
• se o numero for um dos divisores acimas entaum é primo tbm.

Facil!!!

:!:

E ae léo blz? vlw a atenção.
Pessoa eu acho que fiz o que vc disse, mudei o codigo e ele ficou assim…

[b]    public void Resusltado()

{

int cont=1;

int contt = 0;

while ( cont <= 5 ){
            int mod = numero%cont;
            
            
               if ( mod <=2 ) {
                   System.out.println ("é primo");
                }
                else {
                    System.out.println ("n é primo");
                }
                cont++;
            }
        }[/b]

mas… ñ ta rodando direito ñ…

Allan_BSO:

esta duvidando velho? try to compile :shock:

minha garantia é 100%

deu tudo certo…

a logica eh a seguinte:

• se o numero for divisivel por 2,3,5 ou 7 entaum nao eh primo caso não eh primo.
• se o numero for um dos divisores acimas entaum é primo tbm.

Facil!!!

:!:

A é? Se fosse tão simples assim, acho que muita gente não teria estudado tanto a geração/verificação de números primos.

121 no seu algoritimo é primo, mas na verdade não é, pois é divisível por 11

Allan_BSO:

esta duvidando velho? try to compile :shock:

minha garantia é 100%

deu tudo certo…

[i]a logica eh a seguinte:

• se o numero for divisivel por 2,3,5 ou 7 entaum nao eh primo caso não eh primo.
• se o numero for um dos divisores acimas entaum é primo tbm.
  [/i]
  Facil!!!

:!:

ou…

dividir por 2 primos e pelo proprio valor e dividir por 2 não primos e pelo proprio valor.
Dessas 5 divisões, se o resto da divisão for 0, pelo menos, três vezes o valor não é primo.

davidbuzatto:

Allan_BSO:

esta duvidando velho? try to compile :shock:

minha garantia é 100%

deu tudo certo…

a logica eh a seguinte:

• se o numero for divisivel por 2,3,5 ou 7 entaum nao eh primo caso não eh primo.
• se o numero for um dos divisores acimas entaum é primo tbm.

Facil!!!

:!:

A é? Se fosse tão simples assim, acho que muita gente não teria estudado tanto a geração/verificação de números primos.

121 no seu algoritimo é primo, mas na verdade não é, pois é divisível por 11 :D

ishi!!! Pode crer, corretissimo davidbuzatto!!

O CERTO É DIVIDIR POR 1 até n/2

Tinha feito esse código há umas semanas, e não tinha enxergado esse teu detalhe!!

falei merda. mal ae hahahaha vlw

Testa o 121 ai então

Acontece

[]´s

<blockquote><div class="quote-author">Rudy:</div>Pessoas o numero é primo quando o resultado de sua divisão é menor que seu divisor e seu resto diferente de zero, se eu ñ estiver errado alguem me diz o que tem de erra nessa condição.



if ( numero/cont<cont && numero%cont!=0){

System.out.println (“é primo”);

}

else {

System.out.println (“n é primo”);

}</blockquote>

Teste o algorítmo que eu falei.

É de 1 até n/2 pq se até na metade do intervalo vc não encontrar 2 ou mais divisores, na outra metade você não vai encontrar.

Pessoas acho que agora deu certo, o código ficou assim…

public void Resusltado()

{

if (numero < 2){

System.out.println (“n é primo”);

}

int cont=1;

int conta=1;

while ( cont < numero ){

if ( numero%cont == 0 ){

conta++;

}

if ( conta > 2) {

System.out.println (“n é primo”);

}

else {

System.out.println (“é primo”);

}

cont++;

}

}

testei com os numeros 1, 2, 3, 4, 5, 9, 21 e pelo menos com esse numeros o resultado foi o esperado.
Se alguem poder da uma olhada para mim e me dizer se tem algum erro que eu ñ esteja vendo, eu agradeço vlw pessoas.

Quer um código mais performático?

Olha esse aqui que eu fiz :D

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;
    
}

Testa o 121 ai então :D

Vc esta certo…
Errei admito!!!

mas se eu acrescentar o 11 na minha lógica acima, acredito que o problema será resolvido.

certo?

Ah, outra coisa, a classe BigInteger tem alguns métodos que trabalham com números primos. O método isProbablePrime de BigInteger retorna se o número passado é provavelmente um primo.

davidbuzatto:

Quer um código mais performático?

Olha esse aqui que eu fiz :D

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;
    
}

muito bom david, vlw a ajuda cara. Cada dia que passa a lógica vai me parecendo mais simples :D

Testa o 121 ai então :D

Vc esta certo…
Errei admito!!!

mas se eu acrescentar o 11 na minha lógica acima, acredito que o problema será resolvido.

certo?

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.

Kra agora eu saquei a mancada da minha lógica… podes cre velho!!!
tem que testar de 1 ate a n/2. vc esta certo…
vou reformular o código!!!

valeu!!!

davidbuzatto:

Quer um código mais performático?

Olha esse aqui que eu fiz :D

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;
    
}

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.

agora sim...
valeu velho pelo toque...
as vezes tem que admitir o erro!!! e tentar arrumar...

saca soh:

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;
		
	}
}

funcionou!!! 11, 121, 169, 1849...

Pode-se também usar o crivo de Eratóstenes tbm para gerar números primos.

Rudy:

davidbuzatto:

Quer um código mais performático?

Olha esse aqui que eu fiz :D

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;
    
}

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.

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.

Allan_BSO:

agora sim... valeu velho pelo toque... as vezes tem que admitir o erro!!! e tentar arrumar...

saca soh:

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;
		
	}
}

funcionou!!! 11, 121, 169, 1849...

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.

Rudy, dá uma olhada aqui

Vlw David.

Divida pelos primos encontrados no intervalo de 2 até a raiz quadrada de N. É bem mais rápido.

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 ).

Até!

davidbuzatto:

leobr84:

nada

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

[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]

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.

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.

Até!