Trình tạo số nguyên tố cơ bản trong Python

Question

Chỉ muốn một số phản hồi về trình tạo số nguyên tố của tôi. ví dụ. nó có ổn không, nó sử dụng nhiều tài nguyên vv. Nó không sử dụng thư viện, nó khá đơn giản, và nó phản ánh tình trạng lập trình hiện tại của tôi, vì vậy đừng giữ lại như tôi muốn học.

def prime_gen(n): 

    primes = [2] 
    a = 2 

    while a < n: 

     counter = 0 

     for i in primes: 
      if a % i == 0: 
       counter += 1 

     if counter == 0: 
      primes.append(a) 
     else: 
      counter = 0 

     a = a + 1 

    print primes 

Answer 1

Có một vài tối ưu hóa thar được điểm chung:

Ví dụ:

def prime(x): 
    if x in [0, 1]: 
     return False 
    if x == 2: 
     return True 
    for n in xrange(3, int(x ** 0.5 + 1)): 
     if x % n == 0: 
      return False 
    return True 

• Bìa các trường hợp cơ sở
• Chỉ lặp lên đến căn bậc hai của n

Ví dụ trên không tạo ra số nguyên tố nhưng kiểm tra chúng. Bạn có thể điều chỉnh tối ưu hóa cùng với mã của bạn :)

Một trong những thuật toán hiệu quả hơn tôi đã tìm thấy được viết bằng Python được tìm thấy trong các câu trả lời sau câu hỏi ans (sử dụng một rây):

Simple Prime Generator in Python

thích ứng My own của thuật toán sàng:

from itertools import islice 


def primes(): 
    if hasattr(primes, "D"): 
     D = primes.D 
    else: 
     primes.D = D = {} 

    def sieve(): 
     q = 2 
     while True: 
      if q not in D: 
       yield q 
       D[q * q] = [q] 
      else: 
       for p in D[q]: 
        D.setdefault(p + q, []).append(p) 
       del D[q] 

      q += 1 

    return sieve() 


print list(islice(primes(), 0, 1000000)) 

Mở phần cứng của tôi, tôi có thể tạo ra hàng triệu số nguyên tố đầu tiên khá nhanh chóng (g Iven rằng đây được viết bằng Python):

prologic@daisy 
Thu Apr 23 12:58:37 
~/work/euler 
$ time python foo.py > primes.txt 

real 0m19.664s 
user 0m19.453s 
sys 0m0.241s 

prologic@daisy 
Thu Apr 23 12:59:01 
~/work/euler 
$ du -h primes.txt 
8.9M primes.txt 

Answer 2

Dưới đây là một máy phát điện số nguyên tố khá hiệu quả mà tôi đã viết một khi trở lại sử dụng các Sieve of Eratosthenes:

#!/usr/bin/env python2.7 

def primeslt(n): 
    """Finds all primes less than n""" 

    if n < 3: 
     return [] 

    A = [True] * n 
    A[0], A[1] = False, False 

    for i in range(2, int(n**0.5)+1): 
     if A[i]: 
      j = i**2 
      while j < n: 
       A[j] = False 
       j += i 

    return [num for num in xrange(n) if A[num]] 

def main(): 
    i = '' 
    while not i.isdigit(): 
     i = raw_input('Find all prime numbers less than... ') 
    print primeslt(int(i)) 

if __name__ == '__main__': 
    main() 

Các bài viết Wikipedia (liên kết ở trên) giải thích làm thế nào nó hoạt động tốt hơn tôi có thể, vì vậy tôi chỉ muốn khuyên bạn nên đọc nó.

Answer 3

Đây là phương pháp tiêu chuẩn tạo ra số nguyên tố chuyển thể từ phiên bản C# tại địa chỉ: Most Elegant Way to Generate Prime Number

def prime_gen(n): 

    primes = [2] 

    # start at 3 because 2 is already in the list 
    nextPrime = 3 

    while nextPrime < n: 

     isPrime = True 

     i = 0 

     # the optimization here is that you're checking from 
     # the number in the prime list to the square root of 
     # the number you're testing for primality 
     squareRoot = int(nextPrime ** .5) 

     while primes[i] <= squareRoot: 

      if nextPrime % primes[i] == 0: 

       isPrime = False 

      i += 1 

     if isPrime: 

      primes.append(nextPrime) 

     # only checking for odd numbers so add 2 
     nextPrime += 2 

    print primes 

Answer 4

Tôi có một số tối ưu hóa cho các mã đầu tiên mà có thể được sử dụng khi các đối số là tiêu cực:

def is_prime(x):  
    if x <=1: 
     return False 
    else: 
     for n in xrange(2, int(x ** 0.5 + 1)): 
      if x % n == 0: 
       return False 
    return True 
print is_prime(-3) 

Answer 5

Là Python, thường tốt hơn là trả về một trình tạo sẽ trả về một chuỗi số nguyên tố vô hạn thay vì một danh sách.

ActiveState có một danh sách các Sieve cũ của Eratosthenes recipes

Dưới đây là một trong số họ cập nhật để Python 2.7 sử dụng itertools count với một đối số bước mà không tồn tại khi các công thức ban đầu được viết:

import itertools as it 

def sieve(): 
    """ Generate an infinite sequence of prime numbers. 
    """ 
    yield 2 
    D = {} 
    for q in it.count(3, 2): # start at 3 and step by odds 
     p = D.pop(q, 0) 
     if p: 
      x = q + p 
      while x in D: x += p 
      D[x] = p   # new composite found. Mark that 
     else: 
      yield q   # q is a new prime since no composite was found 
      D[q*q] = 2*q 

Vì nó là một bộ tạo nên nó hiệu quả hơn nhiều so với việc tạo ra toàn bộ danh sách. Kể từ khi nó nằm tổng hợp, nó là tính toán hiệu quả là tốt.

Run này:

>>> g=sieve() 

Sau đó, mỗi cuộc gọi tiếp theo trả về thủ tiếp theo:

>>> next(g) 
2 
>>> next(g) 
3 
# etc 

Sau đó bạn có thể nhận được một danh sách giữa ranh giới (ví dụ, Thủ khoá X từ người đầu tiên X + Y nguyên tố ...) bằng cách sử dụng islice:

>>> tgt=0 
>>> tgt, list(it.islice(sieve(), tgt, tgt+10)) 
(0, [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]) 
>>> tgt=1000000 
>>> tgt, list(it.islice(sieve(), tgt, tgt+10)) 
(1000000, [15485867, 15485917, 15485927, 15485933, 15485941, 15485959, 15485989, 15485993, 15486013, 15486041])