计算一个质数的所有可能因子

Question

我在学习Python教程的时候，看到一个例子是用来检查一个数字是否是质数。我对代码做了一些修改，想让它显示出所有可能的因子，如果这个数字不是质数的话。但是，代码没有正常工作。

代码：

def isprime(number):
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, number):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
            continue
        if notprime == 1:     
            return number, "is not a prime because of these factors", fnum  
        else:
            return True
num =int(raw_input("Enter number: "))
print isprime(num)

输出：

Enter number: 12
Reticulating Splines...
(12, 'is not a prime because of these factors', [1, 2, 3, 4])
>>> 
Enter number: 25
Reticulating Splines...
(25, 'is a prime number')

预期输出：

Enter number: 12
Reticulating Splines...
(12, 'is not a prime because of these factors', [1, 2, 3, 4, 6])

Enter number: 25
Reticulating Splines...
(25, 'is not a prime because of these factors', [1,5])

我猜是控制结构不太好，但有没有人能帮我修复我的代码？

我明白range()是怎么工作的：在这个例子中，range()有一个开始值和一个结束值，步长默认是1。我知道continue是用来继续循环的，但我可以把它和if一起用吗？我觉得这样用是不对的。

更新
问题解决了，原来是缩进的问题 continue应该是给for循环用的，if...notprime也是一样。

def isprime(number):
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, number):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
    if notprime == 1:     
        return number, "is not a prime because of these factors", fnum  
    else:
        return number, "is a prime number"
num =int(raw_input("Enter number: "))
print isprime(num)

更新2： (感谢@neil)
而且这个continue用得真是太傻了

更新后的代码和n/2与sqrt(n)的速度比较
感谢@neil和@emmanuel
n/2代码：v2

import time
def isprime(number):
    start=time.clock()
    print "Reticulating Splines..."
    fnum=[1,]
    notprime=0
    for p in range(2, (number/2)+1):
        if (number % p) == 0:
            notprime=1
            fnum.append(p)
    end=time.clock()
    if notprime == 1:     
        return number, "is not a prime because of these factors", fnum, "Time taken", end-start  
    else:
        return number, "is a prime number. Time Taken", end-start
print "Prime or factor calculator v2 using n/2"
print #
num =int(raw_input("Enter number: "))
print isprime(num)

sqrt(n)代码：v3

import math, time
def isprime(number):
    start=time.clock()
    print "Reticulating Splines..."
    fnum = [1,]
    last = int(math.ceil(math.sqrt(number)))
    for p in range(2, last + 1):
        if (number % p) == 0:
            fnum.append(p)
            fnum.append(number / p)
    # Remove duplicates, sort list
    fnum = list(set(fnum))
    fnum.sort()
    end=time.clock()
    if len(fnum) > 1:     
        return number, "is not a prime because of these factors", fnum ,"Time taken", end-start 
    else:
        return True, "Time taken", end-start

print "Prime or factor calculator v3 using sqrt(n)"
print #

num =int(raw_input("Enter number: "))

print isprime(num)

输出（只显示时间）

sqrt(n)代码的时间：v3
质数或因子计算器v3使用sqrt(n)
输入数字：999999
耗时：0.0022617399697466567

n/2代码的时间：v2
质数或因子计算器v2使用n/2
输入数字：999999
耗时：0.11294955085074321

原始代码(n)的时间：v1
质数或因子计算器v1
输入数字：999999
耗时：0.22059172324972565

v1和v2无法处理数字999999999、999999999999和999999999999999，都会出现内存错误。

不过v3可以处理这三个数字：
999999999 : 0.010536255306192288
999999999999 : 0.75631930873896636
999999999999999 : 24.04511104064909

对于9999999999999999，终端会卡住，而999999999999999999则会出现内存错误。

感谢@Lennart，我在考虑用更面向对象的方式重写代码，使用类来实现。但我好像没有做到这一点。

Answer 1

你只测试了一个数字就返回了结果。把条件判断和返回结果的部分移到循环外面去。

另外，如果是质数就返回 True，如果不是质数就返回一个字符串，这样做不太实际。因为如果你这样调用：

if isprime(7):

那结果总是会被判断为 True。我对这个做了一些改进：

def factors(number):
    fnum=[]
    for p in range(2, number):
        if (number % p) == 0:
            fnum.append(p)
    return fnum

for x in range(100):
    f = factors(x)
    if f:
        print x, "is not a prime and has factors", f
    else:
        print x, "is a prime"

Answer 2

@neil:

“你可以改进的一个地方是，只循环到 n/2，因为没有一个因子会大于这个数的一半。”

顺便说一下，你需要测试的最大值是 int(math.ceil(math.sqrt(n)))，如果每次得到一个值，你也能得到对应的另一个值，就没必要循环到 n/2 了（也就是说，如果 a x b = n，那么 a 或者 b 一定有一个会小于 n 的平方根，另一个则会大于它）：

def isprime(number):
    print "Reticulating Splines..."
    fnum = [1,]
    last = int(math.ceil(math.sqrt(number)))
    for p in range(2, last + 1):
        if (number % p) == 0:
            fnum.append(p)
            fnum.append(number / p)
    # Remove duplicates, sort list
    fnum = list(set(fnum))
    fnum.sort()
    if len(fnum) > 1:     
        return number, "is not a prime because of these factors", fnum  
    else:
        return True

这样可以提高性能，即使最后列表没有排序（不过这可以在循环中通过将两个数字 p 和 number / p 放到合适的位置来实现）。

Answer 3

问题出在你的缩进上 - if notprime==1: 这行代码不应该放在循环里面。它只需要缩进一个层级。

另外，continue 这个语句是多余的。

补充说明：

你可以做一个改进（我昨晚刚在做与质数相关的项目）就是只循环到 n/2，因为没有任何因子会大于这个数字的一半。