在python中查找质数

Question

我需要写一个代码，它将在一个数字范围内找到所有质数，然后按顺序列出它们，说明哪些是质数，哪些不是质数，如果它们不是质数，则显示它们可以被哪些数字整除。它应该看起来像这样：

>>> Prime(1,10)
1 is not a prime number 
2 is a prime number
3 is a prime number
4 is divisible by 2
5 is a prime number
6 is divisible by 2, 3
7 is a prime number
8 is divisible by 2, 4
9 is divisible by 3

到目前为止，我已经有了这个，它将只识别哪些数字是质数，并将它们打印在一个列表中。我不知道如何计算非质数，也不知道如何打印出能被它整除的数字。我也知道1是一个质数。

def primeNum(num1, num2):
   for num in range(num1,num2):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
       print (num,'is a prime number')

Answer 1

使用筛子可以做到这一点：

示例：

from __future__ import print_function


def primes():
    """Prime Number Generator

    Generator an infinite sequence of primes

    http://stackoverflow.com/questions/567222/simple-prime-generator-in-python
    """

    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}  

    # The running integer that's checked for primeness
    q = 2  

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            # 
            yield q        
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next 
            # multiples of its witnesses to prepare for larger
            # numbers
            # 
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1


def factors(n):
    yield 1
    i = 2
    limit = n**0.5
    while i <= limit:
        if n % i == 0:
            yield i
            n = n / i
            limit = n**0.5
        else:
            i += 1
    if n > 1:
        yield n


def primerange(start, stop):
    pg = primes()
    p = next(pg)

    for i in xrange(start, stop):
        while p < i:
            p = next(pg)

        if p == i:
            print("{0} is prime".format(i))
        else:
            print("{0} is not prime and has factors: {1}".format(i, ", ".join(map(str, set(factors(i))))))

输出：

>>> primerange(1, 10)
1 is not prime and has factors: 1
2 is prime
3 is prime
4 is not prime and has factors: 1, 2
5 is prime
6 is not prime and has factors: 1, 2, 3
7 is prime
8 is not prime and has factors: 1, 2
9 is not prime and has factors: 1, 3

Answer 2

您可以将每个数字的除数存储在一个列表中，然后使用", ".join(yourList)打印它

即：

def primeNum(num1, num2):
   for num in range(num1,num2):
       divisors = []
       for i in range(2,num):
           if (num%i == 0):
               divisors.append(str(i))
       if divisors:
           print ('%d is divisible by ' %num + ', '.join(divisors))
       else:
           print ('%d is a prime number' %num)

编辑:哑巴语法错误

Answer 3

只需在将质数设置为false的位置添加一个print和一个分隔符。

一种更优雅的解决方案是创建一个单独的函数isPrime，或者在内部for循环中使用break和else。无论哪种方式，都会使prime变得不必要。

你只能将一个除以1和它本身，所以它是一个质数，至少按照这个定义。