整数分解成素数的Python代码

功能说明

将整数分解成两个素数的乘积。

代码实现（一）

#!/usr/bin/python

import copy

def isPrime(n):
    if n <= 1: return False
    if n <= 3: return True
    for i in range(2, n/2):
        if n % i == 0:
            return False
    return True

def calcAllPrimesInRange(begin, end):
    primes = []
    for i in range(begin, end):
        if isPrime(i):
            primes.append(i)
    return primes

def decomposeNumber(n, maxFactor):
    isFound = False
    primes = calcAllPrimesInRange(2, maxFactor)
    rprimes = copy.copy(primes)
    rprimes.reverse()
    for i in primes:
        for j in rprimes:
            if i * j < n:
                break;
            if i * j == n:
                isFound = True
                print("%s = %s * %s" % (n, i, j))
                break;
        if isFound:
            break;

    if not isFound:
        print("number(%s) factors is NOT found in [0, %s]." % (n, maxFactor))

decomposeNumber(707829217, 1000)
decomposeNumber(707829217, 10000)
decomposeNumber(707829217, 100000)

输出结果

seewin@seewin:~$ python DecomposeNumber.py 
number(707829217) factors is NOT found in [0, 1000].
number(707829217) factors is NOT found in [0, 10000].
707829217 = 8171 * 86627

代码实现（二）

#!/usr/bin/python

import copy

def isPrime(n):
    if n <= 1: return False
    if n <= 3: return True
    for i in range(2, n/2):
        if n % i == 0:
            return False
    return True

def decomposeNumber(n, maxFactor):
    isFound = False
    for i in range(2, maxFactor):
        if not isPrime(i): continue
        if n % i != 0: continue
        j = n / i
        if not isPrime(j): continue
        isFound = True
        print("%s = %s * %s" % (n, i, j))
        break;

    if not isFound:
        print("number(%s) factors is NOT found in [0, %s]." % (n, maxFactor))

decomposeNumber(707829217, 1000)
decomposeNumber(707829217, 10000)
decomposeNumber(707829217, 100000)

输出结果

seewin@seewin:~$ python DecomposeNumber2.py 
number(707829217) factors is NOT found in [0, 1000].
707829217 = 8171 * 86627
707829217 = 8171 * 86627

分析对比

版本二避免了冗余的素数查找，比版本一更高效。