| 發布者 | 內容列 | Fernando
Just can't stay away
註冊日: 2003-11-09
發表數: 108
高雄
|  階乘質數問題 |  | 咱們今天段考數學考了這麼一題:
100!+1,100!+2,100!+3..............100!+140,
這140個連續的自然數中,有幾個是質數?
請問要怎麼算阿? |
| | 2003-11-25 20:28 |  | chf0523
Just can't stay away
註冊日: 2003-08-11
發表數: 87
台南
| | Re: 階乘質數問題 | | =============================
咱們今天段考數學考了這麼一題:
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 個 !
_________________
孩子們, 別再問我為何每天都穿 KAPPA 了! 
|
| | 2003-11-26 00:29 |  | 訪客
| | Re: 階乘質數問題 | | 這個題目可能是超越我們的計算能力，
我們只能保證1,2,3,....100不是100!+1，但無法保證
它沒有大於100的因數。
101,103,107,109,113,127,131,137,139 亦然。
例如6！+1 =721 可被7整除。
這一題請建中吳孟軒同學用電腦檢驗一下吧！
孫文先敬上
|
| | 2003-11-26 08:59 | | galois5
Just can't stay away
註冊日: 2003-11-08
發表數: 86
|  Re: 階乘質數問題 | | 呵呵...
100!+1 是 101 的倍數,
(if p is prime, (p-1)! = -1 (mod p) )
至於其餘9個數，除了直接檢驗，還想不出好方法!!! |
| | 2003-11-26 12:44 | | Fernando
Just can't stay away
註冊日: 2003-11-09
發表數: 108
高雄
| | Re: 階乘質數問題 | | 是阿.段考考的.
但是其餘9個要如何檢驗阿?我用計算機都算到要瘋啦.
不過答案還很好心.他的選項是:不超過10個. |
| | 2003-11-26 19:33 | | 訪客
| | Re: 階乘質數問題 | | 引文:
寫道:
這個題目可能是超越我們的計算能力，
我們只能保證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位的可能性。要是真的如此，就必須試上數千條的橢圓曲線，因此馬上找出質因數的希望恐怕不大。
吳孟軒敬上 |
| | 2004-02-11 22:31 | | Fernando
Just can't stay away
註冊日: 2003-11-09
發表數: 108
高雄
| | Re: 階乘質數問題 | | 辛苦啦.
這真的已經超出我們的計算範圍了.連電腦都要跑那麼久.
這個軟體是可以免費試用的嗎? |
| | 2004-02-12 16:47 | | 訪客
| | Re: 階乘質數問題 | | 引文:
Fernando 寫道:
辛苦啦.
這真的已經超出我們的計算範圍了.連電腦都要跑那麼久.
這個軟體是可以免費試用的嗎?
是的！
這個軟體是可以免費使用的。
此軟體的作者還公佈了原始碼，
有興趣的話可以參考看看。
(註：昨天我寫 "每個數都只花了不到10秒的時間，試了不到10條的橢圓曲線就順利把質因數找到了"，並不代表測試任何一條橢圓曲線都只需要1秒。如果繼續試驗下去，每條橢圓曲線的執行時間而逐漸增加。例如第500條橢圓曲線大約要花4分鐘，第3141592條大約要花2小時。) |
| | 2004-02-12 22:06 | | galois5
Just can't stay away
註冊日: 2003-11-08
發表數: 86
| | | 2004-02-13 10:42 | | 訪客
| | Re: 階乘質數問題 | | 賀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-16 21:39 | |
|
