I have tried solving http://www.spoj.com/problems/PAGAIN/ using segmented sieve.

But am getting tle.

Please suggest how to minimize it.

Solutions:https://ideone.com/qaRr12

# include <iostream.h>

```
# include <conio.h>
int checkprime(unsigned int i)
{ int flag=1;
for (unsigned int j=2;j<i/2;j++)
{if (i%j==0)
{ flag =0;
break ;}
}
if (flag==1)
return 1;
else
return 2;
}
void main ()
{clrscr();
unsigned int n,t;
cout<<"\n Enter your number";
cin>>n;
for(t=n;t<=n,t>2;t--)
{ if ( checkprime(t) == 1)
{ cout<<"\n THe nearest prime number smaller than your number is:";
cout<< t;
break; }
}
getch();
}
```

This problem cannot be solved using deterministic primality test because n can be upto 2^32 which is approx 10^9, so we can solve it using probabilistic primality test.

Topcoder has and excellent tutorial on probabilistic primality test, go through this : https://www.topcoder.com/community/data-science/data-science-tutorials/primality-testing-non-deterministic-algorithms/

PS: In your problem you are using sieve technique but you don’t realise the fact that online judge provides space upto 10^7 so it won’t work above 10^7

sorry i am new

i think you should click on edit.

i hope it is right.

Fixed the formatting.

@vijju this won’t solve the problem, it’ll show TLE, this problem needs to be done with probabilistic primality test than deterministic because n> 10^7 which is beyond allocated space by online judge

hi @neilit1992 we can surely solve this problem using deterministic primality test.

Here is my accepted solution

@akt_rabbit can explain you me the approach please, I didn’t face that procedure yet, I’m well acquainted with segmented seive and probabilistic primality test. I got an idea of your approach but after the step low = n-200 went over my head.

@neilit1992 Its not my code. I merely fixed the presentation of the code, so that it becomes legible.