这个主要的生成器是低效的C ++吗？ [英] Is this prime generator inefficient C++?

问题描述

这被看作是一个有效的素数发生器。在我看来，这是相当高效。是使用流程使程序运行速度更慢吗？

Is this seen as an in efficient prime number generator. It seems to me that this is pretty efficient. Is it the use of the stream that makes the program run slower?

我试图提交到 SPOJ ，它告诉我我的时间限制超过...

I am trying to submit this to SPOJ and it tells me that my time limit exceeded...

#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

推荐答案

这是一个步骤（跳过偶数）我建议将筛选Eratosthenes 作为更有效的算法。从以上链接：

This is one step (skipping even numbers) above the naive algorithm. I would suggest the Sieve Of Eratosthenes as a more efficient algorithm. From the above link:

算法的复杂性是
O（（nlogn）（loglogn））， b $ b需求O（n）。 Eratosthenes筛选的分段
版本，带有基本优化（例如wheel
因式分解）的
版本使用O（n）操作
和O（n1 / 2loglogn / logn）
内存。

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）附近。你跳过evens得到的加速不是那么好，因为你会发现一个偶数在第一次测试时不是最好的。该筛具有大得多的存储器要求，但是对于大的 N ，运行时间复杂性远远优越。

The algorithm you give is somewhere near O(n^2). The speedup you get by skipping evens isn't that great because you would find an even number not to be prime on the first test. The sieve has a much greater memory requirement, but the runtime complexity is far superior for large N.

这篇关于这个主要的生成器是低效的C ++吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！