質因數分解算法 - 台部落

質因數分解算法. 原創 涯若 2020-06-30 02:01. 每個合數都可以寫成幾個質數相乘的形式，這幾個質數就都叫做這個合數的質因數。

如果一個質數是某個數的因數，那麼就說 ... 請輸入正確的登錄賬號或密碼 註冊 忘記密碼 首頁 算法 正文 質因數分解算法 原創 涯若 2020-06-3002:01 每個合數都可以寫成幾個質數相乘的形式，這幾個質數就都叫做這個合數的質因數。

如果一個質數是某個數的因數，那麼就說這個質數是這個數的質因數。

而這個因數一定是一個質數。

質因數（或質因子）在數論裏是指能整除給定正整數的質數。

兩個沒有共同質因子的正整數稱爲互質。

因爲1沒有質因子，1與任何正整數（包括1本身）都是互質。

正整數的因數分解可將正整數表示爲一連串的質因子相乘，質因子如重複可以指數表示。

根據算術基本定理，任何正整數皆有獨一無二的質因子分解式。

只有一個質因子的正整數爲質數。

就是一個數的約數，並且是質數，比如8=2×2×2，2就是8的質因數。

12=2×2×3，2和3就是12的質因數。

把一個式子以12=2×2×3的形式表示，叫做分解質因數。

16=2×2×2×2,2就是16的質因數， 把一個合數寫成幾個質數相乘的形式表示，這也是分解質因數。

分解質因數的方法是先用一個合數的最小質因數去除這個合數，得出的數若是個質數，就寫成這個合數相乘形式；若是一個合數就繼續按原來的方法，直至最後是一個質數。

分解質因數的有兩種表示方法，除了大家最常用知道的“短除分解法”之外，還有一種方法就是“塔形分解法”。

分解質因數對解決一些自然數和乘積的問題有很大的幫助，同時又爲求最大公約數和最小公倍數做了重要的鋪墊。

計算方法 短除法 求一個數分解質因數，要從最小的質數除起，一直除到結果爲質數爲止。

分解質因數的算式的叫短除法，和除法的性質差不多，還可以用來求多個個數的公因式：求最大公因數的一種方法，也可用來求最小公倍數。

求幾個數最大公因數的方法，開始時用觀察比較的方法，即：先把每個數的因數找出來，然後再找出公因數，最後在公因數中找出最大公因數。

12與18都可以分成幾種形式不同的乘積，但分成質因數連乘積就只有以上一種，而且不能再分解了。

所分出的質因數無疑都能整除原數，因此這些質因數也都是原數的約數。

從分解的結果看，12與18都有公約數2和3，而它們的乘積2×3=6，就是 12與18的最大公約數。

採用分解質因數的方法，也是採用短除的形式，只不過是分別短除，然後再找公約數和最大公約數。

如果把這兩個數合在一起短除，則更容易找出公約數和最大公約數。

從短除中不難看出，12與18都有公約數2和3，它們的乘積2×3=6就是12與18的最大公約數。

與前邊分別分解質因數相比較，可以發現：不僅結果相同，而且短除法豎式左邊就是這兩個數的公共質因數，而兩個數的最大公約數，就是這兩個數的公共質因數的連乘積。

實際應用中，是把需要計算的兩個或多個數放置在一起，進行短除。

在計算多個數的最小公倍數時，對其中任意兩個數存在的約數都要算出，其它無此約數的數則原樣落下。

最後把所有約數和最終剩下無法約分的數連乘即得到最小公倍數。

JohnM.Pollard提出了第二種因數分解的方法，PollardRho快速因數分解。

該算法時間複雜度爲O（n^(1/4)）。

分解質因數代碼： 將一個正整數分解質因數。

例如：輸入90,打印出90=2*3*3*5。

  程序分析：對n進行分解質因數，應先找到一個最小的質數k，然後按下述步驟完成：  (1)如果這個質數恰等於n，則說明分解質因數的過程已經結束，打印出即可。

  (2)如果n<>k，但n能被k整除，則應打印出k的值，並用n除以k的商,作爲新的正整數你n,  重複執行第一步。

  (3)如果n不能被k整除，則用k+1作爲k的值,重複執行第一步。

http://www.tuicool.com/articles/Frm6fy 算法 發表評論 登录 所有評論 還沒有人評論，想成為第一個評論的人麼?請在上方評論欄輸入並且點擊發布. 相關文章 智慧家庭場景的推薦系統的發展歷程和方向|InfoQ《公開課》 直播概要： 隨着計算機的蓬勃發展，互聯網進入大數據和人工智能時代，爲了解決信息過載和長尾商品，推薦系統成爲唯一選擇，而面對不同的業務場景，爲了解決業務痛點，會根據不同的場景特點尋找不同的方法和手段來解決推薦中實際遇到的問題。

在智慧家庭領域， InfoQ中文站 2021-12-2110:54:01 Alexa全球排名網站將關閉，排名曾引爭議 {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ 辛晓亮 2021-12-1414:53:55 ThinkingAboveCode：TLA+思維概述 {"type":"doc","content":[{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null 李明昊 2021-12-0717:23:58 你的2.6朵雲裏，會有火山引擎嗎？ {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ 张俊宝 2021-12-0710:28:54 數字化轉型這麼火，你真的看懂了嗎？ {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ 张俊宝 2021-12-0221:08:57 基於圖像的機器學習技術將數十億的電子商務產品分爲數千個類別 {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ CelianGossec 2021-11-2916:28:50 如何用PyTorch構建GAN？ {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ a-yingCheng 2021-11-2311:18:54 繞過硬件瓶頸，成倍提升芯片算力，軟件層面深挖芯片性能可行嗎？ {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ 张俊宝 2021-11-2311:18:54 AppAnnie發佈預測：TikTok將達15億活躍用戶，遙遙領先Instagram {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ 闫园园 2021-11-1919:53:55 不是隻有數字化水平高，纔可以落地知識圖譜 {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockq 罗燕珊 2021-11-1115:23:53 科大訊飛在AI源頭技術上的突破，實現系統性創新 {"type":"doc","content":[{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null Lucien 2021-11-0815:13:57 不滿被辭退，一程序員寫爬蟲程序侵入公司後臺刪庫泄憤，造成經濟損失10餘萬元 {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockq 刘燕 2021-11-0814:03:51 “TrojanSource”算法漏洞幾乎影響所有代碼的安全 {"type":"doc","content":[{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null BrianKrebs 2021-11-0518:33:59 谷歌前CEO發出警告：元宇宙對人類未必是好事，AI技術是“僞神” {"type":"doc","content":[{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null 凌敏 2021-11-0214:03:53 騰訊發佈超大預訓練系統派大星，聚焦解決BERT等超大模型訓練時的“GPU內存牆”問題 {"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"typ InfoQ编辑部 2021-11-0213:38:53 涯 涯若 24小時熱門文章 weilksdhkfjsdkfjh 最新文章 閱讀筆記（8） 質因數分解算法 彙編語言Assembly（二） leetcode兩道題 DL&ML基礎學習一 最新評論文章 SpringBoot統一參數校驗、統一異常、統一響應，這纔是優雅的處理方式！ winforminput輸入數值（可以小數，負數） For健康，還在糾結“喫什麼”？答案在這裏！——營養膳食的基礎準則