判断一个数是否为素数c

判断一个数是否为素数有多种方法，常见的有三种：
1.试除法：从2到sqrt(n)枚举n的因子，如果存在n的因子，则n不是素数。
2.埃氏筛法：先将2到n的所有数标记为素数，然后从2开始枚举，将其所有的倍数标记为合数，最后剩下的就是素数。
3.欧拉筛法：与埃氏筛法类似，但是在标记合数时只标记其最小质因子的倍数，避免了重复标记。

以下是三种方法的C++代码实现：
1.试除法：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    bool flag=true;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            flag=false;
            break;
        }
    }
    if(flag) cout<<"YES";
    else cout<<"NO";
    return 0;
}

2.埃氏筛法：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    bool flag[n+1];
    memset(flag,true,sizeof(flag));
    for(int i=2;i<=n;i++){
        if(flag[i]){
            for(int j=2*i;j<=n;j+=i){
                flag[j]=false;
            }
        }
    }
    if(flag[n]) cout<<"YES";
    else cout<<"NO";
    return 0;
}

3.欧拉筛法：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    bool flag[n+1];
    memset(flag,true,sizeof(flag));
    vector<int> primes;
    for(int i=2;i<=n;i++){
        if(flag[i]) primes.push_back(i);
        for(int j=0;j<primes.size()&&i*primes[j]<=n;j++){
            flag[i*primes[j]]=false;
            if(i%primes[j]==0) break;
        }
    }
    if(flag[n]) cout<<"YES";
    else cout<<"NO";
    return 0;
}