判断一个数是否是素数（质数）

素数（质数）定义

小学数学。。。这里复习一下。。。

• 素数又称质数，一个大于1的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
• 0 和 1 既不是质数也不是合数，最小的质数是 2

代码实现

一、最暴力的实现：

这里直接根据定义来判断一个数是否是素数

    public boolean isPrime(int num) {
		if (num <= 3) return num > 1;//0 和 1 既不是素数也不是合数，2是最小的素数
		
		for(int i = 2; i < num; i++) {
			if (num % i == 0) return false;
		}
		
		return true;
	}

二、优化版本：

简单的思考一下，假如 num 是合数，那么必然存在非 1 的两个约数 num1 和 num2，其中 num1 <= sqrt(n)，num2 >= sqrt(n) 。由此我们可以改进上述方法优化循环次数。如下：

    public boolean isPrime(int num) {
		if (num <= 3) return num > 1;//0 和 1 既不是素数也不是合数，2是最小的素数
		
		int sqrt = (int) Math.sqrt(num);
		for(int i = 2; i <= sqrt; i++) {
			if (num % i == 0) return false;
		}
		
		return true;
	}