Python中的简单素数生成器

存在一些问题:

• 你为什么要打印计数,而不是除以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

如其他人所建议的那样,要想获得更高效的黄金一代,请参见埃拉托斯烯筛。这是一个很好的优化实现,有很多评论:

# 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

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

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个素数。 我本可以用埃拉托斯坦筛,但你说 你想要非常简单的东西

re功能强大:

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]

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

def primes(n): # simple sieve of multiples 
   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

这里有一个 易于理解的

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上的数字可以达到16000左右(在我的2GHz设备上大约需要8秒)。

显然,通过不重新计算每一个偶数的素数,或每一个单个数的3、5、7等的倍数,可以更有效地实现这一点。。。见 Sieve of Eratosthenes Sieve of Atkin 如果你感到特别勇敢和/或疯狂。

买主警告:我是一个巨蟒noob。请不要把我说的任何话当作福音。

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]

这是Eratosthenes筛子的一个numpy版本,它具有OK复杂度(低于对长度为n的数组进行排序)和矢量化。

import numpy as np 
def generate_primes(n):
    is_prime = np.ones(n+1,dtype=bool)
    is_prime[0:2] = False
    for i in range(int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*2::i]=False
    return np.where(is_prime)[0]

时间:

import time    
for i in range(2,10):
    timer =time.time()
    generate_primes(10**i)
    print('n = 10^',i,' time =', round(time.time()-timer,6))

>> n = 10^ 2  time = 5.6e-05
>> n = 10^ 3  time = 6.4e-05
>> n = 10^ 4  time = 0.000114
>> n = 10^ 5  time = 0.000593
>> n = 10^ 6  time = 0.00467
>> n = 10^ 7  time = 0.177758
>> n = 10^ 8  time = 1.701312
>> n = 10^ 9  time = 19.322478

python 3(生成素数)

import math

i = 2
while True:
    for x in range(2, int(math.sqrt(i) + 1)):
        if i%x==0:
            break
    else:
        print(i)
    i += 1

以下是我所拥有的:

def is_prime(num):
    if num < 2:         return False
    elif num < 4:       return True
    elif not num % 2:   return False
    elif num < 9:       return True
    elif not num % 3:   return False
    else:
        for n in range(5, int(math.sqrt(num) + 1), 6):
            if not num % n:
                return False
            elif not num % (n + 2):
                return False

    return True

对于大数来说,它非常快,因为它只检查已经存在的素数的除数。

# primes up to 'max'
def primes_max(max):
    yield 2
    for n in range(3, max, 2):
        if is_prime(n):
            yield n

# the first 'count' primes
def primes_count(count):
    counter = 0
    num = 3

    yield 2

    while counter < count:
        if is_prime(num):
            yield num
            counter += 1
        num += 2

在这里使用发电机可能是为了提高效率。

仅供参考,而不是说:

one = 1
while one == 1:
    # do stuff

你可以简单地说:

while 1:
    #do stuff

在我看来,最好采用功能性方法,

所以我首先创建一个函数来确定这个数是否为素数,然后根据需要在循环或其他地方使用它。

def isprime(n):
      for x in range(2,n):
        if n%x == 0:
            return False
    return True

然后运行一个简单的列表理解或生成器表达式来获得素数列表,

[x for x in range(1,100) if isprime(x)]

另一个简单的例子,只考虑奇数的简单优化。使用惰性流(python生成器)完成的所有操作。

用法:素数=列表(创建素数迭代器(1,30))

import math
import itertools

def create_prime_iterator(rfrom, rto):
    """Create iterator of prime numbers in range [rfrom, rto]"""
    prefix = [2] if rfrom < 3 and rto > 1 else [] # include 2 if it is in range separately as it is a "weird" case of even prime
    odd_rfrom = 3 if rfrom < 3 else make_odd(rfrom) # make rfrom an odd number so that  we can skip all even nubers when searching for primes, also skip 1 as a non prime odd number.
    odd_numbers = (num for num in xrange(odd_rfrom, rto + 1, 2))
    prime_generator = (num for num in odd_numbers if not has_odd_divisor(num))
    return itertools.chain(prefix, prime_generator)

def has_odd_divisor(num):
    """Test whether number is evenly divisable by odd divisor."""
    maxDivisor = int(math.sqrt(num))
    for divisor in xrange(3, maxDivisor + 1, 2):
        if num % divisor == 0:
            return True
    return False

def make_odd(number):
    """Make number odd by adding one to it if it was even, otherwise return it unchanged"""
    return number | 1

def genPrime():
    num = 1
    prime = False
    while True:
        # Loop through all numbers up to num
        for i in range(2, num+1):
            # Check if num has remainder after the modulo of any previous numbers
            if num % i == 0:
                prime = False
                # Num is only prime if no remainder and i is num
                if i == num:
                    prime = True
                break

        if prime:
            yield num
            num += 1
        else:
            num += 1

prime = genPrime()
for _ in range(100):
    print(next(prime))

刚刚学习了主题,在线程中查找示例并尝试制作我的版本:

from collections import defaultdict
# from pprint import pprint

import re


def gen_primes(limit=None):
    """Sieve of Eratosthenes"""
    not_prime = defaultdict(list)
    num = 2
    while limit is None or num <= limit:
        if num in not_prime:
            for prime in not_prime[num]:
                not_prime[prime + num].append(prime)
            del not_prime[num]
        else:  # Prime number
            yield num
            not_prime[num * num] = [num]
        # It's amazing to debug it this way:
        # pprint([num, dict(not_prime)], width=1)
        # input()
        num += 1


def is_prime(num):
    """Check if number is prime based on Sieve of Eratosthenes"""
    return num > 1 and list(gen_primes(limit=num)).pop() == num


def oneliner_is_prime(num):
    """Simple check if number is prime"""
    return num > 1 and not any([num % x == 0 for x in range(2, num)])


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


def simple_is_prime(num):
    """Simple check if number is prime
    More efficient than oneliner_is_prime as it breaks the loop
    """
    for x in range(2, num):
        if num % x == 0:
            return False
    return num > 1


def simple_gen_primes(limit=None):
    """Prime number generator based on simple gen"""
    num = 2
    while limit is None or num <= limit:
        if simple_is_prime(num):
            yield num
        num += 1


if __name__ == "__main__":
    less1000primes = list(gen_primes(limit=1000))
    assert less1000primes == list(simple_gen_primes(limit=1000))
    for num in range(1000):
        assert (
            (num in less1000primes)
            == is_prime(num)
            == oneliner_is_prime(num)
            == regex_is_prime(num)
            == simple_is_prime(num)
        )
    print("Primes less than 1000:")
    print(less1000primes)

    from timeit import timeit

    print("\nTimeit:")
    print(
        "gen_primes:",
        timeit(
            "list(gen_primes(limit=1000))",
            setup="from __main__ import gen_primes",
            number=1000,
        ),
    )
    print(
        "simple_gen_primes:",
        timeit(
            "list(simple_gen_primes(limit=1000))",
            setup="from __main__ import simple_gen_primes",
            number=1000,
        ),
    )
    print(
        "is_prime:",
        timeit(
            "[is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import is_prime",
            number=100,
        ),
    )
    print(
        "oneliner_is_prime:",
        timeit(
            "[oneliner_is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import oneliner_is_prime",
            number=100,
        ),
    )
    print(
        "regex_is_prime:",
        timeit(
            "[regex_is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import regex_is_prime",
            number=100,
        ),
    )
    print(
        "simple_is_prime:",
        timeit(
            "[simple_is_prime(num) for num in range(2, 1000)]",
            setup="from __main__ import simple_is_prime",
            number=100,
        ),
    )

$ python prime_time.py
Primes less than 1000:
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

Timeit:
gen_primes: 0.6738066330144648
simple_gen_primes: 4.738092333020177
is_prime: 31.83770858097705
oneliner_is_prime: 3.3708438930043485
regex_is_prime: 8.692703998007346
simple_is_prime: 0.4686249239894096

因此,我可以看到,对于不同的问题,我们有正确的答案;对于素数生成器 gen_primes 看起来是正确的答案;但对于质数检查 simple_is_prime 功能更适合。

这是可行的,但我总是乐于接受更好的方法来实现这一目标 is_prime 作用

您需要确保所有可能的除数都不会均匀地除以您正在检查的数字。在这种情况下,您将在任何时候打印您要检查的数字,只有一个可能的除数不能均匀地除以该数字。

另外,您不希望使用continue语句,因为continue语句只会导致它在您已经发现数字不是素数时检查下一个可能的除数。

这似乎是家庭作业,所以我将给出一个提示,而不是详细的解释。如果我想错了,请纠正我。

当你看到一个偶数除数时,你就可以摆脱困境了。

一 不可分的数字。例如,2不能平均分成9。但这并不意味着9是质数。你可能想继续,直到你确定 不

(正如其他人所回答的,筛选是一种更有效的方法……只是试图帮助您理解为什么这个特定代码没有达到您想要的效果)

here:

>>> noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
>>> primes = [x for x in range(2, 50) if x not in noprimes]
>>> print primes
>>> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

如果你想直接计算素数,这个怎么样:

def oprime(n):
counter = 0
b = 1
if n == 1:
    print 2
while counter < n-1:
    b = b + 2
    for a in range(2,b):
        if b % a == 0:
            break
    else:
        counter = counter + 1
        if counter == n-1:
            print b

与user107745类似,但使用“all”而不是双重否定(可读性稍高一点,但我认为性能相同):

import math
[x for x in xrange(2,10000) if all(x%t for t in xrange(2,int(math.sqrt(x))+1))]

基本上,它在(2100)范围内的x上进行迭代,并针对(2,x)范围内的所有t只选择那些没有mod==0的

另一种方法可能只是在我们进行时填充素数:

primes = set()
def isPrime(x):
  if x in primes:
    return x
  for i in primes:
    if not x % i:
      return None
  else:
    primes.add(x)
    return x

filter(isPrime, range(2,10000))

import time

maxnum=input("You want the prime number of 1 through....")

n=2
prime=[]
start=time.time()

while n<=maxnum:

    d=2.0
    pr=True
    cntr=0

    while d<n**.5:

        if n%d==0:
            pr=False
        else:
            break
        d=d+1

    if cntr==0:

        prime.append(n)
        #print n

    n=n+1

print "Total time:",time.time()-start

如果要查找某个范围内的所有素数,可以执行以下操作:

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
num = 0
itr = 0
tot = ''
while itr <= 100:
    itr = itr + 1
    num = num + 1
    if is_prime(num) == True:
        print(num)
        tot = tot + ' ' + str(num)
print(tot)

加上 while its <= 还有你的号码。
输出:
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 101

def primes(num):
    if 2 <= num:
        yield 2
    for i in range(3, num + 1, 2):
        if all(i % x != 0 for x in range(3, int(math.sqrt(i) + 1))):
            yield i

用法:

for i in primes(10):
    print(i)

• continue语句看起来是错误的。

• 你可以写“while True:”来获得一个无限循环。

def genPrimes():
    primes = []   # primes generated so far
    last = 1      # last number tried
    while True:
        last += 1
        for p in primes:
            if last % p == 0:
                break
        else:
            primes.append(last)
            yield last

def check_prime(x):
    if (x < 2): 
       return 0
    elif (x == 2): 
       return 1
    t = range(x)
    for i in t[2:]:
       if (x % i == 0):
            return 0
    return 1

import math

def is_prime(num):

    if num < 2:
        return False

    for i in range(2, int(math.sqrt(num) + 1)):
        if num % i == 0:
            return False

return True