素数

素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是质数也不是合数）。

六倍原理

原理：除了2和3以外，其余素数都与6的倍数相邻，也就是也就是说大于3的质数一定满足$6n+1$或$6n-1$。

用途
忘了筛法的时候可以使暴力写法变得不那么暴力

模板

bool isprime(int n)
{
    if (n == 1)
        return false;
    else if (n == 2 || n == 3)
        return true;
    //不满足六倍原理，一定不是素数
    else if (n % 6 != 1 && n % 6 != 5)
        return false;

    //只判断6倍的邻数
    for (int i = 5; i <= sqrt(n); i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

埃氏筛法

原理：要得到自然数$n$以内的全部素数，必须把不大于根号$n$的所有素数的倍数剔除，剩下的就是素数。

时间复杂度：$O(n* log(logn))$
有的写法内层循环不同时间复杂度可能是$O(n*logn)$

模板

bool is_prime[1000]; //标记是否是素数

for (int i = 0; i <= n; i++)
        is_prime[i] = true; //初始化所有的数为素数
    is_prime[1] = false;
    for (int i = 2; i <= sqrt(n); i++)
    { //从第一个素数2开始筛选
        if (is_prime[i])
        { //如果是素数
            for (int j = i * i; j <= n; j += i) //一个小优化，从i * i开始而不是从 i + i开始
            { //则剔除掉它的倍数
                is_prime[j] = false;
            }
        }
    }

欧拉筛法（线性筛）

原理：使用埃式筛法时，同一个数字会被筛选多次，比如6先被2筛选一次，再被3筛选一次，这样就浪费了很多的时间。欧拉筛正是埃式筛的优化。即让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。

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

模板

//求小于等于n的素数的个数，并输出每个素数
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5;
int prime[N]; //存素数
bool vis[N];  //保证不做素数的倍数
int main()
{
    int n, cnt = 0;
    cin >> n;
    memset(vis, false, sizeof(vis)); //初始化
    memset(prime, 0, sizeof(prime));
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])          //未被标记
            prime[cnt++] = i; //则找到素数
        for (int j = 0; j < cnt && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = true; //标记找到的素数的倍数
            if (i % prime[j] == 0)
                break; //线性的关键！！
        }
    }
    cout << cnt << endl;
    for (int i = 0; i < cnt; i++)
        cout << prime[i] << " "; //输出每个素数
    return 0;
}

个人学习记录，非教程，所以不太注重以上算法原理的解释

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。