素数問題高速判定アルゴリズム


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 *       ,       。   1-100     ,
 *   1-10      [2,3,5,7],
 *   11-100  %[2,3,5,7],          
 */
public class Prime {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("           (   a b):");
		while (true) {
			long n1 = sc.nextLong();
			long n2 = sc.nextLong();
			List<Long> primeList = getPrime(n1, n2);
			for (Long prime : primeList) {
				System.out.print(prime + " ");
			}
			System.out.println();
		}
	}

	public static List<Long> getPrime(long begin, long end) {
		List<Long> result = new ArrayList<Long>();// result    begin-end       
		List<Long> tempPrime = new ArrayList<Long>();//   2-Math.sqrt(end)       
		for (long i = 2; i <= Math.sqrt(end); i++) {
			if (isPrime(i)) {
				tempPrime.add(i);
				// System.out.print(i + " ");
			}
		}
		// System.out.println();
		for (long prime : tempPrime) {
			if (prime >= begin) {
				result.add(prime);
			}
		}

		long start = (long) Math.sqrt(end);
		if (start > begin) {
			begin = start;
		}
		for (long i = begin; i <= end; i++) {
			boolean flag = true;
			for (long prime : tempPrime) {
				if (i % prime == 0) {
					flag = false;
					break;
				}
			}
			if (flag) {
				result.add(i);
			}
		}
		return result;
	}

	/**
	 *             
	 */
	public static boolean isPrime(long n) {
		for (long i = 2; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				return false;
			}
		}
		if (n <= 1L) {
			return false;
		}
		return true;
	}
}