[問題] 快速質因數分解的方法

[flere (人間失格)]

想請問一下

如果我有一個數N想質因數分解,N<10^14

藉此得到N的因數可能個數


所以我先建質數表到10^7

發現約有10^6個質數

這樣去做質因數分解的話

如果有一個質數非常靠近10^14

我就每次都必須把10^6個質數全部test完才可以結束

如果資料裡有很多這種數的話處理時間肯定非常慢

請問有比較快的質因數分解方法,或是可以快速判斷這個數就是質數的方法嗎??

畢竟表我沒辦法建到10^14這麼大> <

謝謝: )


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.200.13
→ freef1y3:沒有快速質因數分解方法，不過好像有快速判斷質數的方法
推 suhorng:Pollard-rho algo
推 tjjh89017:快速判斷質數好像是用隨機策略吧
→ suhorng:常見的那種叫 Miller-Rabin
→ flere:謝謝!!!!
推 DJWS:質因數分解的時間複雜度目前還不知道是，也沒有P-time演算法
→ DJWS:判斷質數則是有P-time演算法，叫做AKS Algorithm
→ DJWS:AKS是2002年才發明的第一個P-time演算法，在那之前大多是用
→ DJWS:前面幾位推文所說的方法，雖然都是P-time但不保證答案正確
→ DJWS:(第一句補充)                      是屬於哪一類，
→ kdjf:如果被你找到的話, RSA就不用玩了啊  （天下大亂!!!
原來如此XDDD

因為寫了一題質因數分解的

但是TLE到現在OAO所以才想說是不是有比較快的辦法: P

感謝大家: )
※ 編輯: flere           來自: 140.114.200.13       (02/07 23:28)
→ EdisonX:放 code 上來討論 ?
→ flere:就在剛剛加了cut後終於過了: )
→ suhorng:該不會是ZeroJudge上的題目吧....XD 記得那邊有一系列的
→ flere:是阿XDD不過寫完也都會丟去uva就是了XD
→ flere:就是寫到uva 10290一直不過,zero的是過了,可是uva要開比較
→ flere:小的質數表才會過> <
→ bleed1979:我有寫信給uva說10^6質數表也可以過，不過似乎沒改善。
因為我見到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)
→ firejox:bit array?
→ ilway25:上學期修的課有搞不清楚狀況的助教出分解RSA-100的作業...
→ flere:那是啥??怎麼狀況感覺很好笑XDD
推 suhorng:分解一個100位(十進位)的數字...
→ kdjf:如果那不是兩(幾)個大質數的相乘, 就不是大問題啊XD
→ flere:SOGA~
→ suhorng:可是既然叫RSA不就該恰好是兩個質數的乘積?