Python implements a method to decompose a positive integer into prime factors

An example of Python is given to show how to decompose a positive integer into a prime factor. To share for your reference, specific as follows:

Encounter an python programming problem: decompose a positive integer into prime factors. For example, type 90 and print 90=2*3*3*5.

Version 1:

At first, I wrote it without thinking. The result is the following code

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

As a result, when entering the 10-digit number 9876543210, an error was reported:

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

Version 2:

The error in version 1 is because range has too many items, so I want to reduce the items from range. Since, in determining whether a number n is prime, you only need to take the square root of 2 to n, the code for version 2 is as follows:

#! /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): # Add one more 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

That way, you can increase the number a lot without making an error. However, it is also very limited, when entering large Numbers such as 123124324324134334, it will cause insufficient memory, killing the process

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

In order to operate on a larger number, I guess the reason might be that a large list built by range() was built each time during recursive calls, so I wanted to avoid the use of range, so I got version 3:

Version 3:

code

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

Similarly, the operation speed of 123124324324134334 is very fast, and the following results are obtained

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

PS: Here are a few more computing tools for your reference:

Online factorization prime factor calculator tool:
http://tools.ofstack.com/jisuanqi/factor_calc

Online 1 element function (equation) solving calculation tool:
http://tools.ofstack.com/jisuanqi/equ_jisuanqi

Scientific Calculators online Using _ Advanced calculators online calculation:
http://tools.ofstack.com/jisuanqi/jsqkexue

Online calculators _ Standard calculators:
http://tools.ofstack.com/jisuanqi/jsq

For more information about Python, please refer to Python Math Skills Summary, Python Data Structure and Algorithm Tutorial, Python Function Skills Summary, Python String Manipulation Skills Summary, Python Introduction and Advanced Classic Tutorial and Python Files and Directories Manipulation Skills Summary.

I hope this article has been helpful in Python programming.