# 计算质数（204）

# 题目

# 算法

# 优化的暴力法

暴力法是我们每判断一个数字是不是质数，都从2到数字-1整除一遍看看是否有余数，但是这个过程中我们无需全部整除：

除了2以外其他质数全是奇数
我们只需要整除到x的平方根，如果从2到x的平方根都不能整除，那么x一定是质数

根据以上两项我们就可以优化暴力法，有几点需要注意：

默认res为1，因为我们从3开始判断，跳过了2。3只判断奇数即可，所以每次+2
对每一个数字判断的时候，我们除法运算从3开始而不是2，因为我们只判断奇数，一定不能被2整除；同样，除数我们也每次+2

export const countPrimes = (n) => {
	if (n < 3) return 0;
	let res = 1;
	for (let i = 3; i < n; i += 2) {
		let flag = true;
		for (let j = 3; j * j <= i; j += 2) {
			if (i % j === 0) {
				flag = false;
				break;
			}
		}
		if (flag) res++;
	}
	return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 埃拉托斯特尼筛法（埃氏筛）

每次判断下一个数字时，我们都将该数字的整数倍数字全部标记为“合数”：

先声明一个长度为n的数组，用来标记是不是质数，默认都填充true
我们从2开始向后依次寻找值为true的方格（即这个位置的索引值为质数，即isPrimes[2]表示数字2而不是第3个索引位置）
如果这个数字i的值是true，那么我们将res++，并且将其的整数倍数字全部标记为false，这样以后遍历到这些数字的时候就知道他是合数

埃拉托斯特尼筛法 - 百度百科 (opens new window)

export const countPrimes = (n) => {
	const isPrimes = new Array(n).fill(true);
	let res = 0;
	for (let i = 2; i < n; i++) {
		if (isPrimes[i]) {
			res++;
			for (let j = i + i; j < n; j += i) {
				isPrimes[j] = false;
			}
		}
	}
	return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13

← x的平方根（69） Pow(x, n)（50） →