# Getting tle in PAGAIN spoj

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

1 Like

# 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();
}``````
1 Like

sorry i am new

i think you should click on edit.
i hope it is right.

Hey akt_rabbit,

Check out this :

http://xoptutorials.com/index.php/2017/01/01/spojpagain/

Cheers!

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

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

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.

1 Like
//