咱們今天段考數學考了這麼一題:
100!+1,100!+2,100!+3..............100!+140,
這140個連續的自然數中,有幾個是質數?
請問要怎麼算阿?
高中

回應

chf0523

2003-11-26 00:29
=============================
咱們今天段考數學考了這麼一題:
100!+1,100!+2,100!+3..............100!+140,
這140個連續的自然數中,有幾個是質數?
請問要怎麼算阿?
=============================

100! = 1*2*3*4*5*......*99*100

100!+1 = 1 ( 2*3*4*5*......*99*100 + 1 ) 是質數
(因為任何一個 100 以內的質數都無法整除它)

100!+2 = 2 ( 1*3*4*5*......*99*100 + 1 ) 非質數 (2 的倍數)

100!+3 = 3 ( 1*2*4*5*......*99*100 + 1 ) 非質數 (3 的倍數)

100!+4 = 4 ( 1*2*3*5*......*99*100 + 1 ) 非質數 (4 的倍數)

...........

100!+100 = 100 ( 1*2*3*4*......*99 + 1 ) 非質數 (100 的倍數)

至於 100! + 101 呢 ? 那就看 101 是不是質數囉 !

(例如: 100!+111 = 100!+3*37 是 3 或 37 的倍數, 那就非質數了 !)

所以 只要看 101 ~ 140 有幾個質數, 再加上 100!+1 的那一個

應該就是答案了吧 !

經過我檢驗的結果 , 共有九個 : 101,103,107,109,113,127,131,137,139

外加 100!+1 的那一個 , 所以答案應該有 10 個 !

;-)

訪客 (未驗證)

2003-11-26 08:59
這個題目可能是超越我們的計算能力，
我們只能保證1,2,3,....100不是100!+1，但無法保證
它沒有大於100的因數。
101,103,107,109,113,127,131,137,139 亦然。
例如6！+1 =721 可被7整除。
這一題請建中吳孟軒同學用電腦檢驗一下吧！
孫文先敬上

galois5

2003-11-26 12:44
呵呵...
100!+1 是 101 的倍數,
(if p is prime, (p-1)! = -1 (mod p) )

至於其餘9個數，除了直接檢驗，還想不出好方法!!!

Fernando

2003-11-26 19:33
是阿.段考考的.
但是其餘9個要如何檢驗阿?我用計算機都算到要瘋啦.
不過答案還很好心.他的選項是:不超過10個.

訪客 (未驗證)

2004-02-11 22:31
引用：

寫道:
這個題目可能是超越我們的計算能力，
我們只能保證1,2,3,....100不是100!+1，但無法保證
它沒有大於100的因數。
101,103,107,109,113,127,131,137,139 亦然。
例如6！+1 =721 可被7整除。
這一題請建中吳孟軒同學用電腦檢驗一下吧！
孫文先敬上


檢驗結果：沒有一個是質數。
首先是100!+1這個數，
根據Wilson定理，
因101為質數，
所以100!+1可被101整除。
而其餘幾個數，
根據http://www.alpertron.com.ar/ECM.HTM
因式分解軟體利用橢圓曲線法檢驗的結果如下：
100!+101可被53,611整除
100!+103可被2,186,532,582,953整除
100!+107可被157整除
100!+109可被197整除
100!+127可被12,239整除
100!+131可被191整除
100!+137可被40,492,295,047整除
100!+139可被431整除
至於100!+113，目前只能確定不是質數，但尚未找到確切的質因數。上面列出的八個數，最小質因數都不超過13位，每個數都只花了不到10秒的時間，試了不到10條的橢圓曲線就順利把質因數找到了。但100!+113就沒那麼順利了，目前已試了近600條的橢圓曲線，還是無法找到質因數。此軟體依目前的情形來估計，最小質因數超過30位的機率高達80%以上，甚至不排除有質因數超過40位的可能性。要是真的如此，就必須試上數千條的橢圓曲線，因此馬上找出質因數的希望恐怕不大。

吳孟軒敬上

Fernando

2004-02-12 16:47
辛苦啦.
這真的已經超出我們的計算範圍了.連電腦都要跑那麼久.
這個軟體是可以免費試用的嗎?

訪客 (未驗證)

2004-02-12 22:06
引用：

Fernando 寫道:
辛苦啦.
這真的已經超出我們的計算範圍了.連電腦都要跑那麼久.
這個軟體是可以免費試用的嗎?

是的！
這個軟體是可以免費使用的。
此軟體的作者還公佈了原始碼，
有興趣的話可以參考看看。

(註：昨天我寫 "每個數都只花了不到10秒的時間，試了不到10條的橢圓曲線就順利把質因數找到了"，並不代表測試任何一條橢圓曲線都只需要1秒。如果繼續試驗下去，每條橢圓曲線的執行時間而逐漸增加。例如第500條橢圓曲線大約要花4分鐘，第3141592條大約要花2小時。)

galois5

2004-02-13 10:42
嗯...我這有24小時(windows,linux)開機的主機，有興趣可以丟給我，讓他跑跑看...
只怕會 memory overflow...之類的當機，否則在有限時間應該會跑的出來，應該是模仿M質數一般。 ;-)
引用：

寫道:
引用：

Fernando 寫道:
辛苦啦.
這真的已經超出我們的計算範圍了.連電腦都要跑那麼久.
這個軟體是可以免費試用的嗎?

是的！
這個軟體是可以免費使用的。
此軟體的作者還公佈了原始碼，
有興趣的話可以參考看看。

(註：昨天我寫 "每個數都只花了不到10秒的時間，試了不到10條的橢圓曲線就順利把質因數找到了"，並不代表測試任何一條橢圓曲線都只需要1秒。如果繼續試驗下去，每條橢圓曲線的執行時間而逐漸增加。例如第500條橢圓曲線大約要花4分鐘，第3141592條大約要花2小時。)

訪客 (未驗證)

2005-06-16 21:39
賀100!+113因式分解圓滿完成!
2005年5月19日下午1點多(台灣時間),在第739條橢圓曲線找到了一個31位質因數(簡稱p31),留下128位的合成數(簡稱c128).
5月30日早上9:35,在第1848條曲線將c128分解為p35與p93的乘積.至此,100!+113的因式分解已全部完成.
雖然這次找到的質因數稍微小了一點,無法列入http://www.alpertron.com.ar/ECMREC.HTM的前20名,但能用ECM法找到這麼大的質因數,已是相當神奇.欲破紀錄者,請挑選其他數字繼續努力分解!
以下是100!+113與其質因式分解的詳細數字:
93 326215 443944 152681 699238 856266 700490 715968 264381 621468 592963 895217 599993 229915 608941 463976 156518 286253 697920 827223 758251 185210 916864 000000 000000 000000 000113 = 7 112503 31324 441033 561552 804277 (Curve 739) x 75898 807952 375460 547686 88986 978389 (Curve 1848) x 172 880584 807577 307753 186847 525978 988451 168610 530512 601449 996709 796854 812046 206042 970755 620121

訪客 (未驗證)

2005-06-30 22:52
Dear 孟軒：
您在史丹佛大學過的還好吧？
很高興又聽到您的回應，您應該是存活下來了。
加油！
今年又有莫立平、呂康豪去MIT，黃紹倫也可能以交換學生去普林斯頓，....，看樣子九章的成員們在學術界越來越熱鬧了。
請告訴我您的e-mail.

孫文先敬上