寻找第N个孪生素数

Question

我在试着解决SPOJ上的一个问题。我们需要计算第n个孪生素数对(素数相差2)。N可以大到10^5。我尝试使用筛子进行预计算，我必须筛选到10^8才能得到最大的n个孪生素数，但时间限制很严格(2s)，而且超时。我注意到人们已经在0.00秒内解决了这个问题，所以我在谷歌上到处寻找公式，但没有找到任何有用的东西。有没有人能给我带路？

提前感谢！！

Answer 1

所以基本上，根据Wolfram Alpha的说法，筛选到2000万就足够了。使用Eratosthenes的普通筛子，在odds上，在C++中使用vector<bool> (你使用的是什么语言？)

追踪两个质数就在筛子环内。当你找到一对双胞胎时，把它的下一个素数存储在一个单独的向量中，如果请求一个乱序(比上一个小)的索引(与描述页面上的例子相反)，只需从这个存储中获得素数：

size_t n = 10000000, itop=2236;
vector<bool> s;
vector<int> twins;
s.resize(n, true);
int cnt, k1, k2, p1=3, p2, k=0;
cin >> cnt;
if( cnt-- > 0 )
{
    cin >> k1;
    for( size_t i=1; i < n; ++i )  // p=2i+1
    {
        if( s[i] )
        {
            p2 = 2*i+1;
            if( p2-p1 == 2 ) { ++k; twins.push_back(p1); }
            if( k==k1 )
            { 
                cout << p1 << " " << p2 << endl;
                ......

等。以1.05秒获得接受(在Ideone上为0.18秒)。或者解开逻辑-只需立即预先计算100,000对孪生质数对，然后在单独的循环中访问它们(0.94秒)。

Answer 2

我收到了0.66秒的空调信号。因为，我假设有0.0s的解决方案可以进行更好的优化，然而，我在这里描述我的方法。

我在Sieve of Eratosthenes中使用了一个基本的优化。你知道2是唯一的偶素数，使用它你可以将计算素数的计算时间和内存减少一半。

其次，所有是孪生素数的数都不会是2和3的倍数(因为它们是素数！)因此，这些数字将是6N+1和6N+5的形式(rest不一定是质数)。6N+5 = 6N+6-1 = 6(N+1)-1。因此，可以看出6N+1和6N-1可能是N >= 1的孪生素数。因此，您可以使用之前计算过的素数来预先计算所有这些值。(小写是3 5)

注意:在10^8之前你不需要计算素数，上限要低得多。编辑:如果你愿意，我可以分享我的代码，但如果你自己想出一个解决方案会更好。:)

Answer 3

可以在@ Programming Praxis entry中找到解决此问题的有效算法的描述。还提供了方案和Perl示例代码。