Re: [中學] 質數個數問題
※ 引述《aaaasd ()》之銘言：
: 無窮數列: 1 101 10101 1010101 101010101....
: 有幾個是質數
: 請各位高手幫忙 謝謝
1 = 1
101 = 1 + 100
10101 = 1 + 100 + 10000
= 1 + 10^2 + 10^4 = (10^6-1)/(100-1)
= (10^3-1)(10^3+1)/(9*11)
= (999/9)(1001/11)
故非為質數
1010101 = 1 + 100 + 10000 + 1000000 = 1 + 10^2 + 10^4 + 10^6
= (10^8-1)/99
= (10^4+1)(10^4-1)/(9*11)
= 10001 * (9999/99)
故非為質數
推廣
假設為k位數 則k為 1,3,5,7,9,11....
if(k == 4n-1) //3 7 11... n>1 n為自然數
1 + 100 + 100^2 +.... 100^[(k-1)/2]
= 100^[(k+1)/2] - 1 / 99
= 100^(2n) - 1 / 99
= [10^(2n) - 1]/99 * [10^(2n) + 1]
只要n不等於1即可以寫成兩非1整數相乘 故非為質數
else //(k == 4n-3) 5,9.... n>1 n為自然數
= 1 + 100 +100^2 + .... + 100^[(k-1)/2]
= (100^(2n-1) - 1) / 99
= [10^(2n-1)-1] * [10^(2n-1)+1] / 99
= [10^(2n-1)+1]/11 * [10^(2n-1)-1]/9
只要n不等於1即可以寫成兩非1整數相乘 故非為質數
所以
1 X
101 O
10101 X
1010101 X
.......... X
故只有一個是質數
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.79.21
推
08/21 08:23, , 1F
08/21 08:23, 1F
→
08/22 00:29, , 2F
08/22 00:29, 2F
討論串 (同標題文章)