Питер хочет сгенерировать некоторые простые числа для своей криптосистемы. Помоги ему! Ваша задача - сгенерировать все простые числа между двумя заданными числами!
Входные
Ввод начинается с числа t тестовых случаев в одной строке (t <= 10). В каждой из следующих t строк есть два числа m и n (1 <= m <= n <= 1000000000, n-m <= 100000), разделенные пробелом.
Выход </p>
Для каждого теста выведите все простые числа p, такие что m <= p <= n, по одному на строку, тесты, разделенные пустой строкой. </p>
Может ли кто-нибудь помочь мне оптимизировать мой код, поскольку он показывает превышение лимита времени даже после того, как я использую sieve. Вот ссылка на проблему
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;
}