SPOJ 上的质数发生器 PRIME1

Question

Peter 想为他的密码系统生成一些素数。帮助他！你的任务是生成两个给定数字之间的所有素数！输入

输入以一行中的测试用例数t开始（t<=10）。在接下来的 t 行中，每行有两个数字 m 和 n（1 <= m <= n <= 1000000000，n-m<=100000），由 space 分隔。输出

对于每个测试用例打印所有素数 p 使得 m <= p <= n，每行一个数字，用空行分隔测试用例。

任何人都可以帮助我优化我的代码，因为即使在我使用 sieve 之后它仍显示超出时间限制。这是问题的 link https://www.spoj.com/problems/PRIME1/ 这是我的代码：

#include <iostream>
#include <math.h>
using namespace std;

int is_prime(int m)
{
    int i,c=0;
    for(i=2;i<=sqrt(m);i++)
    {
        if(m%i==0)
        c++;
    }

    if(c==0)
    return 1;
    else
    return 0;
}
int main()
{
    int n,m,i,j,k,num;
    cin>>num;
    for(i=1;i<=num;i++)
    {
      cin>>m>>n;


      int a[n];
      for(j=0;j<=n;j++)
      a[j]=1;
      for(j=m;j<sqrt(n);j++)
      {
         if(is_prime(j)==1)
         {

            for(k=j*j;k<=n;k=k+j)
            {
                a[k]=0;
            }
         }
      }
      for(j=m;j<=n;j++)
      {
            if(a[j]==1)
            cout<<j<<endl;


      }
    cout<<endl;


   }

    enter code here
    return 0;
}

Answer 1

您的代码有几个问题：

您不能在给定的时间限制内创建 10^9 (int a[n] ) 数组！
嵌套的 for 循环花费的时间太长了几乎 O(sqrt(n-m)^2)

优化使用https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes and https://www.geeksforgeeks.org/segmented-sieve/

SPOJ 上的质数发生器 PRIME1

Prime Generator PRIME1 on SPOJ

c++

algorithm

primes

sieve-of-eratosthenes