math - 如何在 O(1) 运行时间上查找素数

Question

我在面试中遇到了这个问题

Please provide a solution to check if a number is a prime number using a loop of one - O(1). The input number can be between 1 and 10,000 only.

我说过这是不可能的，除非你已经存储了最多 10,000 个素数。现在我不完全确定我的回答是否正确。我试图在互联网上搜索答案，最好的答案是运行时间为 O((log n)^6) 的 AKS 算法

Answer 1

使用 SoE (Sieve of Eratosthenes) 是可行的.其结果是一个 bool 数组，通常在 BYTE/WORD/DWORD 数组中编码为单个位，以实现更好的存储密度。通常也只有奇数被存储为偶数，除了 2 都不是质数。通常真值意味着它不是素数....

所以用于检查 x 的朴素 O(1) C++ 代码看起来像:

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 函数的例子:

• Prime numbers by Eratosthenes quicker sequential than concurrently?