这个素数生成器是否效率低下C++？

Question

这被看作是一个有效的素数发生器.在我看来,这是非常有效的.是否使用流使程序运行得更慢？

我想把它提交给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问题)

-Tomek

Answer 1

这是天真算法之上的一步(跳过偶数).我建议使用Sieve Of Eratosthenes作为一种更有效的算法.从以上链接:

该算法的复杂性是O((nlogn)(loglogn)),其存储器要求为O(n).Eratosthenes筛的分段版本具有基本优化(例如轮分解),使用O(n)运算和O(n1/2loglogn/logn)位内存.

你给出的算法是在O(n ^ 2)附近.通过跳过evens得到的加速并不是那么好,因为在第一次测试时你会发现一个偶数不是素数.筛具有更大的内存需求,但运行的复杂性远远优于大型ñ.

Answer 2

您正在搜索的很多更多的数字比你要-顶多只需要去<= (sqrt(num)).