Schnellster Weg, um alle Primzahlen unter N aufzulisten

Question

Dies ist der beste Algorithmus, den ich entwickeln konnte.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

Kann er noch schneller gemacht werden?

Dieser Code hat ein Problem: Da numbers eine ungeordnete Menge ist, gibt es keine Garantie dafür, dass numbers.pop() die niedrigste Zahl aus der Menge entfernt. Trotzdem funktioniert es (zumindest für mich) für einige Eingabelnummern:

>>> sum(get_primes(2000000))
142913828922L
#Das ist die korrekte Summe aller Zahlen unter 2 Millionen
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

Answer 1

Du hast einen schnelleren Code und auch den einfachsten Code, der Primzahlen generiert. Aber für größere Zahlen funktioniert es nicht bei n=10000, 10000000, es scheitert vielleicht am .pop() Methode

Überlege: Ist N eine Primzahl?

• Fall 1:

  Du hast einige Faktoren von N,

  for i in range(2, N):

  Wenn N eine Primzahl ist, wird die Schleife ungefähr ~(N-2) mal durchgeführt. Andernfalls weniger oft

• Fall 2:

  for i in range(2, int(math.sqrt(N)): 

  Die Schleife wird fast ~(sqrt(N)-2) mal durchgeführt, wenn N eine Primzahl ist, sonst wird sie irgendwo unterbrochen

• Fall 3:

  Besser teilen wir N nur durch die Anzahl der Primzahlen<=sqrt(N)

  Wo die Schleife nur (sqrt(N)) mal durchgeführt wird

  (sqrt(N)) << sqrt(N) wenn N steigt

  from math import sqrt
  from time import *
  prime_list = [2]
  n = int(input())
  s = time()
  for n0 in range(2,n+1):
      for i0 in prime_list:
          if n0%i0==0:
              break
          elif i0>=int(sqrt(n0)):
              prime_list.append(n0)
              break
  e = time()
  print(e-s)
  #print(prime_list); print(f'pi({n})={len(prime_list)}')
  print(f'{n}: {len(prime_list)}, time: {e-s}')

• Ausgabe

  100: 25, time: 0.00010275840759277344
  1000: 168, time: 0.0008606910705566406
  10000: 1229, time: 0.015588521957397461
  100000: 9592, time: 0.023436546325683594
  1000000: 78498, time: 4.1965954303741455
  10000000: 664579, time: 109.24591708183289
  100000000: 5761455, time: 2289.130858898163

Für weniger als 1000 erscheint es langsam, aber dann für <10^6 denke ich, dass es schneller ist.

Obwohl ich die Zeitkomplexität nicht verstanden habe.

Answer 2

Dies ist eine elegante und einfachere Lösung, um Primzahlen mithilfe einer gespeicherten Liste zu finden. Beginnt mit 4 Variablen, Sie müssen nur ungerade Primzahlen auf Teiler überprüfen, und Sie müssen nur bis zur Hälfte der Zahl, die Sie als Primzahl testen, testen (es macht keinen Sinn zu testen, ob 9, 11, 13 in 17 dividieren). Es testet zuvor gespeicherte Primzahlen als Teiler.

# Programm zur Berechnung von Primzahlen
primes = [1,3,5,7]
for n in range(9,100000,2):
    for x in range(1,(len(primes)/2)):
        if n % primes[x] == 0:
            break
    else:
        primes.append(n)
print primes

Answer 3

So einfach...

# Sie müssen Primzahlen bis n auflisten
nums = xrange(2, n)
for i in range(2, 10):
    nums = filter(lambda s: s==i or s%i, nums)
print nums

Das ist der Weg, wie du dich mit anderen vergleichen kannst.