Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
ProblemW przedziale liczb naturalnych |
W roku 1978 dwaj informatycy,
David Gries z Cornell University oraz
Jayadev Misra z University of Texas w Austin,
opublikowali w ramach ACMs algorytm wyszukiwania liczb pierwszych, który działa
w czasie liniowym
Algorytm operuje na zbiorze liczbowym
usuń(S, i)
: jest zdefiniowana dla
liczby
i ∈ S;
następne(S, i)
: jest funkcją zdefiniowaną dla liczby
i ∈ S,
której wynikiem jest bezpośrednio następna liczba naturalna w S,
większa
W algorytmie wykorzystuje się twierdzenie:
Liczba złożona x może zostać jednoznacznie zapisana jako:
x = pk×q
gdzie: | p jest najmniejszą liczbą pierwszą dzielącą x
bez reszty; k ≥ 1; p = q lub p jest mniejsze od najmniejszej liczby pierwszej, która dzieli q bez reszty. |
Ponieważ w powyższy sposób nie można zapisać żadnej liczby pierwszej, zatem w
celu usunięcia ze zbioru S liczb złożonych, algorytm musi
jedynie wygenerować wszystkie kombinacje trójek
Porządek α zdefiniowany jest następująco:
|
|
|
|
Poniższa tabelka przedstawia to uporządkowanie, jednocześnie wyjaśniając
sposób pracy algorytmu. Wiersze zawierają kolejne wartości par
p | q | S |
2 |
2 |
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 |
2 |
3 |
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 |
2 |
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 |
2 |
7 |
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 |
2 |
9 |
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 |
2 |
11 |
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 |
2 |
13 |
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 |
2 |
15 |
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 |
3 |
3 |
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 |
3 |
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 |
3 |
7 |
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 |
5 |
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 |
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 |
Zasada działania algorytmu sita liniowego jest następująca: Za p i q
przyjmujemy pierwszą liczbę zbioru.
Za k przyjmujemy 1. Następnie w pętli generujemy liczby
K01: S ← {2, 3, …, n} ; początkowo zbiór S zawiera ; wszystkie liczby z przedziału ; <2, n> K02: p ← 2 ; pierwszy mnożnik K03: Dopóki p×p ≤ n: wykonuj kroki K04…K11 K04: q ← p ; drugi mnożnik K05: Dopóki p×q ≤ n: wykonuj kroki K06…K10 K06: x ← p×q ; obliczamy liczbę złożoną K07: Dopóki x ≤ n: ; w pętli wyrzucamy ze zbioru wykonuj kroki K08…K09 ; liczby złożone K08: usuń(S, x) K09: x ← p×x ; następna liczba złożona K10: q ← następne(S, q) ; za q przyjmujemy następną ; liczbę w zbiorze, która nie ; została jeszcze wyrzucona K11: p ← następne(S, p) ; za p przyjmujemy następną ; liczbę pierwszą ze zbioru K12: Dla i = 2, 3, …, n: ; przeglądamy zbiór i wypisujemy wykonuj krok K13 ; pozostałe w nim liczby pierwsze K13: Jeśli i ∈ S, to pisz i K14: Zakończ
Uwaga: Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program w pierwszym wierszu czyta
liczbę n i w następnych wierszach wypisuje kolejne
liczby pierwsze zawarte w przedziale |
Pascal// Sito Liniowe // Data : 17.03.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- program prg; type Tbarray = array of boolean; var i, n, p, q, x : longword; S : Tbarray; begin readln(n); setlength(S, n+1); for i := 2 to n do S[i] := true; p := 2; while p*p <= n do begin q := p; while p*q <= n do begin x := p*q; while x <= n do begin S[x] := false; x := p*x; end; repeat inc(q); until S[q]; end; repeat inc(p); until S[p]; end; for i := 2 to n do if S[i] then write(i, ' '); writeln; end. |
// Sito Liniowe // Data : 17.03.2008 // (C)2020 mgr Jerzy Wałaszek //--------------------------- #include <iostream> using namespace std; int main() { unsigned int i, n, p, q, x; bool * S; cin >> n; S = new bool[n+1]; for(i = 2; i <= n; i++) S[i] = true; p = 2; while(p*p <= n) { q = p; while(p*q <= n) { x = p*q; while(x <= n) { S[x] = false; x *= p; } while(!S[++q]); } while(!S[++p]); } for(i = 2; i <= n; i++) if(S[i]) cout << i << " "; cout << endl; delete [] S; return 0; } |
Basic' Sito Liniowe ' Data : 17.03.2008 ' (C)2020 mgr Jerzy Wałaszek '--------------------------- Dim As Uinteger i, n, p, q, x Input n Dim As Byte S(n+1) For i = 2 To n S(i) = 1 Next p = 2 While p*p <= n q = p While p*q <= n x = p*q While x <= n S(x) = 0 x *= p Wend Do q += 1 Loop Until S(q) = 1 Wend Do p += 1 Loop Until S(p) = 1 Wend For i = 2 To n If S(i) = 1 Then _ Print i;" "; Next Print End |
Python (dodatek)# Sito Liniowe # Data : 11.02.2024 # (C)2024 mgr Jerzy Wałaszek # -------------------------- n = int(input()) s = [True]*(n+1) p = 2 while p*p <= n: q = p while p*q <= n: x = p*q while x <= n: s[x] = False x *= p while 1: q += 1 if s[q]: break while 1: p += 1 if s[p]: break for i in range(2, n+1): if s[i]: print(i, end=" ") print() |
Wynik: |
100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.