js 判断一个数是否为质数

这几天遇到几个低级算法题，就想试试写一个判断一个数是不是质数的。

## 质数是什么？
又称素数，大于1并且只能被自身和1整除的自然数。

## 思路
其实很简单，做一个循环整除就行了。

先来看看百度到的方法：[https://blog.csdn.net/qq_40190624/article/details/108421691](https://blog.csdn.net/qq_40190624/article/details/108421691)

```ts
function isPrime(n: number) {
	// 为2是因为质数为2,而且质数不能为1和自身不能被其他自然数整除的数叫做质数;
	for (let i = 2; i < n; i++) {
		if (n % i === 0) {
			return false //质数
		}
	}
	return true //非质数
}
```

这个经过验证，确实可以简单判断是否为质数，不过小于等于1的数并没有做检测，这个先不管。

然后我就在想，既然是质数，那首先就应该排除偶数（偶数能被2整除），然后被除数也不会超过数的一半（最大无外乎 2x），所以得到了下面这串代码：

```ts
function isPrimeNum(num: number) {
	// 小于等于1为非质数
	if (num <= 1) return false;
	// 2能被2整除，所以先特殊处理，直接返回 true
	if (num === 2) return true;
	// 先把小数排除掉
	if (num % 1 !== 0) return false;
	// 排除偶数
	if (num % 2 === 0) return false;
	// 因为 num 最大也只能是 2 倍 x，所以 / 2 向下取整就行
	let halfNum = Math.floor(num / 2);
	// 直接从3开始算
	for (let i = 3; i <= halfNum; i++) {
		if (num % i === 0) return false; // 能被整除，非质数
	}
	return true; // 质数
}
```

我们和之前那个方法做一个性能测试，列出 `1000000` 以内的所有质数（打印内容过多，就不做截图了，直接给结果）。第一种方法耗时 `98383 毫秒`，修改之后耗时 `49932 毫秒`，可以看到 **几乎少了一半的时间**。

然后和同事讨论了一下，又有了一个新方案：最大数不是一半，而是开次方根之后的数。修改修改，就变成了以下样子：

```ts
function isPrime(num: number) {
	// 小于等于1为非质数
	if (num <= 1) return false;
	// 2能被2整除，所以先特殊处理，直接返回 true
	if (num === 2) return true;
	// 先把小数排除掉
	if (num % 1 !== 0) return false;
	// 排除偶数
	if (num % 2 === 0) return false;
	// 开根号
	let halfNum = Math.sqrt(num);
	// 开根号之后如果直接是整数，那证明不是质数，直接返回
	if (halfNum % 1 === 0) return false;
	// 依然向下取整
	halfNum = Math.floor(halfNum);
	// 直接从3开始算
	for (let i = 3; i <= halfNum; i++) {
		if (num % i === 0) return false; // 能被整除，非质数
	}
	return true; // 质数
}
```

经过测试，结果依然是对的。好的，我们再来做一次性能测试。这次的耗时仅用时 `187 毫秒`，几乎只是第一次的 **1/490**，第二次的 **1/250**。

等等，既然不能是偶数，那么也不需要每个数都去算了。改一改就变成了：

```ts
function isPrime(num: number) {
	// 小于等于1为非质数
	if (num <= 1) return false;
	// 2能被2整除，所以先特殊处理，直接返回 true
	if (num === 2) return true;
	// 先把小数排除掉
	if (num % 1 !== 0) return false;
	// 排除偶数
	if (num % 2 === 0) return false;
	// 开根号
	let halfNum = Math.sqrt(num);
	// 开根号之后如果直接是整数，那证明不是质数，直接返回
	if (halfNum % 1 === 0) return false;
	// 依然向下取整
	halfNum = Math.floor(halfNum);
	// 直接从3开始算，过滤掉偶数，所以直接+2，能被偶数整除也能被2整除
	for (let i = 3; i <= halfNum; i = i+2) {
		if (num % i === 0) return false; // 能被整除，非质数
	}
	return true; // 质数
}
```

测试结果一致，看看性能，`97毫秒` ！！！仅仅是之前最快速的 **一半**！！！

到这里基本上就告一段落了，应该会有更高效快速的方法，只是还没想到。

添加新评论

最近回复

标签

链接

其它