Вот код ниже (ответ на CP qs)
Ограничение по времени для выполнения составляет 6 секунд, но мой код медленнее, чем.
Как я могу сделать его более эффективным с точки зрения памяти и времени?
Ввод: ввод начинается с количества t тестов в одной строке (t ‹= 10).
В каждой из следующих t строк находятся по два числа m и n (1 ‹= m ‹= n ‹= 1000000000< /strong>, нм ‹= 100000), разделенных пробелом.
Выходные данные: для каждого теста выведите все простые числа p такие, что m ‹= p ‹= n, по одному числу в строке, тесты разделены пустой строкой.
#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;
}
j
› 2. Проверяйте отдельно 2, а затем начинайте циклj
с 3 и шага 2. - person rossum   schedule 20.06.2020t
. Следовательно, нет необходимости сохранять все эти значения, предложите простой цикл, уменьшающийt
до 0, а тело цикла должно работать только с двумя последними значениями, считанными из ввода. Кроме того, функции:scanf()
иprintf()
ОЧЕНЬ интенсивно используют ЦП. Предлагайте использовать:getchar_unlocked()
иputchar_unlocked()
- person user3629249   schedule 21.06.2020test[][]
снова и снова и снова `- это пустая трата времени. Предлагайте работать только с двумя входными данными одного тестового примера одновременно. - person user3629249   schedule 21.06.20201000000000
находится в пределахunsigned int
, поэтому не рекомендуется использоватьlong int
- person user3629249   schedule 21.06.202010^9
и вставить результаты в вашу «тестовую» программу какstatic const
данные. Тогда решение проблемы простое: прокручивайте простые данные до тех пор, пока не будет найдено значение, равное начальному значению, затем выведите каждое найденное значение, пока (но не включая) значение не превысит конечное значение. - person user3629249   schedule 21.06.2020stdlib.h
Предлагаю удалить заголовочный файл - person user3629249   schedule 21.06.2020math.h
и вычислитьsqrt(i)
в отдельную переменную, а затем использовать эту отдельную переменную подобно:int sqrt_n = sqrt( n ); for( j=3; j<=sqrt_n; j+=2 )
- person user3629249   schedule 21.06.2020