I 素数判定算法

枚举判定

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

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);

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 素数筛选算法