PRIME1: Getting tle

general
, , ,
1

Please help me to optimize the following C code:

#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++){
        printf("\n please enter the numbers.\n");
        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
2

  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

3 Likes
3

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

4

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
5
  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);}
6

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

This also displays TLE.

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