Fazendo programa para achar números primos

19 de abril de 2017 7 respostas

Renan_Cesar 19 de abril de 2017

Olá a todos da comunidade, estou cursando Sistemas de informação 2 período e um professor passou uma atividade em Java para se achar números primos.
Quebrei a cabeça para fazer, tinha dado alguns erros ai fui procurar a solução an net. Mas vi que os cara usavam uma solução muito grande com uns códigos que ninquém entendi. Ai fiz de uma forma que não vi até agora em lugar algum e estou postando aqui, espero ajudar quem precise.

public static void main(String[] args) {
        int op, contadorPrimo=0, contadorDig=0;    //Variaveis   
        do{    //Inicio DO-WHILE para controlar quando deseja parar o programa;
            op=Integer.parseInt(JOptionPane.showInputDialog("Numeros digitados: "+contadorDig+"\nNumeros primos digitados: "+contadorPrimo+"\nEntre com número:"));
            contadorDig++; // CONTADOR de quantos números foram digitados;
            ai=op;
            if(op%3!=0 && op%2==1 ||op==2 || op==3){    // Inicio IF para adicionar contador de PRIMOS;
                contadorPrimo++;
            } //Fim IF adionar contador de PRIMOS
        }while(op!=0); //Fim DO-WHILE para programa fechar quando digitar 0;
    }
}

7 Respostas

staroski 19 de abr. de 2017 2 likes

Essa implementação está equivocada.
Você está considerando como primo todos os números divisíveis por 3 e não divisíveis por 2.

Existem várias técnicas de otimizar o algoritmo para verificar se um número é primo, a mais comum é contar os divisores até chegar a raíz quadrada do número testado.

Abaixo tem uma implementação otimizada que certa vez eu submeti no URI Online Judge

private static boolean isPrime(int n) {
	if (n < 2) {
		return false;
	}
	if (n < 4) {
		return true;
	}
	if (n % 2 == 0 || n % 3 == 0) {
		return false;
	}
	for (int i = 5; i * i <= n; i += 6) {
		if (n % i == 0) {
			return false;
		}
		if (n % (i + 2) == 0) {
			return false;
		}
	}
	return true;
}

Renan_Cesar 19 de abr. de 2017

Não entendi amigo, pelo que sei de primo usando essa sintaxa dentro do IF funciona perfeitamente. Já testei com várias cadeias de números primso sem erro algum. E o exemplo que tu mandou no site está errado, pois, 3 é primo e 123 não é. Gostaria que em explicasse melhor.

rmendes08 19 de abr. de 2017 1 like

Colega, está errado o seu código. Pelo seu código, qualquer número não-primo que não tenha fator 2 ou 3 vai ser contabilizado como número primo, exemplo: 35, 55, 77, etc.

staroski 20 de abr. de 2017 1 like

Ué, mas o meu algoritmo diz exatamente isso: que 3 é primo e 123 não é.
Tem certeza de que executou o código corretamente?
Execute o exemplo abaixo:

public class ExercicioPrimos {

	public static void main(String[] args) {
		ExercicioPrimos programa = new ExercicioPrimos();
		programa.executar();
	}

	private void executar() {
		for (int numero = 0; numero < 150; numero++) {
			String respostaStaroski = algoritmo_do_staroski(numero) // algoritmo do staroski diz que é primo?
					? "staroski"                                    // então apresenta nome do staroski
					: "        ";                                   // senão apresenta vazio
			
			String respostaRenan    = algoritmo_do_renan(numero)    // algoritmo do renan diz que é primo?
					? "renan"                                       // então apresenta nome do renan
					: "     ";                                      // senão apresenta vazio

			// apresenta resultado
			System.out.printf("quem diz que %03d é primo?    %s    %s\n", numero, respostaStaroski, respostaRenan);
		}
	}

	private static boolean algoritmo_do_renan(int op) {
		if (op % 3 != 0 && op % 2 == 1 || op == 2 || op == 3) {
			return true;
		}
		return false;
	}

	private static boolean algoritmo_do_staroski(int n) {
		if (n < 2) {
			return false;
		}
		if (n < 4) {
			return true;
		}
		if (n % 2 == 0 || n % 3 == 0) {
			return false;
		}
		for (int i = 5; i * i <= n; i += 6) {
			if (n % i == 0) {
				return false;
			}
			if (n % (i + 2) == 0) {
				return false;
			}
		}
		return true;
	}
}

E irá obter a seguinte saída:

quem diz que 000 é primo?                     
quem diz que 001 é primo?                renan
quem diz que 002 é primo?    staroski    renan
quem diz que 003 é primo?    staroski    renan
quem diz que 004 é primo?                     
quem diz que 005 é primo?    staroski    renan
quem diz que 006 é primo?                     
quem diz que 007 é primo?    staroski    renan
quem diz que 008 é primo?                     
quem diz que 009 é primo?                     
quem diz que 010 é primo?                     
quem diz que 011 é primo?    staroski    renan
quem diz que 012 é primo?                     
quem diz que 013 é primo?    staroski    renan
quem diz que 014 é primo?                     
quem diz que 015 é primo?                     
quem diz que 016 é primo?                     
quem diz que 017 é primo?    staroski    renan
quem diz que 018 é primo?                     
quem diz que 019 é primo?    staroski    renan
quem diz que 020 é primo?                     
quem diz que 021 é primo?                     
quem diz que 022 é primo?                     
quem diz que 023 é primo?    staroski    renan
quem diz que 024 é primo?                     
quem diz que 025 é primo?                renan
quem diz que 026 é primo?                     
quem diz que 027 é primo?                     
quem diz que 028 é primo?                     
quem diz que 029 é primo?    staroski    renan
quem diz que 030 é primo?                     
quem diz que 031 é primo?    staroski    renan
quem diz que 032 é primo?                     
quem diz que 033 é primo?                     
quem diz que 034 é primo?                     
quem diz que 035 é primo?                renan
quem diz que 036 é primo?                     
quem diz que 037 é primo?    staroski    renan
quem diz que 038 é primo?                     
quem diz que 039 é primo?                     
quem diz que 040 é primo?                     
quem diz que 041 é primo?    staroski    renan
quem diz que 042 é primo?                     
quem diz que 043 é primo?    staroski    renan
quem diz que 044 é primo?                     
quem diz que 045 é primo?                     
quem diz que 046 é primo?                     
quem diz que 047 é primo?    staroski    renan
quem diz que 048 é primo?                     
quem diz que 049 é primo?                renan
quem diz que 050 é primo?                     
quem diz que 051 é primo?                     
quem diz que 052 é primo?                     
quem diz que 053 é primo?    staroski    renan
quem diz que 054 é primo?                     
quem diz que 055 é primo?                renan
quem diz que 056 é primo?                     
quem diz que 057 é primo?                     
quem diz que 058 é primo?                     
quem diz que 059 é primo?    staroski    renan
quem diz que 060 é primo?                     
quem diz que 061 é primo?    staroski    renan
quem diz que 062 é primo?                     
quem diz que 063 é primo?                     
quem diz que 064 é primo?                     
quem diz que 065 é primo?                renan
quem diz que 066 é primo?                     
quem diz que 067 é primo?    staroski    renan
quem diz que 068 é primo?                     
quem diz que 069 é primo?                     
quem diz que 070 é primo?                     
quem diz que 071 é primo?    staroski    renan
quem diz que 072 é primo?                     
quem diz que 073 é primo?    staroski    renan
quem diz que 074 é primo?                     
quem diz que 075 é primo?                     
quem diz que 076 é primo?                     
quem diz que 077 é primo?                renan
quem diz que 078 é primo?                     
quem diz que 079 é primo?    staroski    renan
quem diz que 080 é primo?                     
quem diz que 081 é primo?                     
quem diz que 082 é primo?                     
quem diz que 083 é primo?    staroski    renan
quem diz que 084 é primo?                     
quem diz que 085 é primo?                renan
quem diz que 086 é primo?                     
quem diz que 087 é primo?                     
quem diz que 088 é primo?                     
quem diz que 089 é primo?    staroski    renan
quem diz que 090 é primo?                     
quem diz que 091 é primo?                renan
quem diz que 092 é primo?                     
quem diz que 093 é primo?                     
quem diz que 094 é primo?                     
quem diz que 095 é primo?                renan
quem diz que 096 é primo?                     
quem diz que 097 é primo?    staroski    renan
quem diz que 098 é primo?                     
quem diz que 099 é primo?                     
quem diz que 100 é primo?                     
quem diz que 101 é primo?    staroski    renan
quem diz que 102 é primo?                     
quem diz que 103 é primo?    staroski    renan
quem diz que 104 é primo?                     
quem diz que 105 é primo?                     
quem diz que 106 é primo?                     
quem diz que 107 é primo?    staroski    renan
quem diz que 108 é primo?                     
quem diz que 109 é primo?    staroski    renan
quem diz que 110 é primo?                     
quem diz que 111 é primo?                     
quem diz que 112 é primo?                     
quem diz que 113 é primo?    staroski    renan
quem diz que 114 é primo?                     
quem diz que 115 é primo?                renan
quem diz que 116 é primo?                     
quem diz que 117 é primo?                     
quem diz que 118 é primo?                     
quem diz que 119 é primo?                renan
quem diz que 120 é primo?                     
quem diz que 121 é primo?                renan
quem diz que 122 é primo?                     
quem diz que 123 é primo?                     
quem diz que 124 é primo?                     
quem diz que 125 é primo?                renan
quem diz que 126 é primo?                     
quem diz que 127 é primo?    staroski    renan
quem diz que 128 é primo?                     
quem diz que 129 é primo?                     
quem diz que 130 é primo?                     
quem diz que 131 é primo?    staroski    renan
quem diz que 132 é primo?                     
quem diz que 133 é primo?                renan
quem diz que 134 é primo?                     
quem diz que 135 é primo?                     
quem diz que 136 é primo?                     
quem diz que 137 é primo?    staroski    renan
quem diz que 138 é primo?                     
quem diz que 139 é primo?    staroski    renan
quem diz que 140 é primo?                     
quem diz que 141 é primo?                     
quem diz que 142 é primo?                     
quem diz que 143 é primo?                renan
quem diz que 144 é primo?                     
quem diz que 145 é primo?                renan
quem diz que 146 é primo?                     
quem diz que 147 é primo?                     
quem diz que 148 é primo?                     
quem diz que 149 é primo?    staroski    renan

Silvio_Dasilvamartin 20 de abr. de 2017

Renan Cesar esse problema parece ser dificil mas é só pensar um pouco.
O que é um número primo? um número para ser considerado primo só pode ser divisivel pelo número 1 ou por ele mesmo certo? Então nesse caso ele só tem dois divisores correto? cria uma variável divisores e faça um laço for e compare se o resto do numero pesquisado pela flag é igual 0 se for incremente a variável divisor.

BEGIN

VAR numero;

VAR divisores;

Imprima(“Informe o  número para verificar se é primo”);

leia(numero);

para(i = 1; i menor ou igual numero; i passo !){

se(numero mod i igual 0) então

divisores -> divisores passo 1;

}

if(divisores igual 2) então

escreva("O número é primo)

senão

escreva(“O número não é primo”)

END

giu_d 26 de mai. de 2017

Para saber se um número é primo ou não:

import java.util.Scanner;

public class NumeroPrimo {

public static void main(String[] args) {
	
	
    
    Scanner entrada = new Scanner(System.in);
    
	
	System.out.print("Digite um número: ");
	int m = entrada.nextInt();
	
	boolean ePrimo = true;
	
	
	for(int i = 2; i <= m - 1; i++){
		if (m % i == 0) 
			ePrimo = false;
	}
    
	if (ePrimo == true) { 
		System.out.println("O número " + m + " é primo");
           } else {
    	       System.out.println("O número " + m + " não é primo");
    	
    

	}

}

}

anon62916717 4 de jun. de 2017

Se jogar 25 na entrada, vai ver uma falha (contraprova) no objetivo.
Se sua codificação fosse o que alega, valeria alguns milhões de reais, seria ótimo, pois imagine a aclamação, não pelo prêmio, mas pela descoberta dos milênios.
Há matemáticos que dedicam sua vida a esta descoberta, tadinho de Carl Friedrich Gauss.

Além disso, @staroski está correto, uma das formas de otimizar a contagem é quebrando o laço da operação quando o quadrado do divisor impar incrementado de dois em dois for >= ao dividendo.
Só adicionei uma linha dentro do if, apenas para acompanhar os resultados em tempo real, ele não alterou a lógica da sua codificação.

int op, contadorPrimo=0, contadorDig=0;    //Variaveis   
        do{    //Inicio DO-WHILE para controlar quando deseja parar o programa;
            op=Integer.parseInt(JOptionPane.showInputDialog("Numeros digitados: "+contadorDig+"\nNumeros primos digitados: "+contadorPrimo+"\nEntre com número:"));
            contadorDig++; // CONTADOR de quantos números foram digitados;
            ai=op;//
            if(op%3!=0 && op%2==1 ||op==2 || op==3){    // Inicio IF para adicionar contador de PRIMOS;
                contadorPrimo++;
                JOptionPane.showMessageDialog(null, op+" is not a \"Optmus Prime\" number");//só adicionei a verificação 
            } //Fim IF adionar contador de PRIMOS
        }while(op!=0); //Fim DO-WHILE para programa fechar quando digitar 0;
    }

Criado 19 de abril de 2017

Ultima resposta 4 de jun. de 2017

Respostas 7

Participantes 6

7 Respostas

Topicos relacionados