任务

给定一个正整数N，求出[2,N]中的所有素数。

说明

数组valid[i]记录i是否为素数。初始所有的valid[i]都为true。从2开始从小到大枚举i，若valid[i]=true，则把从i^2开始的所有i的倍数的valid赋为false。

结束之后valid[i]=true的就是素数。

接口

void getPrime(int n, int &tot, int ans[maxn])

复杂度：O(NlogN)，O(N)，两种实现

输入：N 所需素数的范围

输出：

• &tot 引用，素数总数
• ans 素数表

代码：

#include 
    
     #include 
     
      using namespace std;const int maxn = 1010;bool valid[maxn];void getPrime(int n, int &tot, int ans[maxn]) {    tot = 0;    int i, j;    for (i = 2; i <= n; i ++) valid[i] = true;    for (i = 2; i <= n; i ++)        if (valid[i]) {            if (n/i < i) break;            for (j = i * i; j <= n; j += i) valid[j] = false;        }    for (i = 2; i <= n; i ++)        if (valid[i]) ans[++tot] = i;}/* 素数筛法 O(N) */void getPrime2(int n, int &tot, int ans[maxn]) {    tot = 0;    memset(valid, true, sizeof(valid));    for (int i = 2; i <= n; i ++) {        if (valid[i]) {            ans[++tot] = i;        }        for (int j = 1; j <= tot && i * ans[j] <= n; j ++) {            valid[ i * ans[j] ] = false;            if (i % ans[j] == 0) break;        }    }}int main() {    int n = 100, tot, ans[maxn];    cout << "method 1" << endl;    getPrime(n, tot, ans);    cout << "tot = " << tot << endl;    for (int i = 1; i <= tot; i ++) {        if (i > 1) cout << ",";        cout << ans[i];    } cout << endl;    cout << "method 2" << endl;    getPrime2(n, tot, ans);    cout << "tot = " << tot << endl;    for (int i = 1; i <= tot; i ++) {        if (i > 1) cout << ",";        cout << ans[i];    } cout << endl;    return 0;}
     
    

使用范例

POJ3177