Just for fun——分解一个正

发布时间:2019-10-11 09:02:27编辑:auto阅读(2032)

    Reason

    为什么我要记录这个问题,因为之前面试的时候遇到过,当时自己写的算法不好,所以,在此记录一下

    Answer

    代码是基于python3写的(人生苦短,写算法请用python,web的话请用php ^_^)

    def prime(n):
        l = []
        while n > 1:
            for i in range(2, n + 1):
                if n % i == 0:
                    n = int(n / i)
                    l.append(i)
                    break
        return l
        
        
    print(prime(1020)) # [2, 2, 3, 5, 17]
    

    Explanation

    从最小质数2开始,如果num能被i整除,则num = num / i,不能则i += 1
    这里你可能有疑问,如果一个数被6整除了呢,那么它加入这个list不久不对了嘛?
    但是你应该意识到,被6能整除,它肯定被它的质数整除了,我们是从最小质数开始的

关键字