试除法

根据素数的定义，对于自然数$n$，只要能够找到除了1和它本身以外，能够整除该数的正整数，那么它就不是素数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i <= n; ++i) {
        if (n % i == 0 && i != n) {
            return false;
        }
    }

    return true;
}

又因为，如果$d$是$n$的约数，那么$n=d \times n/d$，故$n/d$也是，且$\min{d, n/d} \leq \sqrt{n}$,

因此只需要测试到$\sqrt{n}$即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i * i <= n; ++i) {
        // i won't equal to n, so i != n is unnecessary.
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

上述方法需要约$2^{n/2}/((n/2)\ln 2)$次测试。

埃氏筛

对于单个小整数，试除法尚可，但是如果要枚举$n$以内的素数，使用试除法就需要对$n$以内的所有自然数都做测试，效率太低。

埃拉托斯特尼筛法，简称埃氏筛，从2开始，将每个素数的所有倍数标记为合数，如果这个$n$小于最后一个标出的素数的平方，那么所有小于$n$且未标记的都是素数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
vector<bool> isPrime(n, true);
isPrime[0] = isPrime[1] = false;

int i = 0;

while (i * i < n) {
    if (isPrime[i]) {
        int j = 2;
        while (i * j <= n) {
            isPrime[i * j] = false;
            ++j;
        }
    }

    ++i;
}

埃氏筛的时间复杂度为$O(n\log n \log n)$，但这个方法最大的问题在于，需要的内存随着$n$的增大而增大。

整数分解

试除法

分解整数，普通方法是用短除法，从最小的素数除起，知道结果为素数为止。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
for (int i = 2; i * i <= n; ++i) {
    while (n % i == 0) {
        std::cout << i;
        n /= i;
    }
}

if (n > 1) {
    std::cout << n;
}

既然是从最小的素数除起，上述代码在每次++i后，为什么不检测i是否为素数？

原因是，内层循环相当于已经把当前i的所有倍数去除了，类似埃氏筛，故下次取到的能够整除$n$的i是素数。

素数相关问题及算法

试除法

埃氏筛

整数分解

试除法

References