模板原题

1. 寻找因数筛法

时间复杂度：O(nn)O(n\sqrt n)

核心模板代码如下：

1
2
3
4
5
6
7
bool isprime(int n)
{
    if (n < 2) return false;	//0和1都不是
    for(int i = 2; i * i <= n; ++ i)
        if(n % i == 0) return false;	//有1和它本身以外的其他因子就不是素数了 
    return true;
}

2. 埃氏筛法

时间复杂度：O(nlog⁡log⁡n)O(n\log \log n)

核心模板代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Eratosthenes(int n)
{
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
            for (int j = 2 * i; j <= n; j += i)
                vis[j] = true;
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            cout << i << ' ';
    cout << '\n';
}

3. 欧拉筛法

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

核心思路：

最小质因数 ×\times 最大因数（非自己） == 这个合数

核心模板代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
void getprimes(int n)
{
    for (int i = 2; i <= n; i ++)
    {
        if (!vis[i]) primes[++ cnt] = i;
        for (int j = 1; primes[j] * i <= n; j ++)
        {
            vis[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}