Getting tle in PAGAIN spoj

I have tried solving using segmented sieve.
But am getting tle.
Please suggest how to minimize it.

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;
      return 2;
void main ()
 unsigned int n,t;
 cout<<"\n Enter your number";
  { if ( checkprime(t) == 1)
       {	cout<<"\n THe nearest prime number smaller than your number is:";
	cout<< t;
	break; }

1 Like

Hey akt_rabbit,

Check out this :


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 :
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. :smiley:

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

1 Like