c++ - 质数生成算法

Question

请查看以下内容，看看您是否可以提供建议。

cout << "2" << endl;
cout << "3" << endl;

ofstream of("Primes.txt");

unsigned long prime = 0;
unsigned long i = 1;
for (i = 1; i < 100000; i++)
{
    prime = ((i*2)+(i+1) + (i % 2));
    of << prime << endl;
}
of.close();
return 0;

部分完成的计算第n个素数的公式

第 n 个素数被吐出，但它的所有素数因子也被吐出

如何筛选列表并仅找到素数。

5
7
11
13
17
19
23
25
29
31
35
37
41
43
47
49
53
55
59
61
65
67
71
73
77
79
83
85
89
91
95
97
101
103

好的，我稍微改变了方法 - 我会尝试实现sieve tonight - 我现在要去写信息学测试了，但是这是我对一些素数的新实现。

vector<int> Primes;

bool IsPrime(int q)
{
    for(unsigned int i = 0; i < Primes.size(); i++)
    {
        if(q % Primes[i] == 0)
            return false;
    }
    return true;
}

int main()
{
    Primes.push_back(2);
    cout << "2" << " is prime" << endl;
    for (unsigned int i = 2; i < 1000000000; i++)
    {
        if(IsPrime(i))
        {
            Primes.push_back(i);
            cout << i << " is prime" << endl;
        }
    }
}

好的，这确实给出了素数，但实际上使用了很多内存。并且随着 vector 变长而随时间缓慢增长。

Answer 1

当您查找(小)素数列表时，消除可被素数(2、3、5、7 等)整除的数字是一个不错的主意，但您也应该使用新发现的素数确保该列表仅包含质数(不仅是 2、3、5、7，还包括那些通过的:11、13、17 等)

对于更大的素数(如果数字太大，你就无法计算解释的方式，因为你需要检查从 1 到要检查的数字的几乎所有数字(无论如何，每 4-5 个))，通常的方法是取一个随机的大数并检查它是否通过 Fermats Small Theorem比如说 3、5、7 和 11(IIRC 如果它只通过 3、5、7 和 11，它成为非素数的概率真的不太可能)。

查看 Fermats primality test以获得更多动手解释。