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

Programação Java
#1

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

[code]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);
	}
}

}
[/code]

#2

[code]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("2147483647");
	} 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)");
	   }

}
[/code]

#3