Como descobrir se um numero muito grande é primo com maior agilidade?

Boa noite, fiz um programa para discobrir se um número é primo, porem quando informo um valor muito alto "prico", como ex: [telefone removido] ele demora muito para retornar a resposta, gostaria de saber se tem alguma forma de agilizar este processo. O codigo que fiz é o seguinte:

public class Exercicio1003 {


	public static void main(String[] args) {
		java.util.Scanner scan = new java.util.Scanner(System.in);
		java.io.PrintStream saida = System.out;
		saida.print("Digite SAIR para sair do programa");
		while(true){
			long num = 0;
			try{
				saida.print("\n\nInforme um número Inteiro:");
				String st = scan.nextLine();
				if(st.equalsIgnoreCase("sair"))System.exit(0);
				num = Long.parseLong(st);
				if(num <= 1)throw new IllegalArgumentException("O número deve ser maior que 1!");
			}catch(NumberFormatException nfe){
				saida.print("Erro: Dado Inválido");
				continue;
			}catch(IllegalArgumentException iae){
				saida.print("Erro: " + iae.getMessage());
				continue;
			}
			String resp = "";
			if(num % 2 == 1){
				for(long i = 2; i < num/2; i++){
					if(num % i == 0){
						resp = "NÂO é um número primo";
						break;
					}
					resp = "É um número primo";
				}
			}
			else resp = "NÂO é um número primo";
			if(num == 2)resp = "É um número primo";
			saida.print(resp);
		}
	}		
}

1 Resposta

balrog 29 de mai. de 2010

package com.planetadventure.mashups;

public class TestPrimeNumber {

	public static long input, root;
	public static boolean isPrime;

	public static void main(String[] args) {
		long start = new java.util.Date().getTime();
		
		try {
			input = Long.parseLong("[telefone removido]");
		} catch (NumberFormatException nfx) {
			System.out.println("NAN");
			System.exit(1);
		}

		if (input == ((input >> 1) << 1)) {
			input += 1;
		}
		for (long i = input;; i += 2) {
			root = (long) Math.sqrt(i);
			for (long j = 3; j <= root; j++) {
				if (i == (long) (i / j) * j) {
					isPrime = false;
					break;
				}
				if (j == root) {
					isPrime = true;
				}
			}
			if (isPrime == true) {
				System.out.println(i + " is prime");
				break;
			} else {
				System.out.println(i + " is not prime");
			}
		}
		long end = new java.util.Date().getTime();
		calculateTime((end-start)/1000);
	}
	
	   public static void calculateTime(long timeInSeconds) {
		      long hours, minutes, seconds;
		      hours = timeInSeconds / 3600;
		      timeInSeconds = timeInSeconds - (hours * 3600);
		      minutes = timeInSeconds / 60;
		      timeInSeconds = timeInSeconds - (minutes * 60);
		      seconds = timeInSeconds;
		      System.out.println(hours + " hour(s) " + minutes + " minute(s) " + seconds + " second(s)");
		   }
}

1 Resposta

Topicos relacionados