Pchełki Python, odcinek 2: pierwsze mniejsze od miliona

https://xpil.eu/8hYXn 📋

Dziś druga pchełka z kodem Python; tym razem wyliczymy sobie wszystkie liczby pierwsze mniejsze od miliona. Google mówi, że jest ich 78498.

Opisy poszczególnych instrukcji umieściłem wewnątrz kodu, w formie komentarzy.

Miłej lektury...

# komentarze w Pythonie wstawiamy w ten sposób. Nie ma tutaj komentarzy blokowych (/* ... */) znanych z C

import math, time
# biblioteka math będzie potrzebna do wyliczenia pierwiastka kwadratowego
# biblioteka time przyda się do zmierzenia czasu wykonywania programu

start = time.clock()
# zapamiętujemy czas rozpoczęcia obliczeń

primes = [2, 3]
# inicjalizujemy tablicę primes dwiema początkowymi liczbami pierwszymi.
# Oczywiście można by tu wstawić więcej liczb, oszczędzając w ten sposób trochę obliczeń.
# Ale jesteśmy leniwi, więc wstawiamy tylko dwie: dwójkę i trójkę.
# Pozostałe liczby będą się w tej tablicy pojawiać sukcesywnie
# w miarę wykonywania programu.

candidate = max(primes) + 2
# pierwszy kandydat na liczbę pierwszą to największa z dotychczas znanych liczb pierwszych + 2.
# Czyli w tym przypadku 5.

while candidate <= 1000000:
# otwieramy pętlę główną, iterującą po kandydatach mniejszych od miliona

  ix = 0
  # ustawiamy indeks na zero (na pierwszym elemencie tablicy primes, czyli na dwójce)

  sqrt_candidate = math.sqrt(candidate)
  # wyliczamy i zapamiętujemy pierwiastek kwadratowy z bieżącego kandydata. W pierwszej iteracji będzie to
  # pierwiastek z 5 czyli dwa z hakiem

  while primes[ix] <= sqrt_candidate and candidate % primes[ix] != 0:
  # otwieramy pętlę wewnętrzną, iterującą po potencjalnych dzielnikach pierwszych bieżącego kandydata,
  # od dwójki aż do pierwiastka z kandydata
    ix += 1
    # w tej pętli wewnętrznej jest tylko jedna linijka, zwiększająca indeks dzielnika.
    # Pętla zakończy się, kiedy znajdziemy dzielnik, lub kiedy żaden z potencjalnych dzielników
    # nie dzieli kandydata bez reszty

  if primes[ix] > sqrt_candidate:
  # po wyjściu z pętli sprawdzamy czy dzielnik znajdujący się pod indeksem ix
  # jest większy od pierwiastka z kandydata
    primes.append(candidate)
    # jeżeli tak, kandydat jest liczbą pierwszą, dodajemy go do tablicy primes

  candidate += 2
  # kolejny kandydat jest o 2 większy od poprzedniego. Tutaj kończy się pętla zewnętrzna

elapsed = time.clock() - start
# wyliczamy czas, jaki upłynął od rozpoczęcia obliczeń do chwili obecnej

print("%d primes calculated in %.3f seconds" % (len(primes), elapsed))
# wypisujemy czas wykonania oraz liczbę znalezionych liczb pierwszych na standardowe wyjście

primes.reverse()
# odwracamy tablicę z wyliczonymi liczbami pierwszymi

print(primes[1:100])
# z odwróconej tablicy wypisujemy pierwszych sto elementów
# można by wypisać wszystkie, ale komu by się chciało przeglądać 78498 liczb...

Efekt wykonania powyższego kodu:

78498 primes calculated in 6.689 seconds
[999979, 999961, 999959, 999953, 999931, 999917, 999907, 999883, 999863, 999853, 999809, 999773, 999769, 999763, 999749, 999727, 999721, 999683, 999671, 999667, 999653, 999631, 999623, 999613, 999611, 999599, 999563, 999553, 999541, 999529, 999521, 999499, 999491, 999451, 999437, 999433, 999431, 999389, 999377, 999371, 999359, 999331, 999329, 999307, 999287, 999269, 999239, 999233, 999221, 999217, 999199, 999181, 999169, 999149, 999133, 999101, 999091, 999083, 999067, 999049, 999043, 999029, 999023, 999007, 998989, 998983, 998969, 998957, 998951, 998947, 998941, 998927, 998917, 998909, 998897, 998861, 998857, 998843, 998839, 998831, 998819, 998813, 998779, 998759, 998749, 998743, 998737, 998717, 998689, 998687, 998681, 998653, 998651, 998633, 998629, 998623, 998617, 998561, 998551]

https://xpil.eu/8hYXn 📋