输入格式

输入一个数n， 表示所求素数的最大范围。

输出格式

第一行输出范围内的素数个数m。

接下来的m行从小到大每行输出一个素数。

代码

#include <cstdio>
using namespace std;
#define MAXN 1000050

int read() {
    int x = 0; bool f = 0; char ch = getchar();
    while (!isdigit(ch)) f = (ch == 45), ch = getchar();
    while ( isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return f ? (~x + 1) : x;
}

int n;

int prime[MAXN], notPrime[MAXN], tot = 0;

void judgePrime(int n) {
    notPrime[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!notPrime[i]) prime[++tot] = i;
        for (int j = 1; j <= tot && prime[j] * i <= n; j++) {
            notPrime[prime[j] * i] = 1;
            if (i % prime[j] == 0) 
                break;
        }
    }
}

int main() {
    n = read();
    judgePrime(n);
    for (int i = 1; i <= tot; i++) 
        printf("%d\n", prime[i]);
    return 0;
}