作者DreamYeh (天使)
看板puzzle
標題Re: [問題] 質數
時間Thu Jul 12 13:07:07 2012
※ 引述《EIORU ()》之銘言：
: 有一個村子
: 村子裡每間房子的門牌號碼都是質數
: 村長住在第一間 門牌號碼是"2"
: 第二間, 第三間, 門牌號碼是"3","5",...
: 一天 他開始檢查 村子的房子門牌號碼
: 他發現 村子裡門牌號碼加起來 是個質數
: 扣掉村長家門牌號碼 也是個質數
: 請問 這間村子至少有幾棟房子?
假設這一題意思是：
已知某村莊村長門牌是２，且有後面那個加起來是質數性質，那答案就是２間，
即（2,3）
我重看一次題目，目前理解題意是：
已知某村莊，村長家是２、第二間是３、第三間是５
（也就是說不是單純舉例而已XD）
其他還不知道，但有加起來是質數、扣掉村長家也是質數性質
那解答就稍微牽扯到數論了～（雖然只是最簡單的）
簡單想一下就知道，加起來的質數一定是"孿生質數"中比較大的那一個
假設村莊只有四棟房子
第四棟房子號碼假設是x
則很簡單，就是要去找一組孿生質數較大的數，且該數- (2+3+5) 也是質數就好
簡單驗證幾組孿生質數就可發現，x總是3的倍數
比方說設 2+3+5+x = 31 (31是29,31這組孿生質數較大的） => x=21
稍微找一下孿生質數性質就知道，這是必然了，因為孿生質數有這個性質：
大於3的孿生質數可以表示成 (6n - 1, 6n + 1)
10 除以3餘一，跟孿生質數較大數相減，當然一定是三的倍數！
所以四棟不可能
五棟呢？當然也不可能～相加的起來一定是偶數嘛！
那六棟呢？
比方說 (2,3,5,x,y,z)
一開始取x=7,y=11，很快就會發現不可能，為什麼呢？原因同上，細節大家可自己想
取x=7,y=13就ok了！
就是要取孿生質數數組較大的，且較大的-(2+3+5+7+13)也是質數的組合就好
簡單就能發現59,61這組孿生質數合乎條件，事實上你當然可找到無限多組解
在59,61這組解下，村莊所有房子門牌分別為2,3,5,7,13,31
最少即為六棟(#)
--
— 請多指教喔!!
／＼●／＼ ))
(( ／ /▲\ ＼
\\ My Blog:
http://dreamyeh.pixnet.net/blog
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.222.246
1F：推 dreamfire:推天使大大啦！ 07/12 13:21
2F：推 grooving:有學問果然有差 我沒聽過"孿生質數"這種東西 剛剛才自己 07/12 14:07
3F：→ grooving:算半天証明4間不可能… 07/12 14:07
4F：→ cj6u40:板上神人太多讓我壓力好大，PO個題目彷彿隨時會被質問QQ 07/12 14:10
5F：→ squirrel1085:其實不需要聽過孿生質數這名詞 只是用它比較好解釋 07/12 17:09
6F：→ squirrel1085:而(6n - 1, 6n + 1)這個性質 也是可以自己想出來的 07/12 17:10
7F：推 EIORU:門牌是照質數順序的 07/12 18:34
8F：→ DreamYeh:若限定門牌是照質數順序2,3,5,7..且至少三棟 那答案=96 07/12 20:47
9F：→ EIORU:答對了 07/12 20:48
10F：→ stimim:除了暴力算，有其他方法嗎？ 07/12 20:58