Python质数检查器
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18833759/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python Prime number checker
提问by Chris
I have been trying to write a program that will take an inputed number, and check and see if it is a prime number. The code that I have made so far works perfectly if the number is in fact a prime number. If the number is not a prime number it acts strange. I was wondering if anyone could tell me what the issue is with the code.
我一直在尝试编写一个程序，该程序将输入一个数字，然后检查它是否是质数。如果数字实际上是素数，我到目前为止编写的代码可以完美运行。如果该数字不是质数，则它的行为很奇怪。我想知道是否有人可以告诉我代码有什么问题。
a=2
num=13
while num > a :
if num%a==0 & a!=num:
print('not prime')
a=a+1
else:
print('prime')
a=(num)+1
the result given when 24 is inputed is: not prime not prime not prime prime
输入24时给出的结果是：不是素数不是素数不是素数
How would i fix the error with the reporting prime on every odd and not prime for every even
我将如何通过报告每个奇数的素数而不是每个偶数的素数来解决错误
采纳答案by Steven Rumbalski
You need to stop iterating once you know a number isn't prime. Add a breakonce you find prime to exit the while loop.
一旦你知道一个数字不是质数，你就需要停止迭代。添加一个break一旦你找到prime退出while循环。
Making only minimal changes to your code to make it work:
只需对代码进行最少的更改即可使其正常工作：
a=2
num=13
while num > a :
if num%a==0 & a!=num:
print('not prime')
break
i += 1
else: # loop not exited via break
print('prime')
Your algorithm is equivalent to:
你的算法相当于：
for a in range(a, num):
if a % num == 0:
print('not prime')
break
else: # loop not exited via break
print('prime')
If you throw it into a function you can dispense with breakand for-else:
如果你把它扔到一个函数中，你可以省去break和 for-else：
def is_prime(n):
for i in range(3, n):
if n % i == 0:
return False
return True
Even if you are going to brute-force for prime like this you only need to iterate up to the square root of n. Also, you can skip testing the even numbers after two.
即使你要像这样对素数进行蛮力，你也只需要迭代到 的平方根n。此外，您可以跳过测试两个之后的偶数。
With these suggestions:
有了这些建议：
import math
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
Note that this code does not properly handle 0, 1, and negative numbers.
请注意，此代码不能正确处理0，1和负数。
We make this simpler by using allwith a generator expression to replace the for-loop.
我们通过使用all生成器表达式来替换 for 循环，使这变得更简单。
import math
def is_prime(n):
if n % 2 == 0 and n > 2:
return False
return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2))
回答by Destructor
def isprime(n):
'''check if integer n is a prime'''
# make sure n is a positive integer
n = abs(int(n))
# 0 and 1 are not primes
if n < 2:
return False
# 2 is the only even prime number
if n == 2:
return True
# all other even numbers are not primes
if not n & 1:
return False
# range starts with 3 and only needs to go up
# the square root of n for all odd numbers
for x in range(3, int(n**0.5) + 1, 2):
if n % x == 0:
return False
return True
Taken from:
取自：
回答by Ofir Israel
Your problem is that the loop continues to run even thought you've "made up your mind" already. You should add the line breakafter a=a+1
您的问题是即使您已经“下定决心”，循环仍在继续运行。您应该在break之后添加该行a=a+1
回答by Prashant Kumar
After you determine that a number is composite (not prime), your work is done. You can exit the loop with break.
在您确定一个数是合数（不是质数）后，您的工作就完成了。您可以使用 退出循环break。
while num > a :
if num%a==0 & a!=num:
print('not prime')
break # not going to update a, going to quit instead
else:
print('prime')
a=(num)+1
Also, you might try and become more familiar with some constructs in Python. Your loop can be shortened to a one-liner that still reads well in my opinion.
此外，您可能会尝试更加熟悉 Python 中的某些结构。您的循环可以缩短为单行，在我看来仍然很好读。
any(num % a == 0 for a in range(2, num))
回答by kindall
The two main problems with your code are:
您的代码的两个主要问题是：
- After designating a number not prime, you continue to check the rest of the divisors even though you already know it is not prime, which can lead to it printing "prime" after printing "not prime". Hint: use the `break' statement.
- You designate a number prime before you have checked all the divisors you need to check, because you are printing "prime" insidethe loop. So you get "prime" multiple times, once for each divisor that doesn't go evenly into the number being tested. Hint: use an
elseclause with the loop to print "prime" only if the loop exits without breaking.
- 在指定一个数不是素数后，即使您已经知道它不是素数，您也继续检查其余的除数，这可能导致它在打印“非素数”后打印“素数”。提示：使用‘break’语句。
- 在检查所有需要检查的除数之前指定一个数素数，因为您在循环内打印“素数” 。因此，您多次获得“质数”，对于每个不均匀进入被测试数字的除数一次。提示：
else仅当循环退出而没有中断时，才在循环中使用子句打印“prime”。
A couple pretty significant inefficiencies:
几个非常显着的低效率：
- You should keep track of the numbers you have already found that are prime and only divide by those. Why divide by 4 when you have already divided by 2? If a number is divisible by 4 it is also divisible by 2, so you would have already caught it and there is no need to divide by 4.
- You need only to test up to the square root of the number being tested because any factor larger than that would need to be multiplied with a number smaller than that, and that would already have been tested by the time you get to the larger one.
- 您应该跟踪已经找到的质数，并且只能除以这些数。既然已经除以 2，为什么还要除以 4？如果一个数能被 4 整除，它也能被 2 整除，所以你已经抓住了它，不需要被 4 整除。
- 您只需要测试到被测试数字的平方根，因为任何大于该数字的因子都需要乘以一个小于该数字的数字，而在您获得更大的数字时，该数字已经被测试过了。
回答by CodingOcean
This would do the job:
这将完成这项工作：
number=int(raw_input("Enter a number to see if its prime:"))
if number <= 1:
print "number is not prime"
else:
a=2
check = True
while a != number:
if number%a == 0:
print "Number is not prime"
check = False
break
a+=1
if check == True:
print "Number is prime"
回答by Francis Mujjuni
a=input("Enter number:")
def isprime():
total=0
factors=(1,a)# The only factors of a number
pfactors=range(1,a+1) #considering all possible factors
if a==1 or a==0:# One and Zero are not prime numbers
print "%d is NOT prime"%a
elif a==2: # Two is the only even prime number
print "%d is prime"%a
elif a%2==0:#Any even number is not prime except two
print "%d is NOT prime"%a
else:#a number is prime if its multiples are 1 and itself
#The sum of the number that return zero moduli should be equal to the "only" factors
for number in pfactors:
if (a%number)==0:
total+=number
if total!=sum(factors):
print "%d is NOT prime"%a
else:
print "%d is prime"%a
isprime()
回答by saegarde
This is a slight variation in that it keeps track of the factors.
这是一个微小的变化，因为它跟踪因素。
def prime(a):
list=[]
x=2
b=True
while x<a:
if a%x==0:
b=False
list.append(x)
x+=1
if b==False:
print "Not Prime"
print list
else:
print "Prime"
回答by Keisuke URAGO
This example is use reduce(), but slow it:
这个例子是使用reduce()，但速度很慢：
def makepnl(pnl, n):
for p in pnl:
if n % p == 0:
return pnl
pnl.append(n)
return pnl
def isprime(n):
return True if n == reduce(makepnl, range(3, n + 1, 2), [2])[-1] else False
for i in range(20):
print i, isprime(i)
It use Sieve Of Atkin, faster than above:
它使用Sieve Of Atkin，比上面更快：
def atkin(limit):
if limit > 2:
yield 2
if limit > 3:
yield 3
import math
is_prime = [False] * (limit + 1)
for x in range(1,int(math.sqrt(limit))+1):
for y in range(1,int(math.sqrt(limit))+1):
n = 4*x**2 + y**2
if n<=limit and (n%12==1 or n%12==5):
# print "1st if"
is_prime[n] = not is_prime[n]
n = 3*x**2+y**2
if n<= limit and n%12==7:
# print "Second if"
is_prime[n] = not is_prime[n]
n = 3*x**2 - y**2
if x>y and n<=limit and n%12==11:
# print "third if"
is_prime[n] = not is_prime[n]
for n in range(5,int(math.sqrt(limit))):
if is_prime[n]:
for k in range(n**2,limit+1,n**2):
is_prime[k] = False
for n in range(5,limit):
if is_prime[n]: yield n
def isprime(n):
r = list(atkin(n+1))
if not r: return False
return True if n == r[-1] else False
for i in range(20):
print i, isprime(i)
回答by Sakti Rout
Prime number check.
质数检查。
def is_prime(x):
if x < 2:
return False
else:
if x == 2:
return True
else:
for i in range(2, x):
if x % i == 0:
return False
return True
x = int(raw_input("enter a prime number"))
print is_prime(x)
