algorithm - 从随机数数组中识别素数的最快算法是什么？

Question

我有一个随机数数组，我必须从该数组中返回素数。我熟悉 root(n) 解决方案（n 是那个特定的数字而不是数组的大小）。我不能应用 Eratosthenes 的筛子，因为它适用于一定范围内的数字，但这里的数字是完全随机的。

如果我遗漏了什么，请纠正我。提前致谢！

Answer 1

您正在寻找素数测试。您应该能够搜索并找到很多可能性。这是我几年前写的一个答案，可能远远超出您的预期：

查找给定数字是否为素数的最快方法

大多数细节都针对大于 64 位的数字，其中有很多可能的题外话和选择。对于 64 位输入，简单而合理的答案是使用一个小试除法，然后使用一组精心设计的 Miller-Rabin 测试，这些测试给出确定性结果（既不使用随机性，也没有错误的可能性，如果正确实施）。如果您想稍微优化一下，则需要考虑散列集和 BPSW。

附录：如果输入的数量远大于最大输入大小或唯一输入的数量，或者存在某种分布（例如预期许多重复输入），则有些情况可以更快地完成。然后，诸如缓存或生成用于快速查找的位集之类的解决方案可能会更快。输入集的知识有很大帮助。

Answer 2

每个素数都与 6n 相邻（其中 n>=1 ）。

首先检查一个数字是否与 6 的倍数相邻。

如果数字相邻，则对该数字应用素数测试算法。6n 方法的理由： https ://www.youtube.com/watch?v=ZMkIiFs35HQ

Answer 3

如果空间很重要并且您熟悉 c++，则可以使用 bitset 代替 bool，这将提高 8 倍，因为 bool 使用 8 位作为元素，而 bitset 仅使用一位来存储 1 或 0 的值；

const int SIZE = 1000000;
const int LIMIT = sqrt(SIZE)+1;

bitset<SIZE> prime;

void sieve() {
    prime.flip();
    prime[1]=0;
    for(int i=2;i<=LIMIT;i++) {
        if (prime[i])
            for(int j=2*i;j<SIZE;j+=i)
                prime[j]=0;
    }
}

bool isPrime(int n) {
    return prime[n];
}