写这个类型博客的目的就是想总结一下某个专题的知识点，方便以后比赛前复习，由于太菜，如有错误，还请斧正。

首先讲一下求素数筛的几个算法

一、循环暴力法（O(n*sqrt(n))）

二、埃氏筛(O(nloglogn))对于数据范围较小的可以用，写着方便

void isprime(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=2;j*i<=n;j++)
        {
            vis[i*j]=true;
        }
    }
}

三、线性筛（欧拉筛）(O(n))

void oulasai(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i]) prime[x++]=i;
        for(int j=0;j<x;j++)
        {
            if(i*prime[j]>n) break;
            vis[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

四、米勒罗宾素数检测（基于随机算法的筛法，不稳定）

摘自：https://www.cnblogs.com/SinGuLaRiTy2001/p/6591414.html

#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
const int count=10;
int modular_exp(int a,int m,int n)
{
    if(m==0)
        return 1;
    if(m==1)
        return (a%n);
    long long w=modular_exp(a,m/2,n);
    w=w*w%n;
    if(m&1)
        w=w*a%n;
    return w;
} 
bool Miller_Rabin(int n)
{
    if(n==2)
        return true;
    for(int i=0;i<count;i++)
    {
        int a=rand()%(n-2)+2;
        if(modular_exp(a,n,n)!=a)
            return false;
    }
    return true;
}
int main()
{
    srand(time(NULL));
    int n;
    scanf("%d",&n);
    if(Miller_Rabin(n))
        printf("Probably a prime.");
    else
        printf("A composite.");
    printf("\n");
    return 0;
}

以上是常用的几种素数筛法

下面呢就来讲讲素数的一些性质

1.哥德巴赫猜想：任何一个大于4的偶数可以拆分成两个质数，任何一个大于7的奇数可以拆分成三个质数

2.如果2^x-1是素数，那x一定也是素数

3.所有大于10的质数中，个位数只有1,3,7,9

4.任何大于3的素数都可以表示为形式

5.所有大于2的素数都可以唯一地表示成两个平方数之差​​​​

6.当n为大于2的整数时，2^n+1和2^n-1两个数中，如果其中一个数是素数，那么另一个数一定是合数

当然素数的应用还有很多

比如预处理每个数的所有质因数：

const int N = 100000 + 5;
vector<int > prime_factor[N];
void init(){
    for(int i = 2; i < N; i ++){
        if(prime_factor[i].size() == 0){//如果i是质数 
            for(int j = i; j < N; j += i){
                prime_factor[j].push_back(i); 
            }
        }
    }
}

比如预处理每个数的所有因数

const int N = 100000 + 5;
vector<int > factor[N];
void init(){
    for(int i = 2; i < N; i ++){ 
        for(int j = i; j < N; j += i){
            factor[j].push_back(i); 
        }
    }
}

 比如预处理每个数的质因数分解

const int N = 100000 + 5;
vector<int > prime_factor[N];
void init(){
    int temp;
    for(int i = 2; i < N; i ++){
        if(prime_factor[i].size() == 0){
            for(int j = i; j < N; j += i){
                temp = j;
                while(temp % i == 0){
                    prime_factor[j].push_back(i);
                    temp /= i;
                }  
            }
        }
    }
}

可能以后还会有加减