Guys if anyone can help me!
My solution is going TLE with this solution :
thespectator:
(edit)
2016-08-30 09:27:01
Guys if anyone can help me!
My solution is going TLE with this solution :
include
using namespace std;
define ll long long int
vector prime;
ll m,n,seg_size=46400;
void pre(bool flag=false)
{
//ofstream fout("prime.txt",ios::out|ios::trunc);
prime.push_back(2);
for(ll i=3;i<=seg_size;i++)
{
bool isprime=true;
ll cap=sqrt(i)+1;
for(int j=0;j<prime.size();j++)
{
if(prime[j]>=cap)
{
break;
}
if(i%prime[j]==0)
{
isprime=false;
break;
}
}
if(isprime)
{
prime.push_back(i);
}
}
if(flag)
{
for(int i=0;i<prime.size();i++)
{
if(prime[i]>=m&&prime[i]<=n)
cout<<prime[i]<<endl;
}
}
//fout.close();
}
int main()
{
int t;
cin>>t;
//ofstream fout("prime.txt",ios::app);
while(t--)
{
cin>>m>>n;
if(n<46400)
{
pre(true);
}
else if(m>46400)
{
pre();
bool cross[100007];
ll low,high;
low=m;
high = m+46400;
while(low<n)
{
memset(cross,1,sizeof(cross));
for(int i=0;i<prime.size();i++)
{
ll lowlim=((low+prime[i]-1)/prime[i])*prime[i];
for(ll j=lowlim;j<=high;j+=prime[i])
{
cross[j-low]=false;
}
}
for(ll i=low;i<high;i++)
{
if(cross[i-low])
{
cout<<i<<endl;
}
}
low=low+seg_size;
high=high+seg_size;
if(high>n)
high=n;
}
}
else if(m<46400&&n>46400)
{
pre(true);
bool cross[100007];
ll low,high;
low=46400;
high = low+46400;
while(low<n)
{
memset(cross,1,sizeof(cross));
for(int i=0;i<prime.size();i++)
{
ll lowlim=((low+prime[i]-1)/prime[i])*prime[i];
for(ll j=lowlim;j<=high;j+=prime[i])
{
cross[j-low]=false;
}
}
for(ll i=low;i<high;i++)
{
if(cross[i-low])
{
cout<<i<<endl;
}
}
low=low+seg_size;
high=high+seg_size;
if(high>n)
high=n;
}
}
}
//fout.close();
return 0;
}
Can someone help me to reduce its time complexity,,,,,,please