What can be more better approach?

help
,
1

Hey why i am seeing time limit exceed in codechef but however on codechef’s code compile and run its perfectly working and it says time taken to be 0 seconds as i am an spoj user too so i submitted there also and it worked correctly giving just time taken to be 1.89 seconds code is here…


program PRIME1;

uses Math;


var
<var>
   T:integer;
   N,M:longint;
   i,y,pos:longint;
</var>
begin
	
	read(T);
	
	while T <> 0 do
	begin
	readln(M,N);
	
	for i := M to N do
	begin
	pos := ceil(sqrt(i));
	for y := 2 to pos do
	begin
	if i mod y = 0 then break
	else continue;
    end;
    if i > 1 then
    begin
	if (i mod y <> 0)  or (i=2)then
	writeln(i);
	end;
	end;
	writeln;
	T := T-1;
	end;

end.

as i suppose there is not any better approach that the sqrt(num) for finding wheter it is prime or not or there any then please do tell?

1 Like
2

maybe using AKS algorithm will help.It uses the fact that all the prime numbers other than 2 and 3 are of the form 6n-1 or 6n+1 where n belongs to natural numbers.
I haven’t tried it though.

3

Try using Sieve of Eratosthenes…its very simple and very efficient…below link will be helpfull…Edit it to solve your purpose…