计算一个素数的所有可能因数 [英] Calculate all possible factors of a prime
问题描述
正在阅读 Python 教程并遇到一个检查数字是否为素数的示例.我更改了一些内容，以便结果会显示该数字的所有可能因数的列表，如果该数字不是素数，但是代码不起作用.
Was going through a Python Tutorial and came across an example to check whether a number is prime or not. I changed a few things so that the result would display a list of all possible factors of the number, if the number is not a prime, However, the code didn't work.
代码:
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])
我的猜测是控制结构不佳，但有人可以修复我的代码吗?
Poor control structure is my guess, but can someone fix my code?
我了解 range() 是如何工作的:在这种情况下，range() 被赋予一个开始值和一个停止值，步骤默认为 1.我了解继续，继续循环，但我可以将它与 if 一起使用吗?我认为这是错误的.
I understand how range() works: In this case range() is given a start and a stop value, step defaults to 1. I understand that continue, continues a loop, but can I use it with if? I think that is wrong.
更新
已解决，缩进问题continue 应该用于 for 循环，同上 用于 if...notprime.
UPDATE
Solved, problem with indentation the continue should have been for the for loop, ditto for the 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 很愚蠢
Update2: (Thx to @neil)
And the continue is plain stupid
更新了 n/2 和 sqrt(n) 之间的代码和速度比较感谢@neil 和@emmanuel
n/2 代码:v2
Updated Code and speed comparisons between n/2 and sqrt(n)
Thanks to @neil and @emmanuel
n/2 code: 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
使用 sqrt(n)
的素数或因数计算器 v3输入号码:999999
所用时间'，0.0022617399697466567
n/2 代码时间:v2
使用 n/2 的素数或因数计算器 v2
输入号码:999999
所用时间:0.11294955085074321
原始代码时间(n):v1
素数或因数计算器 v1
输入号码:999999
所用时间:0.22059172324972565
v1 和 v2 无法处理数字 999999999、999999999999 和 999999999999999，都给出了 MemoryError
v1 and v2 could not handle numbers 999999999, 999999999999 and 999999999999999, both gave a MemoryError
但是 v3 处理了三个数字:
999999999:0.010536255306192288
999999999999:0.75631930873896636
999999999999999:24.04511104064909
However v3 handled the three numbers:
999999999 : 0.010536255306192288
999999999999 : 0.75631930873896636
999999999999999 : 24.04511104064909
shell 挂起 9999999999999999 并为 999999999999999999 提供 MemoryError
The shell hangs for 9999999999999999 and gives a MemoryError for 999999999999999999
感谢@Lennart，我正在考虑通过使用类以更 OOP 友好的方式重写代码.但我似乎做得不对.
Thanks to @Lennart, I am thinking of rewriting the code in a more OOP friendly way, by using classes. But I don't seem to be doing it right.
推荐答案
问题在于缩进 - if notprime==1: 不应该在 for 循环中.它应该只有一级缩进.
The problem is your indentation - if notprime==1: shouldn't be within the for loop. It should only have one level of indentation.
此外，continue 是不必要的.
你可以做的一个改进(我昨晚只是在研究欧拉项目问题的素数)是只循环到 n/2 - 因子不能大于数字的一半.
An improvement you can make (I was just working on primes last night for a Project Euler problem) is to only loop to n/2 - there can't be a factor greater than half the number.
这篇关于计算一个素数的所有可能因数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
