素数判定

0 1
0 0

OK

分析：

1、0 和 1 既不是素数也不是合数，2 是素数

2、大于 2 的数，能被 2 整除的不是素数

3、素数有一个定理：如果 n 不是素数，则 n 有满足 1 < d <= sqrt(n) 的一个因子 d

4、根据以上三条，设计出来的素数算法时间复杂度是 ( sqrt(n) / 2 )，较常规素数算法效率更高些

import java.util.Scanner;

public class Main {
	// 素数判定，时间复杂度(sqrt(n)/2)
	static boolean isPrime(int num) {
		if (num < 2) {
			return false;
		}
		if (num == 2) {
			return true;
		}
		if (num % 2 == 0) {
			return false;
		}
		for (int i = 3; i < Math.sqrt(num); i += 2) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		int x, y;
		while (scanner.hasNext()) {
			x = scanner.nextInt();
			y = scanner.nextInt();

			if (x == 0 && y == 0) {
				return;
			}

			boolean flag = true;
			for (; x <= y; x++) {
				if (!isPrime(x * x + x + 41)) {
					flag = false;
				}
			}

			if (flag) {
				System.out.println("OK");
			} else {
				System.out.println("Sorry");
			}
		}
	}
}

[hdu 2012] 素数判定,布布扣,bubuko.com

[hdu 2012] 素数判定

原文：http://blog.csdn.net/u011506951/article/details/23020283