Agfdhyk

When i submiting this code at hackerearth i am getting TLE.

Any suggestions how can i optimise this
Code.

#include <stdio.h>

#include <stdlib.h>



int checkPrime(int);



int main() {

int a, b,

    reminder,sum=0,n;



    scanf("%d %d",&a,&b);



    while(a <= b) {

        n = a;

        sum = 0;

        reminder = 0;



        while (n > 0) {

        reminder = n % 10;

        sum += reminder;

        n = n / 10;

        }



        if(sum > 1 && checkPrime(sum) == 1 && checkPrime(a) == 1) {

            printf("%d ",a);  

        }



        ++a;

    }



return 0;

}



int checkPrime(int p) {



int i,flag=1;



for(i=2; i <= p / 2; i++){

    if(p%i == 0)  {

        flag = 0;

        break;  

    }

}



return flag;



}

Here is the problem i coded for

And how can i analysis this code and get
Time complexity.

Your checkprime function takes a lot of runtime. It runs for N/2 operations.

You are running this for all the numbers, so you are running for N*N/2 operations, which is too much.

I would suggest that you use a better method of generating the primes. Take a look at the Sieve of Eratosthenes

There are some primitive ways like this one for instance, looping through the odd numbers and some more optimizations

int isPrime ( int n )

{

    if (n <= 1) return 0; // zero and one are not prime

    unsigned int i;

    for (i=2; i*i<=n; i++) {

        if (n % i == 0) return 0;

    }

    return 1;

}

Seive is kind of over-kill, in your case ( if you are not taking in to consideration your memory requirements ) because the range could be very very large 1000000 you might want to use some sort of bitmap to generate the Seive.

here is a very loosely written Idea of how to generate and use Seive.

char *seive;



void generate_seive( int n )

{

        seive = calloc( 1, n );

        if( !seive )

        {

                printf("E...");

                exit(0);

        }



        // Generate Seive 

        for( int i = 2; i < n ; i ++)

        {

                if( seive[i] == 1 )

                        continue;

                // Essentially mark all primes as 0 and

                // non-primes as 1's

                seive[i] = 0;

                for( int j = i + i ; j < n ; j += i )

                        seive[j] = 1;

        }

}



int main()

{

        generate_seive(100);



        // Iterating through the generated Seive 

        // should do

        for( int i = 2; i < 100 ; i ++ )

                if( seive[i] == 0 )

                        printf("%dn", i);

        return 0;

}