生成m和n之间的素数 [英] Generating prime numbers between m and n

问题描述

这是spoj.com上的实践问题 http://www.spoj.com/problems/ PRIME1 / ..

This is a practice problem on spoj.com http://www.spoj.com/problems/PRIME1/ ..

我的提交内容提供「超过时间限制」

my submission gives "time limit exceeded"

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

constraints are : 1 <= m <= n <= 1000000000, n-m<=100000 time limit for maximum 10 test cases : 6 s

下面的代码基于筛选的eratosthenes，

I wrote the following code based on the sieve of 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'是我们必须在其之间生成素数的数字范围。

here 'm' and'n' are the range of numbers between which we have to generate prime numbers.

我面对的问题是当我接受输入
100000000 100100000它需要1.04秒运行（ideone.com C ++ 4.3.2 ）和
10000000 10100000需要0.07秒

The problem i'm facing is when I take input as 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）为什么时间之间巨大的差异，

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

2) Is there an even faster way to approach this problem ?

推荐答案

1）为什么时间之间的巨大差异，这个 ？

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

时间的差异来了，因为构建筛网所需的时间对于这两个范围是不同的。对于更大的数字，它会更高。

The difference in time is coming because the time needed to build the sieve is different for both the ranges. It will be higher for bigger numbers.

2）有更快的方法来处理这个问题吗？

2) Is there an even faster way to approach this problem ?

如注释中所述，您计算每个测试用例的筛。你需要只建一个筛子，只有sqrt（1000000000）= 100000。

As stated in the comments, you are computing the sieve for every test case. You need to build the sieve only once and only up to sqrt(1000000000) = 100000.

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

My solution (long ago) was as follows:

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

这篇关于生成m和n之间的素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！