判断质数

试除法

时间复杂度O(sqrt(n))

C++代码

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
    // 这里不能写i * i <= n. 因为i*i有可能会溢出
        if (x % i == 0)
            return false;
    return true;
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }

    return 0;
}

筛法

朴素筛法O(nlog(logn))

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i])  continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法O(n)

保证每个数只被其最小质数所筛

在第二个循环内, 每次将st[primes[j] * i] = true;
要说明每次primes[j]都是primes[j] * i的最小质因子!!
1) 若i % primes[j] != 0时, 由于primes[j]是从小到大枚举的, 所以可以认为是小于所有i的质因子, 同时也就是i * primes[j]的最小质因子
2) 若i % primes[j] = 0时, primes[j]是i的最小质因子, 同时是i * primes[j]的最小质因子; 这种情况的特殊情况如: 9 * 3 = 27; 切不可把判断语句写在前面

void get_prime(int n)
{
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}