Python：找到X的最大质数

Question

嘿，亲爱的Python爱好者们，

警告：我刚开始学习编程。好了，既然你们已经被提醒了……

我正在尝试写一个Python文件，目的是找到我在代码中声明的一个变量的最大质数。

这是我的思路：

Step 1:Find Factors of X
Step 2:Put factors of X in an array a
Step 3:Analyze last element of array a
Step 4:Check if last element of array a is Prime
Step 5: if last element of array a is prime print "found the largest prime" along with the number itself, else, analyze second to last element in array a, and so on until at a[1]
Step 6: if no prime numbers in array, print "no primes found"

问题出在最后一个else语句上，当处理x=28和它的因子数组时：[1, 2, 4, 7, 14]，我的代码认为7不是质数……

我的步骤在这里列出了：

#find factors, put them in an array a

#1.Find factors of X
#2.Put factors of X in an array a

x=28
i=1
a=[]
length = 0

while i<x:      
    if x%i == 0:    #checks to see if X is divisible by anything between 1 and X-1
        a.append(i)  #adds factor to array a
    i = i+1         

print "your factors are: ", "\n", a
print "\n"


#3. Analyze the last element in array a
# Before loop below, a = [1, 2, 4, 7, 14] and length = 5

length = 0
length = len(a)
n=a[length-1]-1  
print "checking for primes in your array now...", "\n"

while len(a) > 2:
    if a[length-1]%n != 0:       
        n=n-1
        if n == 1:
            print "PRIME TIME"
            break
    else:
        print a[length-1], "is not a prime"  #added
        del a[-1]
        length = len(a) 
        print "length = ",length
        if length == 2:
            print "NO Primes"

我有几个问题：

• 你们会如何重新给变量x、i、a[]和n赋值，以让代码更容易阅读呢？

• 在第二个循环中，第一次循环后，分析7时，为什么代码不识别它是一个质数呢？

非常感谢你们的建设性反馈！！

Answer 1

好的，我会这样做：

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  
            n /= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

print "Factors: ", primes(28)
print "The largest is: ", max(primes(28))

首先使用 primes 函数，这个函数我从 这里 找到的。它会返回一个数组，里面包含所有的质因数。然后，简单地使用 max-function，这个函数会给你数组中最大的元素。

输出结果如下：

Factors:  [2, 2, 7]
The largest is:  7

希望这能帮到你。