Учитывая, что входные данные могут быть до 1000000000, как я могу написать программу, эффективную по времени и памяти? (выведите все простые числа от m до n) - PullRequest
Новая
       127

Учитывая, что входные данные могут быть до 1000000000, как я могу написать программу, эффективную по времени и памяти? (выведите все простые числа от m до n)

1 голос
/ 20 июня 2020

Вот код ниже (ответ на CP qs)

Ограничение по времени для выполнения составляет 6 секунд, но мой код медленнее, чем.

Как мне сделать больше памяти и эффективное время?

  • Ввод: ввод начинается с числа t тестовых случаев в одной строке ( t <= 10 </strong>).

  • В каждой из следующих строк t есть два числа m и n ( 1 < = m <= n <= 1000000000 </strong>, nm <= 100000 </strong>) через пробел.

  • Вывод: для каждого теста выведите все простые числа p таким образом, что m <= p <= n </strong>, одно число в строке, тестовые примеры разделены пустой строкой. 

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    long int t,m,n,i,j,k;
    //printf("Enter number of testcases:\n");
    scanf("%ld",&t);
    long int test[t][2];
    for(i=0;i<t;i++){
        //printf("Enter m,n:\n");
        scanf("%ld %ld",&test[i][0],&test[i][1]);
    }
    
    for(k=0;k<t;k++){    
        for(i=test[k][0];i<=test[k][1];i++){
            for(j=2;j*j<i*i;j++){
                if(i%j==0)
                    break;
            }
            if(j==i){
                printf("%ld\n",i);
                }
            }
            printf("\n");
    }
    return 0;
}

1 Ответ

3 голосов
/ 20 июня 2020

Используйте сито Эратосфена .

Это сегментированное сито Эратосфена, модифицированное для работы только с одним сегментом, согласно вашим входным данным.

Разница в том, что сегментированное сито проходит по сегментам бесконечно и использует столько простых чисел, сколько необходимо для текущего просеиваемого сегмента (до его квадрат верхнего предела root); здесь предел верхнего сегмента (и, следовательно, основного сегмента) известен заранее.

Основной сегмент простирается до sqrt самого большого значения, которое необходимо учитывать; здесь он указан как 10^9. sqrt(10^9) < 32000, поэтому сегмент ядра охватывает от 0 до 32000 и просеивается простым ситом Эратосфена.

Поскольку у вас несколько прогонов, используйте одно и то же ядро ​​для каждого прогона.

код в связанном ответе легко изменить в соответствии с требованиями этого вопроса: вместо оценки значения top просто используйте n, предоставленное вам во входных данных. above - это то, что здесь называется m.

...