Как найти простое число на O (1) времени выполнения

Question

Я получил этот вопрос в интервью

Пожалуйста, предоставьте решение, чтобы проверить, является ли число простым числом, используя цикл из одного - O (1).Вводимое число может быть только от 1 до 10000.

Я сказал, что это невозможно, если вы не сохранили все простые числа до 10000.Теперь я не совсем уверен, был ли мой ответ правильным.Я попытался найти ответ в интернете, и лучше всего мне подошел алгоритм AKS со временем выполнения O ((log n) ^ 6)

Answer 1

это возможно при использовании SoE (Сито Эратосфена) .Его результатом является массив bool s, обычно кодируемый как один бит в массиве BYTE/WORD/DWORD для лучшей плотности хранения.Также обычно сохраняются только нечетные числа, поскольку четные, кроме 2, не являются простыми числами.Обычно истинное значение означает, что оно не простое ....

Поэтому наивный O(1) C ++ код для проверки x будет выглядеть так:

bool SoE[10001]; // precomputed sieve array
int x = 27; // any x <0,10000>

bool x_is_prime = !SoE[x];

если SoE закодирован как 8-битный BYTE массив, вам нужно настроить бит доступа:

BYTE SoE[1251]; // precomputed sieve array ceil(10001/8)
int x = 27; // any x <0,10000>

BYTE x_is_prime = SoE[x>>3]^(1<<(x&7));

для грубой конструкции SoE не O(1) !!!Вот пример, интенсивно использующий его для ускорения моей IsPrime функции:

• Простые числа по Эратосфену быстрее последовательных, чем одновременно?