时间戳

首页 > 解决方案 > 在python中使用“for循环”查找数字的素数

python-3.x - 在python中使用“for循环”查找数字的素数

问题描述

我知道如何使用 while 循环来实现这一点，但我需要找出使用 for 循环的解决方案。对于给定的 num = 56，我的代码在输出下方[2, 7, 4]，而正确的答案是[2,2,2,7]。我哪里错了？

def prime_fac(num):
    a = num
    pf = []
    for x in range(2,a):
        if a % x == 0:
            if x == 2 or x == 3:
                pf.append(x)
                a = a//x
            else:
                for y in range(2,x):
                    if (x % y) == 0:
                        break
                else:
                    pf.append(x)
                    a = a // x
        else:
            continue
    if a>1:
        pf.append(a)
    print (f"Prime factors of {num} are {pf}")
number = int(input('Enter a number to find its prime factors: '))
prime_fac(number)

标签： python-3.xfor-loopprime-factoring

解决方案

你的问题是算法，而不是 Python 代码。x您的程序在除法时增加除数a，而不检查 if x**i(i>1) divides a。在您的输出中，最后一个数字表示不止一次除数的所有素数的乘积a。你可以使用PythonTutor 之类的调试器来找出你的程序在哪里没有，你期望什么。

实际上，我只是想给你一些伪代码来改进你的算法，这样你就可以实现算法了。但后来我注意到，伪代码在 Python 中几乎相同：

def prime_fac(num):
    a = num
    pf = []
    #ranges in Python don't include the last element, therefore we need a + 1 to detect also prime numbers
    for x in range(2, a + 1):
        #check if x is divisor and repeat
        while a % x == 0:
            pf.append(x)
            a = a // x

        #all factors found?
        if a == 1:
            #yes, return list with prime factors
            return pf 
        #no, go to next x

现在，您可以尝试提高算法的效率，因为这种策略相当慢。

推荐阅读