本文共 1152 字，大约阅读时间需要 3 分钟。

东软学习小组成员：夜枫

本题要求使用筛法求出1~N以内的质数。

求n以内的质数。其中 n是传入的参数。n 的值不超过10 000 000的范围； 求出的质数存入容器vector并返回。

#include 
   
    #include 
    
     using namespace std;vector
     
       sieve(int n); //函数声明,求n以内的质数int main(int argc, char const *argv[]){
       int n;    cin >> n;    vector
      
        ans = sieve(n);    cout << ans.size() << endl;    for (int i = 0; i < ans.size(); i++) {
           cout << ans[i];        if (i < ans.size() - 1)cout << " ";    }    cout << endl;    return 0;}/* 请在这里填写答案 */
      
     
    
   

#include
   
    bool a[10000002];vector
    
      sieve(int n) {
   	vector
     
       temp;    int cont = 0;    memset(a, true, sizeof(a));    for (int i = 2; i <= n; ++i) {
           if (a[i]) {
               temp.push_back(i);//加入数组        }        cont = temp.size();//在这里得到，数组的元素个数，可以避免for循环内反复调用函数，节省时间        for (int j = 0; j < cont&&temp[j]*i<=n; ++j) {
               a[temp[j] * i] = false;            if (i % temp[j] == 0) {
   //避免重复标记//当前数i 是当前素数的倍数，则后面的素数乘以当前数肯定是当前数的倍数，会造成重复标记，所以遇到整除要结束当前循环的标记，进入下一轮                break;            }        }    }	return temp;}
     
    
   

转载地址：http://qggwi.baihongyu.com/