如何用Java判断任意一个数是否为素数

一. 知识点

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为质数。
1不是素数

二. 代码实现

方法一

package tv.zhangjia.algorithms;

public class Test {
	public boolean isPrime(int n) {
		if(n < 2) {
			return false;
		}
		for(int i = 2; i * i <= n; i++) {
			if(n % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) {
		for(int i = 2; i <= 10; i++) {
			System.out.println(i + "是素数吗：" + new Test().isPrime(i));
		}
	}
	
}
/*输出：
2是素数吗：true
3是素数吗：true
4是素数吗：false
5是素数吗：true
6是素数吗：false
7是素数吗：true
8是素数吗：false
9是素数吗：false
10是素数吗：false*/

方法二

package tv.zhangjia.algorithms;

public class Test {
	public boolean isPrime(int n) {
		if (n < 2) {
			return false;
		}
		for (int i = 2; i < n; i++) {
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		System.out.println("97" + new Test().isPrime(97));
		System.out.println("for循环执行了：" + j + "次");
	}

}
/*输出：
2是素数吗：true
3是素数吗：true
4是素数吗：false
5是素数吗：true
6是素数吗：false
7是素数吗：true
8是素数吗：false
9是素数吗：false
10是素数吗：false*/

三. 两个方法比较

虽然两个方法的结果是相同的，但是效率却极大的不同，我们可以通过查看for循环的执行次数，来比较两个方法的效率，这里我们以100以内的最大的素数97为例

首先看方法二：

//方法二：
package tv.zhangjia.algorithms;

public class Test {
	static int j = 0;

	public boolean isPrime(int n) {
		if (n < 2) {
			return false;
		}
		for (int i = 2; i < n; i++) {
			j++;
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		System.out.println("97是素数吗：" + new Test().isPrime(97));
		System.out.println("for循环执行了：" + j + "次");
	}

}

/*97是素数吗：true
for循环执行了：95次*/

再看方法一：

package tv.zhangjia.algorithms;

public class Test {
	static int j = 0;

	public boolean isPrime(int n) {
		if (n < 2) {
			return false;
		}
		for (int i = 2; i * i <= n; i++) {
			j++;
			if (n % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		System.out.println("97是素数吗：" + new Test().isPrime(97));
		System.out.println("for循环执行了：" + j + "次");
	}

}

/*97是素数吗：true
for循环执行了：8次*/

通过上面两个方法的比较我们可以看出，虽然两个方法的输出结果一致，但是方法一的效率是方法二的近十倍之高

四. 简单扩展

关于方法一，还是以97为例，i = 2开始，一直到i = 10的时候，退出for循环。为什么不用判断11 -95这些数字呢？因为97除以10以后的任何数数字，都不是整数，就算我们假设这个结果是整数，也肯定比10小，然而比10小的数字，我们已经判断过了
关于方法一，其实只要把for循环中的i++改成i += 2，效率又会提示2倍，因为除了2以外，其他所有的偶数都不是素数，所以可以直接用i += 2来排除偶数