performance - 这是一个好的素性检查解决方案吗？

Question

我编写此代码是为了检查一个数字是否是质数(对于 10^9+7 以内的数字)

这是一个好方法吗？
这个的时间复杂度是多少？

我所做的是创建一个unordered_set，它存储最大到sqrt(n)的素数。
检查一个数是否为素数时，首先检查它是否小于表中的最大数。
如果小于，则会在表中搜索，因此在这种情况下复杂度应为 O(1)。
如果大于，则使用包含素数的数字集合中的数字进行整除测试。

#include<iostream>
#include<set>
#include<math.h>
#include<unordered_set>
#define sqrt10e9 31623

using namespace std;

unordered_set<long long> primeSet = { 2, 3 }; //used for fast lookups

void genrate_prime_set(long range) //this generates prime number upto sqrt(10^9+7)
{
    bool flag;
    set<long long> tempPrimeSet = { 2, 3 }; //a temporay set is used for genration
    set<long long>::iterator j;
    for (int i = 3; i <= range; i = i + 2)
    {
        //cout << i << " ";
        flag = true;
        for (j = tempPrimeSet.begin(); *j * *j <= i; ++j)
        {
            if (i % (*j) == 0)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            primeSet.insert(i);
            tempPrimeSet.insert(i);
        }
    }
}

bool is_prime(long long i,unordered_set<long long> primeSet)
{
    bool flag = true;
    if(i <= sqrt10e9) //if number exist in the lookup table
        return primeSet.count(i);    

    //if it doesn't iterate through the table  

    for (unordered_set<long long>::iterator j = primeSet.begin(); j != primeSet.end(); ++j)
    {
        if (*j * *j <= i && i % (*j) == 0)
        {
            flag = false;
            break;
        }
    }
    return flag;
}
int main()
{
    //long long testCases, a, b, kiwiCount;
    bool primeFlag = true;
    //unordered_set<int> primeNum;
    genrate_prime_set(sqrt10e9);
    cout << primeSet.size()<<"\n";
    cout << is_prime(9999991,primeSet);
    return 0;
}

Answer 1

我认为这并不是完成手头工作的特别有效的方式。

尽管最终可能不会产生太大的影响，但生成达到某个特定限制的所有素数的有效方法显然是使用筛子 - 埃拉托色尼筛子既简单又快速。有一些修改可以更快，但对于您正在处理的小尺寸，它们可能不值得。

这些通常会以比您当前使用的格式更有效的格式生成输出。特别是，您通常只需为每个可能的素数(即每个奇数)指定一位，如果该数字是合数，则最终将其归零，如果是素数，则最终将其归零(当然，如果您愿意，您可以反转含义) )。

由于从 3 到 31623 的每个奇数只需要一位，因此这只需要大约 16 K 位，或大约 2K 字节——按照现代标准来看，这确实是微不足道的内存量(特别是:小到足以适应 L1)缓存很容易)。

由于位是按顺序存储的，因此通过您正在测试的数字的平方根的因子进行计算和测试也很简单，而不是针对表中的所有数字(包括大于平方根的数字)进行测试您正在测试的数字的根，这显然是浪费时间)。这还可以优化对内存的访问，以防某些内存不在缓存中(即，您可以按顺序访问所有数据，使硬件预取器的工作尽可能简单)。

如果您想进一步优化，我会考虑使用筛子来查找 10⁹+7 以内的所有素数，并查找输入。这是否是一个胜利将(很大程度上)取决于您预计收到的查询数量。快速检查表明，埃拉托斯特尼筛法的简单实现可以在大约 17 秒内找到 10⁹ 以内的所有素数。之后，每个查询(当然)基本上是瞬时的(即单次内存读取的成本)。这确实需要大约 120 MB 的内存来存储筛选结果，这曾经是一个主要考虑因素，但(除了相当有限的系统)通常不会再有。