Python实现将一个正整数分解质因数的方法分析

yipeiwu_com7年前Python基础

本文实例讲述了Python实现将一个正整数分解质因数的方法。分享给大家供大家参考,具体如下:

遇到一个python编程联系题目:将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。

版本一:

开始,没动脑子就开始写了,结果如下代码

#! /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

结果,输入9876543210这个十位数的时候,报错:

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

版本二:

版本一报错是因为range有了太多的项,于是想着减少range出的list的项。由于,在判断一个数n是否是质数的时候,只需从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): #多加个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

这样,数字可以增大很多而不至于报错。但是 ,也是很有限度的,当输入大数如 123124324324134334 时,会导致内存不足,杀死进程

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

为了追求能对更大的数进行操作,猜想原因可能是递归调用时每次都需要建立一个很大的由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

同样对123124324324134334 进行操作,速度很快,得到如下结果

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

PS:这里再为大家推荐几款计算工具供大家进一步参考借鉴:

在线分解质因数计算器工具:
http://tools.jb51.net/jisuanqi/factor_calc

在线一元函数(方程)求解计算工具:
http://tools.jb51.net/jisuanqi/equ_jisuanqi

科学计算器在线使用_高级计算器在线计算:
http://tools.jb51.net/jisuanqi/jsqkexue

在线计算器_标准计算器:
http://tools.jb51.net/jisuanqi/jsq

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数学运算技巧总结》、《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

相关文章

python获取地震信息 微信实时推送

本文实例为大家分享了python获取地震信息微信实时推送的具体代码,供大家参考,具体内容如下 import requests,time from lxml import etree...

python实现名片管理系统

python实现名片管理系统

本文实例为大家分享了python实现名片管理系统的具体代码,供大家参考,具体内容如下 系统需求 程序启动,显示名片管理系统欢迎界面,并显示功能菜单 ******************...

Django框架视图介绍与使用详解

Django框架视图介绍与使用详解

本文实例讲述了Django框架视图介绍与使用。分享给大家供大家参考,具体如下: 视图 视图:即一个python函数,可以叫 视图函数,或者简称 视图,定义在 应用/views.py...

Python中super的用法实例

super 是用来解决多重继承问题的,直接用类名调用父类方法在使用单继承的时候没问题,但是如果使用多继承,会涉及到查找顺序(MRO)、重复调用(钻石继承)等种种问题。总之前人留下的经验就...

OpenCV实现人脸识别

主要有以下步骤: 1、人脸检测 2、人脸预处理 3、从收集的人脸训练机器学习算法 4、人脸识别 5、收尾工作 人脸检测算法: 基于Haar的脸部检测器的基本思想是,对于面部正面大部分区域...