首页 文章

生成m和n之间的素数[重复]

提问于
浏览 次
2

这个问题在这里已有答案：

这是spoj.com http://www.spoj.com/problems/PRIME1/上的练习题 .

我的提交给出了“超出时间限制”

约束为：1 <= m <= n <= 1000000000，n-m <= 100000最大10个测试用例的时间限制：6 s

我根据eratosthenes的筛子编写了以下代码，

void sieve(int m,int n)
{
       bool prime[1000005]; 
        bool prime2[1000005];
  int i;
    int k;

   prime[0]=1;
   prime[1]=1;

   int mi=sqrt(n);

   for (int i=2; i<=mi; i++)
      if (prime[i]==0)
         for ( k=i*i; k<=n; k+=i)
            {
                if(k<=mi)
            prime[k]=1;

            if(k>=m)
            {

            prime2[k-m]=1;
            }

            }


    int u=min(n,(int)1000000);
   for(i=0;i<u;i++){

    if(prime2[i]==0 && i+m>=2 && i+m<=n)
    printf("%d\n",i+m);
   }
            printf("\n");


}

这里'm'和'n'是我们必须生成素数的数字范围 .

我面临的问题是当我输入 100000000 100100000 it takes 1.04 s to run (ideone.com C++ 4.3.2) and for 10000000 10100000 it takes 0.07 s 时

1) why the huge difference between the times , what is contributing to this ?

2）有更快的方法来解决这个问题吗？

c++ performance algorithm

1 回答

  • 2

    1）为什么时代的巨大差异，是什么促成了这一点？

    时间上的差异即将到来，因为构建筛子所需的时间对于两个范围都是不同的 . 对于更大的数字，它会更高 .

    2）是否有更快的方法来解决这个问题？

    正如评论中所述，您正在计算每个测试用例的筛子 . 您只需要构建一次筛网，最多只需要sqrt（1000000000）= 100000 .

    我的解决方案（很久以前）如下：

    #include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iterator>

bool is_prime (const int& n, std::vector<int>& v);

int main() {
  int t;
  std::cin >> t;
  std::vector<int> prime_array;

  // build the sieve
  for (int i=2; i<=100000; i++)
    if ( is_prime( i, prime_array ) ) 
        prime_array.push_back( i );

  while (t--) {
    long long m;
    long long n;

    std::cin >> m;
    std::cin >> n;

    if (m<2) m = 2;

    //check for the prime numbers in the range.
    for (int i=m; i<=n; i++)
      if ( is_prime( i, prime_array ) ) 
        std::cout << i << std::endl;
    std::cout << std::endl;

  }
  return 0;
}


// we need to check for prime factors up to sqrt(n)
bool is_prime (const int& n, std::vector<int>& v) {
  double root = sqrt (n);
  std::vector<int>::iterator it = v.begin();
  while ( it != v.end() && *it <= root ) {
    if (!( n % *it)) return 0;
    it++;
  }
  return 1;
}
    回复于

相关问题