Basic Primzahlengenerator in Python

Question

Ich wollte nur ein paar Feedbacks zu meinem Primzahlengenerator. z.B. Ist es in Ordnung, verwendet es zu viele Ressourcen usw. Es verwendet keine Bibliotheken, es ist ziemlich einfach, und es ist eine Reflektion meines aktuellen Standes der Programmierkenntnisse, also halte dich nicht zurück, wie ich es lernen will.

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

Es gibt einige Optimierungen thar sind üblich:

Beispiel:

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 

• Abdeckung die Basis Fällen
• Nur zur Quadratwurzel von n iterieren up

Das obige Beispiel generiert keine Primzahlen, sondern testet sie. Sie könnten die gleichen Optimierungen an Ihrem Code anpassen :)

Einer der effizientere Algorithmen ich in Python geschrieben gefunden habe, ist in der folgenden Fragen ans Antwort (unter Verwendung eines Siebs) gefunden:

Simple Prime Generator in Python

Meine eigene Anpassung des Siebalgorithmus:

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)) 

Auf meiner Hardware ich ziemlich schnell die ersten Millionen Primzahlen erzeugen können (g Iven, dass dies in Python) geschrieben:

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

Hier ist ein ziemlich effizienter Primzahl-Generator, den ich eine Weile zurück schrieb, verwendet den 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() 

Wikipedia-Artikel (oben verlinkten) Erläutert wie es besser funktioniert, als ich könnte, also werde ich nur empfehlen, dass du das liest.

Answer 3

Dies ist die Standardmethode der Primzahlen von der C# -Version bei angepasst Erzeugung: 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

ich einige Optimierungen für den ersten Code haben, die verwendet werden kann, wenn das Argument negativ ist:

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

Als Python ist es normalerweise besser, einen Generator zurückzugeben, der eine unendliche Folge von Primzahlen anstelle einer Liste zurückgibt.

Activestate hat eine Liste von älterem Sieb des Eratosthenes recipes

Hier ist einer von ihnen zu Python aktualisiert 2.7 itertools count mit einem Schritt Argumente, das nicht existierte, als das ursprüngliche Rezept geschrieben wurde:

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 

Da es sich um einen Generator handelt, ist es viel effizienter als eine ganze Liste. Da Composite lokalisiert wird, ist es auch recheneffizient.

Run this:

>>> g=sieve() 

Dann ist jeder nachfolgende Aufruf gibt die nächste Primzahl:

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

Sie können dann eine Liste zwischen den Grenzen erhalten (dh die X-te Primzahl von der ersten bis zur X + Y prime ...) mit 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])