数学——数论--埃拉托色尼筛选法¶

数学——数论--埃拉托色尼筛选法¶

SJTU OJ 4047 埃拉托色尼筛法

问题描述¶

在公元前3世纪，古希腊天文学家埃拉托色尼发现了一种找出不大于n的所有自然数中的素数的算法，即埃拉托色尼筛选法。这种算法能比比朴素的遍历法更快地找出素数，它首先需要按顺序写出2到n中所有的数。以n=20为例：

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

然后把第一个元素画圈，表示它是素数，然后依次对后续元素进行如下操作：如果后面的元素是画圈元素的倍数，就画X，表示该数不是素数。在执行完第一步后，会得到素数2，而所有是2的倍数的数将全被画掉，因为他们肯定不是素数。接下来，只需要重复上述操作，把第一个既没有被圈又没有画X的元素圈起来，然后把后续的是它的倍数的数全部画X。本例中这次操作将得到素数3，而所有是3的倍数的数都被去掉。以此类推，最后数组中所有的元素不是画圈就是画X。所有被圈起来的元素均是素数，而所有画X的元素均是合数。给定一个数字，编写一个程序实现埃拉托色尼筛选法找出小于或等于该数字的的所有素数。

输入输出描述¶

输入¶

输入为一个正整数n, 2≤n≤2000000

输出¶

输出为一行，输出所有小于或等于输入的素数
数据之间用空格分隔
最后的一行输出后面无空格

程序运行示例1¶

Sample Input 1¶

Sample Output 1¶

2 3 5

程序运行示例2¶

Sample Input 2¶

Sample Output 2¶

2 3 5 7 11 13 17 19

注意¶

不要显示多余的提示信息，避免输出判定**错误**。
注意判断**输出信息**是否符合要求。

#include <bits/stdc++.h>

using namespace std;

vector<bool> isPrime(2000005, true);
int n;


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) {
            for (int j = 2; j * i <= n; ++j) isPrime[i * j] = true;
        }
    }

    for (int i = 2; i <= n; ++i) {
        if (isPrime[i]) cout << i << ' ';
    }
    cout << ndl;

    return 0;
}

空间复杂度 $O(n)$ ，时间复杂度 $O(n \log \log n)$ 。