寻找第N个Twin Prime [英] Finding the Nth Twin Prime

问题描述

我正在尝试解决SPOJ上的问题.我们需要计算第n个孪生素数对(素数相差2). n可以大到10 ^ 5.我尝试使用筛子进行预计算，我不得不筛分高达10 ^ 8才能获得最大的n个孪生素数，但是时间限制是严格的(2s)，并且超时.我注意到人们已经在0.00秒内解决了问题，因此我在Google上四处寻找公式，却无济于事.有人可以引导我吗?

I was trying to solve a problem on SPOJ. We are required to calculate the nth twin prime pair( primes differing by 2). n can be as large as 10^5. I tried a precalculation using a sieve, I had to sieve up to 10^8 to get the maximum n twin prime, but the time limit is strict(2s) and it times out. I noticed people have solved it in 0.00 seconds, so i looked around for a formula on google, and couldnt get anything helpful. Could someone please guide me?

提前谢谢！

推荐答案

因此，根据Wolfram Alpha的说法，基本上筛分20,000,000就足够了.在C ++中使用vector<bool>奇怪地使用Eratosthenes的普通筛网(您使用哪种语言使用BTW?).

So basically, sieving up to 20,000,000 is enough, according to Wolfram Alpha. Use plain sieve of Eratosthenes, on odds, with vector<bool> in C++ (what language were you using BTW?).

在筛网循环内跟踪孪生素数.找到双胞胎时，将一对较低的素数存储在单独的向量中，如果请求了无序索引(小于先前的索引)(它们与描述页面上显示的示例相反)，从此存储中获取素数:

Track the twin primes right inside the sieve loop. Store the lower prime of a pair in a separate vector as you find the twins, and if an out-of-order (smaller then previous) index is requested (and they are, contrary to the examples shown on the description page), just get the prime from this storage:

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秒)中访问它们即可.

etc. Got accept with 1.05 sec (0.18 sec on Ideone). Or untangle the logic - just pre-calculate 100,000 twin prime pairs right away, and access them in a separate loop afterwards (0.94 sec).

这篇关于寻找第N个Twin Prime的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！