2021-01-10

Python 程式碼 : 整數因數分解(integer factorization)(質因數分解prime factorization)

  1.  一個整數的質因數一定不會大於該整數。
  2. 建立該整數的所有可能質因數列表
    • 建立一個檢測質數的函式 (chkPrime)
    • 使用質數函式找出小於等於該整數的質因數列表(getPrimeList)
  3. 使用質因數列表找出該整數的所有因數列表(getFactorList)
  4. 改善空間:
    • chkPrime中,2已列入質數,其餘的偶數,不用再測試,一定不是質數
      for i in range(2, n): 可以改成 for i in range(3, n, 2):
    • 如果質因數只有一個,這個整數就是質數,不須再分解計算了。
    • 可質因數分解的整數,不會存在超過該整數一半以上的質因數,
      所以供測試的質因數清單可以再簡化。
    • ... 




沒有留言:

張貼留言