Python中的简单Prime生成器

Question

请问有人请告诉我这段代码我做错了什么？无论如何,它只是打印'计数'.我只想要一个非常简单的素数发生器(没什么特别的).

import math

def main():
    count = 3
    one = 1
    while one == 1:
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                continue
            if count % x != 0:
                print count

        count += 1

Answer 1

有一些问题:

• 当它没有除以x时,为什么要打印计数？它并不意味着它是素数,它只意味着这个特定的x不会分裂它
• continue 移动到下一个循环迭代 - 但你真的想停止使用它 break

这是你的代码,有一些修复,它只打印出素数:

import math

def main():
    count = 3
    
    while True:
        isprime = True
        
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                isprime = False
                break
        
        if isprime:
            print count
        
        count += 1

对于效率更高的黄金时代,请参阅其他人建议的Erastothenes筛选.这是一个很好的,优化的实现,有很多注释:

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # 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

请注意,它返回一个生成器.

Answer 2

def is_prime(num):
    """Returns True if the number is prime
    else False."""
    if num == 0 or num == 1:
        return False
    for x in range(2, num):
        if num % x == 0:
            return False
    else:
        return True

>> filter(is_prime, range(1, 20))
  [2, 3, 5, 7, 11, 13, 17, 19]

我们将在列表中获得最多20个素数.我本来可以使用Eratosthenes的Sieve,但你说你想要一些非常简单的东西.;)

Answer 3

print [x for x in range(2,100) if not [t for t in range(2,x) if not x%t]]

Answer 4

重要的是:

import re


def isprime(n):
    return re.compile(r'^1?$|^(11+)\1+$').match('1' * n) is None

print [x for x in range(100) if isprime(x)]

###########Output#############
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Answer 5

SymPy是一个用于符号数学的 Python 库。它提供了几个生成素数的函数。

isprime(n)              # Test if n is a prime number (True) or not (False).

primerange(a, b)        # Generate a list of all prime numbers in the range [a, b).
randprime(a, b)         # Return a random prime number in the range [a, b).
primepi(n)              # Return the number of prime numbers less than or equal to n.

prime(nth)              # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1)     # Return the largest prime smaller than n
nextprime(n)            # Return the ith prime greater than n

sieve.primerange(a, b)  # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes. 

这里有些例子。

>>> import sympy
>>> 
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Answer 6

def primes(n): # simple Sieve of Eratosthenes 
   odds = range(3, n+1, 2)
   sieve = set(sum([list(range(q*q, n+1, q+q)) for q in odds],[]))
   return [2] + [p for p in odds if p not in sieve]

>>> primes(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

要测试数字是否为质数：

>>> 541 in primes(541)
True
>>> 543 in primes(543)
False

Answer 7

这是一个简单的（Python 2.6.2）解决方案......它符合OP的原始请求（现在已经六个月了）；并且应该是任何“编程 101”课程中完全可以接受的解决方案......因此这篇文章。

import math

def isPrime(n):
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0: 
            return False;
    return n>1;

print 2
for n in range(3, 50):
    if isPrime(n):
        print n

这种简单的“蛮力”方法对于现代 PC 上高达约 16,000 的数字来说“足够快”（在我的 2GHz 机器上大约需要 8 秒）。

显然，通过不重新计算每个偶数的素数，或者每个数字的 3、5、7 等的每个倍数，这可以更有效地完成...参见埃拉托色尼筛法（参见上面的 eliben 的实现），如果您感觉特别勇敢和/或疯狂，甚至可以使用阿特金筛。

买者自负：我是一个Python菜鸟。请不要把我说的任何话当作福音。