c++ - 这个素数生成器是低效的 C++ 吗？

Question

这是否被视为效率低下的素数生成器。在我看来，这非常有效。是不是使用了stream导致程序运行变慢了？

我正在尝试将此提交给 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)

-托梅克

Answer 1

这是朴素算法之上的一步(跳过偶数)。我建议 Sieve Of Eratosthenes作为一种更有效的算法。从上面的链接:

The complexity of the algorithm is O((nlogn)(loglogn)) with a memory requirement of O(n). The segmented version of the sieve of Eratosthenes, with basic optimizations such as wheel factorization, uses O(n) operations and O(n1 / 2loglogn / logn) bits of memory.

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