Оптимизация последовательности простых чисел

Question

Оптимизация последовательности простых чисел

Я застрял на вопросах из трудностей среднего уровня практики Codechef с постановкой задачи:

Шридхар хочет сгенерировать некоторые простые числа для своей криптосистемы.
Помоги ему! Ваша задача — сгенерировать все простые числа между двумя данными
чисел

Остальная часть описания, формат ввода / вывода, примеры тестовых примеров по этому вопросу

Проблема с моей реализацией заключается в получении TLE (превышено ограничение по времени), и я хочу решить эту проблему. Можете ли вы указать на любую проблему в моей реализации, я не могу понять ее после нескольких часов пробного запуска.

Включает в себя, директивы и функцию ifPrime

#include<map>
#include<math.h>
#include<stdio.h>
#define LLD long long int
#define REPNE(i,a,b) for(LLD i=a; i<=b; ++i)
#define REPNEI(i,a,b,k) for(LLD i=a; i<=b; i+=k)
using namespace std;

map<LLD, bool> mem;

bool ifPrime ( LLD a ) {
if ( a<2 ) return false;
else if ( a==2 ) return true;
else if ( a%2==0 ) return false;

REPNEI(i,3,sqrt(a),2) {
if ( a%i==0 ) return false;
}

mem[a] = true;
return true;
}

Генерация основной функции

void genPrime ( LLD a, LLD b ) {
REPNE(i,a,b) {
if ( mem.find(i) != mem.end() ) printf("%lld\n", i);
else if ( ifPrime(i) ) printf("%lld\n", i);
} printf("\n");
}

Главный

int main ( ) {
// freopen("input.txt", "r", stdin);

int t; scanf("%d", &t);
REPNE(test, 1, t) {
LLD a, b;
scanf("%lld %lld", &a, &b);

genPrime(a,b);

}
}

Я не могу придумать другого решения этой проблемы, единственный способ, которым я пришел, — это запоминание, а также обработка больших целых чисел. Нужна помощь.

2

algorithm analysis c++

Решение

Другие решения

Вы должны рассмотреть использование std :: unordered_map вместо std :: map. Часто std :: map реализуется с деревьями, а std :: unordered_map с хеш-таблицами. Операции с хеш-таблицами на современных компьютерах обычно выполняются быстрее, чем на деревьях.

0

Источник

Accepted Answer

У подхода есть проблема в том, что он генерирует ключ запоминания, пары значений. Вероятно, они должны быть проверены немедленно, а не сохранять их.

Простое решение состоит в том, чтобы перебрать диапазон m<=x<=n и затем проверьте, простое ли число, используя оптимизированный алгоритм проверки на простые числа, который принимает около (O ((n-m) ^ 1/2)), который является тихим меньше для очень больших чисел.

Основная функция

bool ifPrime ( int n ) {
if ( n==2 ) return true;
else if ( n%2==0 || n<=1 ) return false;
for ( int i=3; i<=sqrt(n); i+=2 ) {
if ( n%i==0 ) return false;
}

return true;
}

а ты главное как

int main ( ) {
int t; scanf("%d", &t);
REPNE(test, 1, t) {
LLD a, b;
scanf("%lld %lld", &a, &b);

REPNE(i,a,b) {
if ( ifPrime(i) ) printf("%lld\n", i);
} printf("\n");
}
}

Я пытался кодировать в соответствии с вашими определениями макросов, надеюсь, это поможет 🙂

3