Problem 10394 Twin Primes，孿生質數

此題是要找出 p 和 p+2 都是質數的對數，找出前 100000 對就行了，我算過，前 100000 對的孿生質數不超過 18409300。

我用的方法很粗糙，2.252 秒才 AC，依照之前找質數的方法，這裡就不多說了，直接提供 C 語言程式碼如下：

int isPrime[18409300] = {0};
int prime[100001][2] = {0};
int index = 0;
void creat()
{
    int i, j;
    for (i = 3; i < 18409300; i += 2)
    {
        if(!isPrime[i])
        {
            for (j = i + i; j < 18409300; j += i)
                isPrime[j] = 1;
            if (!isPrime[i - 2])
                prime[index][0] = i - 2, prime[index ++][1] = i;
        }
    } 
} 

接著只須在主程式內直接印出即可。

By David.K

p10394題目連結
回ACM題庫目錄
回首頁