piątek, 28 lutego 2014

Sito Eratostenesa

Sito Eratostenesa

Sito Eratostenesa - przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału [2,n]\;.

Algorytm

 

Ze zbioru liczb naturalnych z przedziału [2,n]\;, tj. \{2,3,4,\dots ,n\}, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 4,6,8,\dots .
  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: 6,9,12,\dots , przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.
  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
Według tej samej procedury postępujemy dla liczby 5.
  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.
  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
Wykreślanie powtarzamy do momentu, gdy liczba i\;, której wielokrotność wykreślamy, będzie większa niż {\sqrt {n}}.
Dla danej liczby n\; wszystkie niewykreślone liczby mniejsze, bądź równe n\; są liczbami pierwszymi.
  2 3 -4- 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 -44- 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60


Autor: o

Brak komentarzy:

Prześlij komentarz

Subskrybuj: Komentarze do posta (Atom)