现在的位置: 首页 > 软件测试 > 测试技术 > 正文

Python题目解答:输入一个整数N,输出N的所有最小因子

2016年05月03日 测试技术 ⁄ 共 625字 ⁄ 字号 暂无评论 ⁄ 阅读 450 次

题目:输入一个整数N,输出N的所有最小因子,也称素因子

其中,任何一个大于1的数,都可以写成多个素数的乘积,我们把这些素数叫做这个数素因子

例如:

输入:120

输出:2 2 2 3 5

输入:27

输出:3 3 3

 

python求解素因子代码如下:

# -*- coding:utf-8 -*-

def isprime(num):
    count = num / 2
    while count >1:
        if num % count == 0:
            return False
            break
        else:
            count -= 1
    else:
        return True

def getfactor(num):
    l = []
    if isprime(num):
        return [num]
    count = num / 2
    for n in range(2, count + 1):
        if num % n == 0 and isprime(n):
            l.append(n)
    return l

def primecal(num):
    fac = getfactor(num)
    mul = 1
    for n in fac:
        mul *= n
    if mul == num:
        return fac
    else:
        return fac + primecal(num / mul)

if __name__ == '__main__':
    num=int(raw_input('Please input a number:\r\n'))
    print sorted(primecal(num))

执行结果示例:

Please input a number:
120
[2, 2, 2, 3, 5]

给我留言

留言无头像?