题解 | #素数#

- 每次用vector存放满足条件素数（每次都判断，时间复杂度较高）

#include<iostream>
#include<vector>
using namespace std;
vector<int>sushu;

bool baoli(int x){//判定素数
    if(x<=1)return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        int i=11;
        while(i<n){
            if(baoli(i))sushu.push_back(i);//满足条件素数存入向量中
            i=i+10;
        }
        if(sushu.empty())printf("-1\n");
        else {
              for(int i=0;i<sushu.size();i++){
                if(i==0)printf("%d",sushu[i]);
                else printf(" %d",sushu[i]);
              }
            printf("\n");
        }
    }
    return 0;
}

- 先存好素数表，每次仅需查表

#include<iostream>
#include<vector>
using namespace std;
vector<int>sushu;

bool baoli(int x){//判定素数
    if(x<=1)return false;
    for(int i=2;i*i<=x;i++){
        if(x%i==0)return false;
    }
    return true;
}

int main(){
     int i=11;
        while(i<10000){
            if(baoli(i))sushu.push_back(i);//构造素数表
            i=i+10;
        }
    int n;
    while(scanf("%d",&n)!=EOF){
       int sum=0;
       for(int i=0;sushu[i]<n;i++){//查表，统计输出个数
           sum++;
       }
        
       if(sum==0)printf("-1");
       else{
            for(int i=0;i<sum;i++){
               if(i==0)printf("%d",sushu[i]);
               else printf(" %d",sushu[i]);
            }
       }
       printf("\n");
       }
    
    return 0;
}