[問題] 快速質因數分解的方法
看板Prob_Solve (計算數學 Problem Solving)作者flere (人間失格)時間12年前 (2012/02/07 14:25)推噓4(4推 0噓 21→)留言25則, 10人參與討論串1/1
想請問一下
如果我有一個數N想質因數分解,N<10^14
藉此得到N的因數可能個數
所以我先建質數表到10^7
發現約有10^6個質數
這樣去做質因數分解的話
如果有一個質數非常靠近10^14
我就每次都必須把10^6個質數全部test完才可以結束
如果資料裡有很多這種數的話處理時間肯定非常慢
請問有比較快的質因數分解方法,或是可以快速判斷這個數就是質數的方法嗎??
畢竟表我沒辦法建到10^14這麼大> <
謝謝: )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.200.13
→
02/07 15:34, , 1F
02/07 15:34, 1F
推
02/07 16:02, , 2F
02/07 16:02, 2F
推
02/07 16:03, , 3F
02/07 16:03, 3F
→
02/07 16:04, , 4F
02/07 16:04, 4F
→
02/07 16:16, , 5F
02/07 16:16, 5F
推
02/07 20:12, , 6F
02/07 20:12, 6F
→
02/07 20:12, , 7F
02/07 20:12, 7F
→
02/07 20:14, , 8F
02/07 20:14, 8F
→
02/07 20:15, , 9F
02/07 20:15, 9F
→
02/07 20:16, , 10F
02/07 20:16, 10F
→
02/07 22:22, , 11F
02/07 22:22, 11F
原來如此XDDD
因為寫了一題質因數分解的
但是TLE到現在OAO所以才想說是不是有比較快的辦法: P
感謝大家: )
※ 編輯: flere 來自: 140.114.200.13 (02/07 23:28)
→
02/08 01:39, , 12F
02/08 01:39, 12F
→
02/08 03:17, , 13F
02/08 03:17, 13F
→
02/08 08:09, , 14F
02/08 08:09, 14F
→
02/08 13:18, , 15F
02/08 13:18, 15F
→
02/08 13:19, , 16F
02/08 13:19, 16F
→
02/08 13:20, , 17F
02/08 13:20, 17F
→
02/08 19:32, , 18F
02/08 19:32, 18F
因為我見到3e7,只能在zerojudge上過而已
而且還跑了2.多秒
在uva也想開到3e7有什麼好方法嗎??
基本上我都是寫
for(i=2~N)
if(i is prime)
for(j=2*i~N,j+=i)
j不是質數
很普通的去建表而已OAO
※ 編輯: flere 來自: 140.114.200.13 (02/08 20:02)
→
02/08 20:10, , 19F
02/08 20:10, 19F
→
02/10 13:24, , 20F
02/10 13:24, 20F
→
02/10 16:30, , 21F
02/10 16:30, 21F
推
02/10 18:12, , 22F
02/10 18:12, 22F
→
02/10 19:40, , 23F
02/10 19:40, 23F
→
02/10 20:52, , 24F
02/10 20:52, 24F
→
02/10 22:18, , 25F
02/10 22:18, 25F
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
