寻找Nth Twin Prime

Question

我试图解决SPOJ上的问题.我们需要计算第n个孪生素数对(素数相差2).n可以大到10 ^ 5.我尝试使用筛子进行预先计算,我必须筛分至10 ^ 8以获得最大的n孪生素数,但时间限制是严格的(2s)并且它超时.我注意到人们已经在0.00秒内解决了它,所以我在谷歌上寻找一个公式,并没有得到任何帮助.有人可以指导我吗？

提前致谢!!

Answer 1

因此，根据 Wolfram Alpha 的说法，基本上，筛分 2​​0,000,000 个就足够了。在 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 秒）访问它们。