c++ - C++ 中埃拉托色尼筛法的问题

Question

我正在尝试用 C++ 实现 Erasthones 筛法，但遇到了很多问题。我的代码如下:

#include <iostream>
int main()
{
    const int max = 1000;
    int count = 1;
    bool arr[max];

    for(int i = 0; i < max; ++i)
        arr[i] = true;

    for(int i = 2; i < max; i++)
    {
        //mark all multiples
        for(int j = 2; (j*i) < max-1; ++j) arr[i*j] = false;
    }
}

我不知道下一步是什么。我在网上看过，但我不明白很多代码。您能否提供一个有效的 C++ 代码示例及其工作原理？

Answer 1

您的代码没有重大缺陷 - 它可以工作，但有点笨重。

基本逻辑是:

1. 用 1(用于节省内存的字符)填充一个名为 sieve 的 vector
2. 对于第一个 vector 中的每个素数元素，将其所有倍数标记为素数
3. 将第一个 vector 中的每个素数元素添加到 retVector 中，并返回所有素数的 vector ，直到 limit

筛子在 C++ 中的另一个工作实现可能如下所示:

vector<long long> sieve(unsigned long long & limit) 
{
    vector<char> sieve(limit, '1');
    vector<long long> retVector;

    for (long long i = 0; i < limit; i++)
        sieve[i] = 1;

    for (long long i = 2; i < limit; i++) {
        if (sieve[i] == 1) {
            for (long long j = i*i; j < limit; j += i)
                sieve[j] = 0;
        }
    }
    for (long long i = 2; i < limit; ++i) if (sieve[i] == 1) retVector.push_back(i);
    return retVector;
}