c++ - isPrime 函数的改进

Question

网上有很多问题需要你找质数，所以我决定写一组函数来找它们。我使用 Eratosthenes 筛法 生成素数，因为与其他算法相比，它快速且易于实现。但是，我想知道是不是我的代码而不是我的方法 效率低下。我使用的是 STL 容器/迭代器吗？我的代码中是否有任何部分减慢了程序速度？

换句话说，它确实计算出了正确的结果，但我想知道是否可以通过一些算法改进而不是仅仅通过一些代码调整来提高它的效率。

非常感谢任何帮助。

这是我的代码(如果难以阅读，我深表歉意)

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

#define initial_prime_barrier 100
bool isFlagged(int i) { return i == 0; }
bool isNextStart(int i) { return i != 0; }

vector<int> generatePrimesBelow(int limit)
{
   vector<int> primes;
   for (int i = 2; i < limit; i++)
   {
      primes.push_back(i);
   }  
   vector<int>::iterator currentStart = primes.begin();
   do
   {
      int numberAtStart = *currentStart;
      vector<int>::iterator currentNumber = currentStart + numberAtStart;
      do
      {
         *currentNumber = 0;
         advance(currentNumber, numberAtStart);
      } while (currentNumber < primes.end());
      currentStart = find_if(currentStart + 1, primes.end(), isNextStart);
   } while ((*currentStart) * (*currentStart) < limit);
   vector<int>::iterator newEnd = remove_if(primes.begin(), primes.end(), isFlagged);
   primes.erase(newEnd, primes.end());
   return primes;
}

bool isPrime(int number)
{
   static vector<int> primes = generatePrimesBelow(initial_prime_barrier);
   static int numPrimes = primes.size();
   static int largestPrime = primes[numPrimes-1];
   static int halfwayPrime = primes[numPrimes/2];
   if (number == largestPrime)
   {
      return true;
   }
   else if (number < largestPrime)
   {
      if (number == halfwayPrime)
      {
         return true;
      }
      else if (number > halfwayPrime)
      {
         for (int i = numPrimes/2; i < numPrimes; i++)
         {
            if (number == primes[i])
            {
               return true;
            }
         }
      }
      else if (number < halfwayPrime)
      {
         for (int i = numPrimes/2; i >= 0; i--)
         {
            if (number == primes[i])
            {
               return true;
            }
         }
      }
   }
   else if (number > largestPrime)
   {
      primes = generatePrimesBelow(number + number);
      numPrimes = primes.size();
      largestPrime = primes[numPrimes-1];
      halfwayPrime = primes[numPrimes/2];
      return isPrime(number);
   }
   return false;
}

int main (int argc, char * const argv[]) 
{
   const int number = 123123;
   cout << (isPrime(number) ? "YES" : "NO") << endl;
}

Answer 1

是的，这是你的方法。几件事。您不需要数组来保存数字，数组中每个条目的地址就是数字本身。您只需要它们包含两个值 - true和 false .所以让你的数组 vector<bool> ，它会更紧凑。然后，在你的内部循环中，你从 x+x 开始并按 x 的步骤推进.你应该从x*x开始, 并按 2*x 步进- 这将适用于所有 x除了 2 .做一个特例，或者在初始化循环中标记这些偶数。或在 i 处理条目表示数字 2*i+1并完全免除处理偶数。这应该会加快您的筛选代码。最后，你不需要特殊的 find_if调用它的所有机制，你可以只检查循环中出现的当前条目。

(编辑:)在你的isPrime您手动执行二进制搜索，但 STL 中已经有一个 binary_search 算法。如果你保留你的 vector<bool>，你根本不需要它按原样筛选阵列，不压缩。然后 isPrime(i)只需要检查数组的值是否位于索引 i 处还是true .

(edit2:) 现在，关于效率。您重新计算了 n+n ，可能是为了测试更多的数字。如果你只测试几个，简单的试分赔率会更快。如果要测试的数字都在一个狭窄的上部区域，您最好的选择是偏置筛，下部筛到sqrt。测试区域的上限。如果数字分布广泛，则可以使用您当前的整个数组方法。

此处要使用的关键事实是大约有 n ~= m/log m m 以下的素数在值(value)上，即从 0 中筛选一个数组至 m需要 O(m*log (log m))时间，然后筛选 a 之间的上部区域和 b ，即宽度 d=b-a , 通过以下所有素数 r=sqrt b ，它需要的时间与 d*log (log r) 成正比.

另外，当增加你的筛阵列时最好扩大，而不是重新计算整个。质数都在那里。要筛选附件，需要遍历筛选数组中的所有素数，直到 sqrt。其新的上边缘。这让人想起分段筛子，尽管每个新分段都取代了前一个分段，或者在任何情况下都与前一个分段分开。