c++ - 我的埃拉托色尼筛法耗时太长

Question

我已经实现了 Sieve of Eratosthenes解决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;
    }
  }
}

Answer 1

您的代码很慢，因为您没有实现埃拉托色尼筛法算法。该算法以这种方式工作:

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，如果您使用这种天真的方法会导致内存问题方式。这个问题是你的:)