Getting tle in PAGAIN spoj

general
, ,
1

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
2

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
3

sorry i am new

4

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

5

Hey akt_rabbit,

Check out this :

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

Cheers!

6

Fixed the formatting.

7

@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

8

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

9

hi @neilit1992 we can surely solve this problem using deterministic primality test.
Here is my accepted solution

10

@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:

11

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

1 Like