快捷導(dǎo)航

Python實(shí)現(xiàn)將一個(gè)正整數(shù)分解質(zhì)因數(shù)的方法分析

更新時(shí)間：2017年12月14日 10:23:05 作者：rosboy

這篇文章主要介紹了Python實(shí)現(xiàn)將一個(gè)正整數(shù)分解質(zhì)因數(shù)的方法,結(jié)合實(shí)例形式對(duì)比分析了Python計(jì)算正整數(shù)分解質(zhì)因數(shù)的算法逐步改進(jìn)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Python實(shí)現(xiàn)將一個(gè)正整數(shù)分解質(zhì)因數(shù)的方法。分享給大家供大家參考，具體如下：

遇到一個(gè)python編程聯(lián)系題目：將一個(gè)正整數(shù)分解質(zhì)因數(shù)。例如：輸入90,打印出90=2*3*3*5。

版本一：

開始，沒動(dòng)腦子就開始寫了，結(jié)果如下代碼

#! /usr/bin/python
# 014.py
import math
number = int(raw_input("Enter a number: "))
while number != 1:
  for i in range(1, number + 1):
    if (number % i) == 0 and i != 1:
      number = number / i
      if number == 1:
        print " %d" %i
      else:
        print " %d*" %i,
      break

結(jié)果，輸入9876543210這個(gè)十位數(shù)的時(shí)候，報(bào)錯(cuò)：

Traceback (most recent call last):
File "./014.py", line 8, in <module>
for i in range(1, number + 1):
OverflowError: range() result has too many items

版本二：

版本一報(bào)錯(cuò)是因?yàn)閞ange有了太多的項(xiàng)，于是想著減少range出的list的項(xiàng)。由于，在判斷一個(gè)數(shù)n是否是質(zhì)數(shù)的時(shí)候，只需從2到n的平方根就行了，所以有了版本二，代碼如下：

#! /usr/bin/python
# 014_1.py
import math
number = int(raw_input("Enter a number: "))
list = []
def getChildren(num):
  print '*'*30
  isZhishu = True
  for i in range(2, int(math.sqrt(1 + num)) + 1): #多加個(gè)1
    if num % i == 0 and i != num :
      list.append(i)
      isZhishu = False
      getChildren(num / i)
      break
  if isZhishu:
    list.append(num)
getChildren(number)
print list

這樣，數(shù)字可以增大很多而不至于報(bào)錯(cuò)。但是，也是很有限度的，當(dāng)輸入大數(shù)如 123124324324134334 時(shí)，會(huì)導(dǎo)致內(nèi)存不足，殺死進(jìn)程

Traceback (most recent call last):
File "./014_1.py", line 20, in <module                                            >
    getChildren(number)
File "./014_1.py", line 11, in getChildren
    for i in range(2, int(math.sqrt(1 + num)) + 1):
MemoryError

為了追求能對(duì)更大的數(shù)進(jìn)行操作，猜想原因可能是遞歸調(diào)用時(shí)每次都需要建立一個(gè)很大的由range()建立的list，于是想避免range的使用，于是有了版本三：

版本三：

代碼

#! /usr/bin/python
# 014_1.py
import math
number = int(raw_input("Enter a number: "))
list = []
def getChildren(num):
  print '*'*30
  isZhishu = True
  i = 2
  square = int(math.sqrt(num)) + 1
  while i <= square:
    if num % i == 0:
      list.append(i)
      isZhishu = False
      getChildren(num / i)
      i += 1
      break
    i += 1
  if isZhishu:
    list.append(num)
getChildren(number)
print list

同樣對(duì)123124324324134334 進(jìn)行操作，速度很快，得到如下結(jié)果

Enter a number: 123124324324134334
******************************
******************************
******************************
******************************
******************************
[2, 293, 313, 362107, 1853809L]

PS：這里再為大家推薦幾款計(jì)算工具供大家進(jìn)一步參考借鑒：

在線分解質(zhì)因數(shù)計(jì)算器工具：
http://tools.jb51.net/jisuanqi/factor_calc

在線一元函數(shù)（方程）求解計(jì)算工具：
http://tools.jb51.net/jisuanqi/equ_jisuanqi

科學(xué)計(jì)算器在線使用_高級(jí)計(jì)算器在線計(jì)算：
http://tools.jb51.net/jisuanqi/jsqkexue

在線計(jì)算器_標(biāo)準(zhǔn)計(jì)算器：
http://tools.jb51.net/jisuanqi/jsq

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)學(xué)運(yùn)算技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: