0%

素数判定和筛选算法

介绍素数的判定以及筛选算法

I 素数判定算法

枚举判定

对于正整数n,枚举2~n-1以判定n是否为指数
时间复杂度为O(n);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool check(int x) {
if (x == 1) return false;
if (x == 2) return true;
for (int i = 2; i < x; ++ i) {
if (x % i == 0) return false;
}
return true;
}
```
## 优化枚举判定
不难发现,正整数的n总是成对出现的。对于n的判定,只要枚举到\sqrt n就可以了
时间复杂度为O(\sqrtn);
```cpp
bool check(int x) {
if (x == 1) return false;
if (x == 2) return true;
for (int i = 2; i * i < x; ++ i) {
// for (int i = 2; i < sqrt(x); ++ i) { 这样写也是正确的
if (x % i == 0) return false;
}
return true;
}

再优化枚举判定[1]

令$$x≥1$$,将≥5的自然数表示如下
$6x-1,6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1..$
可知

I 素数筛选算法