# PRIME1: Getting tle

#include <stdio.h>
#include <stdlib.h>
int main(){
int p,q,n,i,j,k,l;
printf("\n please enter the no. of test cases");
scanf("%d",&n);
for(k=0;k<n;k++){
scanf("%d %d",&p,&q);
printf("\n Prime numbers between %d and %d.\n",p,q);
if(p>q)
{
int t = p;
p=q;
q=t;
}
if(p==2 || p == 1 && q != 1)
printf("\t 2");
if(p%2 == 0)
p = p+1;
if(q==2)
printf("\t 2");
if(q%2 == 0)
q = q-1;

for(i=p;i<=q;i=i+2)
{
l = i/2;
if(l == 1)
l=2;
for(j=2;j<=l;j++)
{
if(i%j == 0)
break;
if(j==l)
printf("\t %d",i);
}
}
}
return 0;
}
1 Like
1. To check if a number n is prime or not, you need to check if the number is divisible by any number only till sqrt(n) and not till n/2

2. If you to do this task repeatedly, and your numbers are inside a certain range, you can use prime sieve to pre-compute all the primes in that range and output them by just iterating over them

6 Likes

If you are submitting this for PRIME1…
1> make sure that you use something bigger than int
2> There is no need for printf("\n please enter the no. of test cases"); …comment it

https://www.codechef.com/viewsolution/10274498 caused a TLE, so I replaced the cin/cout within the loops to scanf/printf
https://www.codechef.com/viewsolution/10274510
but still getting a TLE

Also, how to prevent 1 from being printed as a prime?

1 Like
1. As mentioned above use sqrt(n) instead of n/2 for checking prime as it will reduce iteration of loop.
2. In above code if one enters p=1 and q=2 output will be 2 2 i.e two times 2.
3. If you will check no. upto sqrt(n)(i.e also dividing it by sqrt(n)) it will not show 1 as prime.
TRY THIS ONE
printf(“The prime numbers between %d and %d are:\n”,l,u);
for(k=l+1;k<u;k++)
{ if(k%2==0&&k!=2){continue;}
else
{ flag=0;
for(i=2;i<=sqrt(k);i++)
{
if(k%i==0)
{flag=1;break;}
}
if(flag==0)
printf("%d\t",k);}

https://www.codechef.com/viewsolution/12185252

This also displays TLE.

I understand the algo sieve of erastothenes. But can someone give an example code?

//