2

这是否被视为有效的素数生成器。在我看来，这非常有效。是使用流使程序运行更慢吗？

我正在尝试将此提交给SPOJ，它告诉我超出了我的时间限制...

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int testCases, first, second, counter = 0;
    bool isPrime = true;
    stringstream out;

    cin >> testCases;

    for (int i = 0; i < testCases; i++) {
        // get the next two numbers
        cin >> first >> second;

        if (first%2 == 0)
            first++;

        // find the prime numbers between the two given numbers
        for (int j = first; j <= second; j+=2) {
            // go through and check if j is prime
            for (int k = 2; k < j; k++) {
                if (j%k == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                out << j << "\n";
            }
            isPrime = true;
        }
        out << "\n";
    }

    cout << out.str();

    return 0;
}

编辑：该程序应该在输入中指定的数字之间生成素数。（有关详细信息，请参见此处：Prime Generator Problem）

-托梅克

4

6 回答 6

14

这是朴素算法之上的一步（跳过偶数）。我建议将埃拉托色尼筛法作为一种更有效的算法。从上面的链接：

该算法的复杂度为 O((nlogn)(loglogn))，内存需求为 O(n)。Eratosthenes 筛子的分段版本，具有基本优化（例如轮分解），使用 O(n) 操作和 O(n1 / 2loglogn / logn) 位内存。

您给出的算法接近 O(n^2)。通过跳过偶数获得的加速并不是那么好，因为您会在第一次测试中发现偶数不是素数。筛子有更大的内存需求，但运行时复杂度对于大N来说要好得多。

于 2008-10-23T20:36:08.450 回答
7

您搜索的数字比您必须搜索的要多得多 - 最多您只需要访问<= (sqrt(num)).

于 2008-10-23T20:36:48.433 回答
4

这是一个简单的埃拉托色尼筛法。它不需要预先声明一个大的布尔数组，但它在时间和空间上仍然是 >>O(n)。不过，只要你有足够的内存，它应该比你目前的幼稚方法要快得多。

#include <iostream>
#include <map>

using namespace std;

template<typename T = int, typename M = map<T, T> >
class prime_iterator {
    public:
        prime_iterator() : current(2), skips() { skips[4] = 2; }
        T operator*() { return current; }
        prime_iterator &operator++() {
            typename M::iterator i;
            while ((i = skips.find(++current)) != skips.end()) {
                T skip = i->second, next = current + skip;
                skips.erase(i);
                for (typename M::iterator j = skips.find(next);
                        j != skips.end(); j = skips.find(next += skip)) {}
                skips[next] = skip;
            }
            skips[current * current] = current;
            return *this;
        }
    private:
        T current;
        M skips;
};

int main() {
    prime_iterator<int> primes;
    for (; *primes < 1000; ++primes)
        cout << *primes << endl;
    return 0;
}

如果这对您来说仍然太慢，您可能想要追求阿特金筛子，一种优化的埃拉托色尼筛子。

实际上，只有在生成的素数范围开始较低时，这些才是相对有效的。如果下界已经相当大，而上界并不比下界大多少，那么筛分方法是浪费工作，最好运行一个素数测试。

于 2008-10-24T22:45:16.523 回答
3

还有一件事，不要在循环中使用 sqrt(n)：

for(int k=1;k<sqrt(n);++k)

如果没有很好的优化，每次迭代都会计算 sqrt。

采用

for (int k=1;k*k < n;++k)

或者干脆

int sq = sqrt ( n );
for (int k=1;k<sq;++k)
于 2009-07-04T08:34:58.047 回答
0

它可以稍微提高效率。您不需要从 2 开始 k，您已经确保不要测试偶数。因此，k 从 3 开始。
然后每次将 k 增加 2，因为您不需要测试其他偶数。我能想到的最有效的方法是只测试一个数字是否可以被已知的素数整除（然后当你找到另一个数时，将它添加到你测试的列表中）。

于 2008-10-23T20:38:19.960 回答
0 
for (int k = 2; k < j; k++) {
     if (j%k == 0) {
         isPrime = false;
         break;
     }
}

应该：

for(int k = 3; k <= j/2; k+=2 )
{
  if( j % k == 0 )
      break;
}

j/2 确实应该是 sqrt(j) 但它通常是一个足够好的估计。

于 2008-10-23T20:40:43.027 回答