彼得想为他的密码系统生成一些素数 . 帮助他！您的任务是生成两个给定数字之间的所有素数！输入
输入以单行中的测试用例数t开始（t <= 10） . 在接下来的t行中的每一行中，存在由空格分隔的两个数m和n（1 <= m <= n <= 1000000000，n-m <= 100000） . 产量
对于每个测试用例，打印所有质数p，使得m <= p <= n，每行一个数，由空行分隔的测试用例 .
任何人都可以帮助我优化我的代码，因为它显示即使在我使用筛子后超出时间限制 . 这是问题的链接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;
}
1 回答
您的代码几乎没有问题：
您无法在给定的时间约束内创建10 ^ 9（
int a[n]）数组！嵌套的 for 循环耗时太长
O(sqrt(n-m)^2)优化使用https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes和https://www.geeksforgeeks.org/segmented-sieve/