[中學] Prime factorrization一些問題

看板Math作者 (天下皆有鋼筆)時間10年前 (2015/07/10 09:49), 編輯推噓6(6推 0噓 10→)
留言16則, 9人參與, 最新討論串1/1
我想問一下 質數分解上 例如數字1517 可以被37 41整除 我想問一下 有甚麼可以推薦的方法嗎? -- " Memory is when Something Happens, and does not completely Unhappen " 百代過客未能磨盡之事 是為回憶 -Edward DeBono -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.189.129.140 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1436492960.A.66B.html
推
07/10 11:31, , 1F
你問了個頗難的問題ow o
07/10 11:31, 1F
推
07/10 11:54, , 2F
這問題是連電腦程式都還不知道有沒有夠快的方法能解
07/10 11:54, 2F
→
07/10 11:55, , 3F
人腦的話試除說不定還容易做一點
07/10 11:55, 3F
推
07/10 12:12, , 4F
先抽出不是質數的部分?
07/10 12:12, 4F
→
07/10 12:44, , 5F
初等方法: 考慮所有小於根號1517的質數..
07/10 12:44, 5F
→
07/10 12:46, , 6F
general number field sieve?
07/10 12:46, 6F
→
07/10 12:47, , 7F
quadratic sieve?
07/10 12:47, 7F
→
07/10 17:16, , 8F
Shor's algorithm! （拖走
07/10 17:16, 8F
推
07/10 17:19, , 9F
先開平方根 然後土法煉鋼...
07/10 17:19, 9F
→
07/11 15:59, , 10F
NPC
07/11 15:59, 10F
推
07/12 20:46, , 11F
這個問題好像還沒被證明是 NPC 的樣子?
07/12 20:46, 11F
→
07/12 20:48, , 12F
如果是 NPC 的話那量子電腦的用途會更廣泛
07/12 20:48, 12F
→
07/12 20:54, , 13F
只已知是 NP∩co-NP, 這裡的東西很有可能比NPC還難
07/12 20:54, 13F
→
07/12 20:55, , 14F
因為這玩意要是 NPC 那就有 NP = co-NP 了
07/12 20:55, 14F
推
07/13 11:32, , 15F
我的理解 NPC 已經是 NP 裡面最難的了
07/13 11:32, 15F
→
07/13 11:32, , 16F
所以如果在 NP 裡面應該不會比 NPC 難?
07/13 11:32, 16F
‣ 更多 Kare112233 的文章
文章代碼(AID): #1LdoIWPh (Math)