Sito Eratostenesa - przypisywany Eratostenesowi z Cyreny algorytm wyznaczania liczb pierwszych z zadanego przedziału ![[2,n]\;](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uUhnEk3ua9kNmR-TQ27Tch8r-5NoAASWhnSU97smFbTJ-iGduLvhLF9mbdpjiNDrCEhZCGhck4TrEZbQzF4GuqELESWSgfEHrvghzZVWMiCf009svnlXIcLJT_FhqicWWLLwG9lfv4sAUnPpUCog=s0-d)
.
Ze zbioru liczb naturalnych z przedziału, tj. 
, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest 
.
Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej:
, przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.
Według tej samej procedury postępujemy dla liczby 5.
Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.
Wykreślanie powtarzamy do momentu, gdy liczba
, której wielokrotność wykreślamy, będzie większa niż 
.
Dla danej liczby
wszystkie niewykreślone liczby mniejsze, bądź równe są liczbami pierwszymi.
.Ze zbioru liczb naturalnych z przedziału
, tj. , wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest .Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej:
, przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.Według tej samej procedury postępujemy dla liczby 5.
Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.
Wykreślanie powtarzamy do momentu, gdy liczba
, której wielokrotność wykreślamy, będzie większa niż .Dla danej liczby
wszystkie niewykreślone liczby mniejsze, bądź równe są liczbami pierwszymi.
Brak komentarzy:
Prześlij komentarz