Python 中的简单素数生成器 [英] Simple prime number generator in Python

问题描述

有人能告诉我这段代码有什么问题吗?无论如何，它只是打印计数".我只想要一个非常简单的素数生成器(没什么特别的).

Could someone please tell me what I'm doing wrong with this code? It is just printing 'count' anyway. I just want a very simple prime generator (nothing fancy).

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

推荐答案

存在一些问题:

• 当 count 没有除以 x 时，为什么要打印出来?这并不意味着它是素数，它只是意味着这个特定的 x 不能整除它
• continue 移动到下一个循环迭代 - 但您真的想使用 break
停止它

• Why do you print out count when it didn't divide by x? It doesn't mean it's prime, it means only that this particular x doesn't divide it
• continue moves to the next loop iteration - but you really want to stop it using break

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

Here's your code with a few fixes, it prints out only primes:

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

如其他人所建议的那样，要获得更高效的素数生成，请参阅埃拉托色尼筛.这是一个很好的优化实现，有很多评论:

For much more efficient prime generation, see the Sieve of Eratosthenes, as others have suggested. Here's a nice, optimized implementation with many comments:

# 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

注意它返回一个生成器.

Note that it returns a generator.

这篇关于Python 中的简单素数生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！