Как я могу избежать TLE на SPOJ с этой программой генератора простых чисел? - PullRequest
Новая
       51

Как я могу избежать TLE на SPOJ с этой программой генератора простых чисел?

0 голосов
/ 04 мая 2020

Это программа генератора простых чисел на SPOJ. Я сталкиваюсь с ужасной ошибкой «Превышен лимит времени». Как я могу преодолеть это? Это ссылка на проблему: - https://www.spoj.com/problems/PRIME1/

В чем может быть причина? Я все еще новичок, и я искал на net, и он говорит мне использовать некоторые алгоритмы, но сейчас я не знаю никаких алгоритмов. 

#include <stdio.h>

void prime(int a,int b)
{
    int y=0;
    for (int i=a;i<=b;i++)
    {
        for (int j=2;j<i;j++)
        {
            int x=i%j;
            if (x==0)
            {
                break;
            }
            else
            {
                y++;
            }
        }
        if (y==i-2)
        {
            printf("%d\n",i);
        }
        y=0;
    }
}

int main()
{
    int test;
    int arr1[11],arr2[11];
    char space[11];
    scanf("%d",&test);

    if (test>10)
    {
        goto end;
    }

    for (int i=0;i<test;i++)
    {
        scanf("%d%c%d",&arr1[i],&space[i],&arr2[i]);
        if (arr1[i]>=1 && arr1[i]<=arr2[i] && arr2[i]<=1000000000 && arr2[i]-arr1[i]<=100000 && space[i]==' ')
        {
            prime(arr1[i],arr2[i]);
            printf("\n");
        }
    }
    printf("\n");
end:
    return 0;
}

Ответы [ 2 ]

2 голосов
/ 05 мая 2020

Вот код, чтобы проверить, является ли число простым числом. Это сложность O (sqrt (N)). Предложенное решение O (N * sqrt (N)) проходит все тестовые случаи как nm <= 100000. </p> 

 bool checkprime(int x){
        if(x==1)
            return false;
        if(x<=3)
            return true;
        for(int i=2;i<=sqrt(x);i++){
            if(x%i==0)
                return false;
        }
        return true;
    }

Некоторый псевдокод для вызова и проверки, является ли число простым. 

for(int i=l;i<=r;i++){
    if(checkprime(i))
        cout<<i<<endl;
    else
        continue;
 }

Однако метод Сегментированное сито эратосфена работает намного быстрее и является лучшим методом для ответа на все запросы.

0 голосов
/ 04 мая 2020

Ваше решение выглядит как квадратичное c, что приведет к превышению времени ожидания для больших чисел. Чтобы сделать его более эффективным, вы можете попробовать другой метод, например Сито Эратосфена

...