开发者社区> 问答> 正文

将一个正整数分解质因数。例如:输入90,打印出90=2*3*3*5。

将一个正整数分解质因数。例如:输入90,打印出90=233*5。

展开
收起
珍宝珠 2019-11-19 15:28:04 3743 0
2 条回答
写回答
取消 提交回答
  • def is_prime2(num):
        for i in range(2, num):
            if not (num % i):
                return False
        return True
    
    
    def factorization(num):
        if num < 2:
            print('This number should be a positive integer greater than one!')
            return
        elif is_prime2(num):
            print("This number must be composite!")
            return
        else:
            lst = [x for x in range(2, num) if is_prime2(x)]
            str1 = ''
            while int(num) != 1:
                for i in lst:
                    if not num % i:
                        str1 += str(i) + '*'
                        num /= i
        return '*'.join(sorted(str1[:-1].split('*')))
    
    
    if __name__ == '__main__':
        print(factorization(90))
    
    2020-02-02 13:35:09
    赞同 展开评论 打赏
  • 程序分析:对n进行分解质因数,应先找到一个最小的质数k,然后按下述步骤完成:
    (1)如果这个质数恰等于n,则说明分解质因数的过程已经结束,打印出即可。
    (2)如果n<>k,但n能被k整除,则应打印出k的值,并用n除以k的商,作为新的正整数你n,重复执行第一步。
    (3)如果n不能被k整除,则用k+1作为k的值,重复执行第一步。

    程序源代码:

    #!/usr/bin/python
    # -*- coding: UTF-8 -*-
    
    def reduceNum(n):
        print '{} = '.format(n),
        if not isinstance(n, int) or n <= 0 :
            print '请输入一个正确的数字 !'
            exit(0)
        elif n in [1] :
            print '{}'.format(n)
        while n not in [1] : # 循环保证递归
            for index in xrange(2, n + 1) :
                if n % index == 0:
                    n /= index # n 等于 n/index
                    if n == 1:
                        print index
                    else : # index 一定是素数
                        print '{} *'.format(index),
                    break
    reduceNum(90)
    reduceNum(100)
    
    

    以上实例输出结果为:

    90 =  2 * 3 * 3 * 5
    100 =  2 * 2 * 5 * 5
    
    2019-11-19 15:28:38
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载