C++ – 判断素数

题目链接

基础型O（n*n）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
    int n,ans=0;
    scanf("%d",&n);
    for(int i=2; i<=n; i++) {
        int flag=0;
        for(int j=2; j<=sqrt(i); j++) {
            if(i%j==0) {
                flag=1;
                break;
            }
        }
        if(flag==0) ans++;
    }
    printf("%d",ans);
    return 0;
}

提高型O（N*log（logN））

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10000007;
bool prime[maxn];
void make_prime(){
    memset(prime,1,sizeof prime);
    prime[0]=prime[1]=0;
    int t=sqrt(maxn);
    for(int i=2;i<=t;i++){
        if(prime[i]){
            for(int j=2*i;j<maxn;j+=i){
                prime[j]=0;
            }
        }
    }
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    make_prime();
    for(int i=1;i<=m;i++){
        int a;
        scanf("%d",&a);
        if(prime[a]==1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

复杂度同上但可打印素数表

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10000007; 
int prime_table[maxn];
bool prime2[maxn];
void liner_function(){
    memset(prime2,true,sizeof prime2);
    prime2[0]=prime2[1]=false;
    int num=0;
    for(int i=2;i<=maxn;i++){
        if(prime2[i])
            prime_table[num++]=i;
        for(int j=0;j<num&&i*prime_table[j]<maxn;j++){
            prime2[i*prime_table[j]]=false;
            if(i%prime_table[j]==0) break;
        }
    }
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    liner_function();
    for(int i=1;i<=m;i++){
        int a;
        scanf("%d",&a);
        if(prime2[a]==true) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}