2010年4月10日 星期六

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題庫目錄
回首頁

沒有留言: