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

StackOverflow https://stackoverflow.com/questions/231381

  •  04-07-2019
  •  | 
  •  

题

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

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

有帮助吗？

解决方案

这是天真算法之上的一步（跳过偶数）。我建议 Sieve Of Eratosthenes 作为一种更有效的算法。从以上链接：

  

算法的复杂性是   O（（nlogn）（loglogn））带有记忆   O（n）的要求。分段   Eratosthenes筛子的版本，   基本优化，如车轮   分解，使用O（n）运算   和O（n1 / 2loglogn / logn）位   存储器中。

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

其他提示

你正在搜索 lot 更多的数字 - 最多你只需要去<= (sqrt(num))。

这是一个简单的Eratosthenes筛子。它不需要预先设置一个大的布尔数组，但它在时间和空间上仍然是<！> gt; <！> gt; O（n）。只要你有足够的记忆力，它应该明显快于你现在的na <！>＃239; ve方法。

#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;
}

如果这对你来说仍然太慢，你可能想要追求阿特金筛选，优化的Eratosthenes筛选。

实际上，如果要生成的素数范围开始较低，这些只是相对有效。如果下限已经相当大并且上限不比下限大很多，则筛分方法是浪费的工作，你最好不要运行素性测试。

还有一件事，不要在循环中使用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)

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

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），但它通常是一个足够好的估计。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top