c++ - 我的埃拉托色尼筛需要太长时间

Question

我已经实施了埃拉托色尼筛法来解决SPOJ问题PRIME1。虽然输出很好，但我的提交超过了时间限制。如何减少运行时间？

int main()
{
  vector<int> prime_list;
  prime_list.push_back(2);
  vector<int>::iterator c;
  bool flag=true;
  unsigned int m,n;
  for(int i=3; i<=32000;i+=2)
  {
    flag=true;
    float s = sqrt(static_cast<float>(i));
    for(c=prime_list.begin();c<=prime_list.end();c++)
    {
        if(*c>s)
            break;
        if(i%(*c)==0)
        {
            flag=false;
            break;
        }
    }
    if(flag==true)
    {
        prime_list.push_back(i);
    }
  }
  int t;
  cin>>t;
  for (int times = 0; times < t; times++)
  {
    cin>> m >> n;
    if (t) cout << endl;
    if (m < 2)
        m=2;
    unsigned int j;
    vector<unsigned int> req_list;
    for(j=m;j<=n;j++)
    {
        req_list.push_back(j);
    }
    vector<unsigned int>::iterator k;
    flag=true;
    int p=0;
    for(j=m;j<=n;j++)
    {
        flag=true;
        float s = sqrt(static_cast<float>(j));
        for(c=prime_list.begin();c<=prime_list.end();c++)
        {
            if((*c)!=j)
            {
                if((*c)>s)
                    break;
                if(j%(*c)==0)
                {
                    flag=false;
                    break;
                }
            }
        }
        if(flag==false)
        {
            req_list.erase (req_list.begin()+p);
            p--;
        }
        p++;
    }
    for(k=req_list.begin();k<req_list.end();k++)
    {
        cout<<*k;
        cout<<endl;
    }
  }
}

score 4 · Accepted Answer

您的代码很慢，因为您没有实现埃拉托色尼筛算法。该算法是这样工作的：

1) Create an array with size n-1, representing the numbers 2 to n, filling it with boolean values true (true means that the number is prime; do not forget we start counting from number 2 i.e. array[0] is the number 2)
2) Initialize array[0] = false.
3) Current_number = 2;
3) Iterate through the array by increasing the index by Current_number.
4) Search for the first number (except index 0) with true value.
5) Current_number = index + 2;
6) Continue steps 3-5 until search is finished.

该算法需要 O(nloglogn) 时间。你所做的实际上需要更多时间 (O(n^2))。顺便说一句，在第二步（搜索 n 和 m 之间的素数）中，您不必检查这些数字是否再次为素数，理想情况下，您将在算法的第一阶段计算它们。

正如我在您链接的站点中看到的那样，主要问题是您实际上无法创建大小为 n-1 的数组，因为最大数 n 为 10^9，如果您以这种幼稚的方式进行操作，则会导致内存问题。这个问题是你的:)

score 3 · Accepted Answer

我会扔掉你拥有的东西，从一个非常简单的筛子实现重新开始，如果真的需要，只会增加更多的复杂性。这是一个可能的起点：

#include <vector>
#include <iostream>

int main() {
    int number = 32000;
    std::vector<bool> sieve(number,false);
    sieve[0] = true;  // Not used for now, 
    sieve[1] = true;  //   but you'll probably need these later.

    for(int i = 2; i<number; i++) {
        if(!sieve[i]) {
            std::cout << "\t" << i;
            for (int temp = 2*i; temp<number; temp += i)
                sieve[temp] = true;
        }
    }
    return 0;
}

对于给定的范围（最多 32000），这将在不到一秒的时间内运行（输出定向到文件 - 到屏幕上通常会更慢）。不过，这取决于你……

score 2 · Accepted Answer

我不确定您是否实施了 Erasthotenes 筛。无论如何，有几件事可以在某种程度上加速您的算法：通过预分配空间（查找std::vector<>::reserve）避免向量内容的多次重定位。该操作sqrt很昂贵，您可以通过修改测试来完全避免它（在检查时停止x*x > y而不是检查x < sqrt(y).

然后，通过修改实际算法，您将获得更好的改进。粗略地看，似乎您正在迭代所有候选者，并为它们中的每一个进行迭代，试图与所有可能是因子的已知素数相除。Erasthotenes 的筛子采用单个素数并在一次通过中丢弃该素数的所有倍数。

请注意，筛子不会执行任何操作来测试一个数字是否为素数，如果它之前没有被丢弃，那么它就是一个素数。对于每个唯一因素，每个非素数仅访问一次。另一方面，您的算法正在多次处理每个数字（针对现有素数）

score 1 · Accepted Answer

我理解这个问题的方式是你必须在 [m,n] 范围内生成所有素数。

一种无需从 [0,n] 计算所有素数的方法是首先生成 [0,sqrt(n)] 范围内的所有素数，因为这很可能会减慢您的速度。

然后使用结果在 [m,n] 范围内进行筛选。要生成初始素数列表，请实现 Eratosthenes 筛子的基本版本（维基百科文章中的伪代码几乎只是一个简单的实现就可以了）。

这应该使您能够在很短的时间内解决问题。

这是 Eratosthenes 筛子的简单示例实现：

std::vector<unsigned> sieve( unsigned n ) {
    std::vector<bool> v( limit, true ); //Will be used for testing numbers
    std::vector<unsigned> p;            //Will hold the prime numbers

    for( unsigned i = 2; i < n; ++i ) {
        if( v[i] ) {                    //Found a prime number
            p.push_back(i);             //Stuff it into our list

            for( unsigned j = i + i; j < n; j += i ) {
                v[i] = false;           //Isn't a prime/Is composite
            }
        }
    }

    return p;
}

它返回一个仅包含从 0 到 n 的素数的向量。然后你可以用它来实现我提到的方法。现在，我不会为您提供实现，但是，您基本上必须做与 Eratosthenes 筛中相同的事情，但不是使用所有整数 [2,n]，而是使用您找到的结果。不确定这是不是放弃太多了？

score 1 · Accepted Answer

我认为稍微加快筛子速度的一种方法是防止在此行中使用 mod 运算符。

if(i%(*c)==0)

而不是（相对）昂贵的 mod 操作，也许如果你在你的筛子中向前迭代加法。

老实说，我不知道这是否正确。如果没有注释和单字母变量名，您的代码很难阅读。

score -1 · Accepted Answer

由于原始问题中的SPOJ 问题未指定必须使用埃拉托色尼筛法解决，因此这里有一个基于本文的替代解决方案。在我六岁的笔记本电脑上，对于最差的单个测试用例（nm=100,000），它的运行时间约为 15 毫秒。

#include <set>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
   while (true) {
      a = a % b;

      if(a == 0)
         return b;

      b = b % a;

      if(b == 0)
         return a;
   }
}

/**
 * Here is Rowland's formula. We define a(1) = 7, and for n >= 2 we set 
 *
 * a(n) = a(n-1) + gcd(n,a(n-1)). 
 *
 * Here "gcd" means the greatest common divisor. So, for example, we find
 * a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1),
 * the so-called first differences of the original sequence.
 */
void find_primes(int start, int end, set<int>* primes) {
   int an;        // a(n)
   int anm1 = 7;  // a(n-1)
   int diff;

   for (int n = start; n < end; n++) {
      an = anm1 + gcd(n, anm1);

      diff = an - anm1;

      if (diff > 1)
         primes->insert(diff);

      anm1 = an;
   }
}

int main() {
   const int end = 100000;
   const int start = 2;

   set<int> primes;

   find_primes(start, end, &primes);
   ticks = GetTickCount() - ticks;

   cout << "Found " << primes.size() << " primes:" << endl;

   set<int>::iterator iter = primes.begin();
   for (; iter != primes.end(); ++iter)
      cout << *iter << endl;
}

score -3 · Accepted Answer

-3

分析您的代码，找到热点，消除它们。Windows , Linux分析器链接。

于 2010-10-05T21:49:00.697 回答

c++ - 我的埃拉托色尼筛需要太长时间

7 回答 7

Related

Reference