math - 如何在 O(1) 运行时找到素数
问题描述
我在一次采访中得到了这个问题
请提供一个解决方案来检查一个数字是否是一个使用一个循环的素数 - O(1)。输入数字只能在 1 到 10,000 之间。
我说这是不可能的，除非你已经存储了多达 10,000 个素数。现在我不完全确定我的回答是否正确。我试图在互联网上搜索答案，我想出了最好的 AKS 算法，运行时间为 O((log n)^6)
解决方案
使用SoE（埃拉托色尼筛）是可行的。其结果是一个bools 数组，通常编码为数组中的单个位，以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功能的例子：