C++判断素数模板

首先是朴素方法

代码：

#include<bits/stdc++.h>
using namespace std;
int num;
bool check(int num){
    if(num < 2){
       return false;
    }
    for(int i=2;i<=sqrt(num);i++){
        if(num%i==0){
            return false;
        }
    }
    return true;
}
int main(){
	check(num);
	return 0;
} 

然后是埃氏筛（从头找没被删的数，再把他的所有倍数都删掉）

代码：

#include <iostream>
using namespace std;
int visit[1000000];
void check(int n){
    visit[0]=1；
    visit[1]=1;
    for(int i=2;i<=n;i++){
        if(!visit[i]){
            for(int j=i*i;j<=n;j+=i){
                visit[j]=1;
            }
        }
    }
}
int main(){
    int n;
    cin>>n;
    check(n);
    for(int i=1;i<=n;i++){
        if(!visit[i])
        cout<<i<<endl;
    }
    return 0;
}

最后是欧拉筛（其实就是优化后的埃氏筛）

代码：

#include<bits/stdc++.h>
using namespace std;
int prime[100000],visit[100000];
void check(){
    visit[1]=1;
    for(int i=2;i<=100000;i++){
        if(!visit[i]){
            prime[++prime[0]]=i;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=100000;j++){
            visit[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;
            }
        }
        continue;
    }
    for(int i=1;i<=100000;i++){
        if(!visit[i]){
            cout<<i<<' ';
        }
    }
    return;
}
int main(){
    check();
    return 0;
}