Получение TLE в hackerearth

Question

Когда я отправляю этот код на hackerearth, я получаю TLE.

Любые предложения, как я могу оптимизировать это Код.

#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;

}

Вот проблема, которую я кодировал для

А как я могу проанализировать этот код и получить Сложность времени.

Answer 1

Есть несколько примитивных способов, таких как этот, например, циклический просмотр нечетных чисел и еще несколько оптимизаций

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 является своего рода over-kill , в вашем случае (если вы не принимаете во внимание ваши требования к памяти), потому что диапазон может быть очень очень большим 1000000, вы можете захотеть использовать какое-то растровое изображение для генерации Seive.

Вот очень слабо написанная идея о том, как создавать и использовать 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("%d\n", i);
        return 0;
}

Answer 2

Ваша checkprime функция занимает много времени выполнения. Он работает для N/2 операций.

Вы выполняете это для всех чисел, поэтому вы выполняете для N*N/2 операций, что слишком много.

Я бы предложил вам использовать лучший метод генерации простых чисел. Взгляните на Сито Эратосфена