33

我一直在尝试编写一个程序，该程序将输入一个数字，并检查它是否是质数。如果这个数字实际上是一个素数，那么我到目前为止所做的代码就可以完美地工作。如果该数字不是素数，它的行为很奇怪。我想知道是否有人可以告诉我代码有什么问题。

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

输入 24 时给出的结果是：不是素数不是素数不是素数

我将如何解决每个奇数报告素数而不是每个偶数素数的错误

4

14 回答 14

70

一旦你知道一个数字不是素数，你就需要停止迭代。break找到素数后添加一个以退出 while 循环。

只需对代码进行少量更改即可使其正常工作：

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')

您的算法等效于：

for a in range(a, num):
    if a % num == 0:
        print('not prime')
        break
else: # loop not exited via break
    print('prime')

如果你把它扔进一个函数中，你可以省去breakfor-else：

def is_prime(n):
    for i in range(3, n):
        if n % i == 0:
            return False
    return True

即使你要像这样对素数进行暴力破解，你也只需要迭代到n. 此外，您可以跳过测试两个之后的偶数。

有了这些建议：

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

请注意，此代码无法正确处理0、1和负数。

我们通过使用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))
于 2013-09-16T17:27:18.680 回答
24 
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

摘自：

http://www.daniweb.com/software-development/python/code/216880/check-if-a-number-is-a-prime-number-python

于 2013-09-16T17:25:33.573 回答
14 
def is_prime(n):
    return all(n%j for j in xrange(2, int(n**0.5)+1)) and n>1
于 2015-06-27T10:49:22.510 回答
10

您的代码的两个主要问题是：

  1. 在指定一个非质数后，即使您已经知道它不是质数，您仍继续检查其余除数，这可能导致它在打印“非质数”后打印“质数”。提示：使用“break”语句。
  2. 在检查所有需要检查的除数​​之前指定一个数素数，因为您在循环内打印“素数”。因此，您多次获得“素数”，对于每个未均匀进入被测试数字的除数一次。提示：else仅当循环退出而没有中断时，才使用带有循环的子句打印“prime”。

几个相当显着的低效率：

  1. 您应该跟踪您已经找到的素数并且只除以这些数字。既然已经除以 2，为什么还要除以 4？如果一个数能被 4 整除，那么它也能被 2 整除，所以你已经掌握了它，不需要被 4 整除。
  2. 您只需要测试到被测试数字的平方根，因为任何大于该数字的因子都需要乘以一个小于该数字的数字，并且在您到达较大的数字时已经测试过了。
于 2013-09-16T17:31:23.433 回答
3

这个例子是使用 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)

它使用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)
于 2014-10-30T19:08:39.993 回答
2

您的问题是即使您已经“下定决心”，循环也会继续运行。您应该在break之后添加该行a=a+1

于 2013-09-16T17:25:57.090 回答
1

在您确定一个数字是合数（不是素数）后，您的工作就完成了。您可以使用 退出循环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

此外，您可能会尝试更加熟悉 Python 中的一些结构。您的循环可以缩短为单行，在我看来仍然很好读。

any(num % a == 0 for a in range(2, num))
于 2013-09-16T17:26:34.177 回答
1

初学者在这里，所以请让我知道我是否可以，但我会这样做：

def prime(n):
    count = 0
    for i in range(1, (n+1)): 
         if n % i == 0: 
             count += 1
    if count > 2:
        print "Not a prime"
    else:
        print "A prime"
于 2015-04-22T12:12:27.673 回答
0

这是一个细微的变化，因为它会跟踪这些因素。

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"
于 2014-09-24T17:08:49.103 回答
0 
max=int(input("Find primes upto what numbers?"))
primeList=[]
for x in range(2,max+1):
    isPrime=True
    for y in range(2,int(x**0.5)+1) :
        if x%y==0:
            isPrime=False
            break

    if isPrime:
        primeList.append(x)
print(primeList)
于 2015-02-02T16:43:57.357 回答
0 
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()
于 2014-07-03T15:43:43.627 回答
0

质数检查。

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)
于 2015-01-13T07:08:34.153 回答
0

这将完成这项工作：

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"
于 2014-03-03T07:33:04.507 回答
0 

# is digit prime? we will see (Coder: Chikak)



def is_prime(x):
    flag = False
    if x < 2:
        return False
    else:
        for count in range(2, x):
            if x % count == 0:
                flag = True
                break
        if flag == True:
            return False
        return True

于 2015-09-16T07:56:39.330 回答