Liczby pierwsze, algorytm naiwny, optymalizacja z pierwiastkiem
ð Podstawa programowa: I.2aLiczba pierwsza to liczba naturalna wieksza od 1, ktora ma dokladnie dwa dzielniki: 1 i sama siebie.
Pierwsze liczby pierwsze: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...
Sprawdzamy, czy liczba n jest podzielna przez jakakolwiek liczbe od 2 do n-1:
ALGORYTM CzyPierwsza_Naiwny(n):
1. JESLI n <= 1 ZWROC "NIE"
2. DLA i OD 2 DO n-1:
a. JESLI n MOD i = 0 ZWROC "NIE" (n jest podzielne przez i)
3. ZWROC "TAK"
Przyklad dla n = 7:
7 MOD 2 = 1 (nie dzieli sie)
7 MOD 3 = 1 (nie dzieli sie)
7 MOD 4 = 3 (nie dzieli sie)
7 MOD 5 = 2 (nie dzieli sie)
7 MOD 6 = 1 (nie dzieli sie)
=> 7 jest liczba pierwszaKluczowa obserwacja: jesli n = a * b, to jeden z czynnikow musi byc <= sqrt(n). Dlatego wystarczy sprawdzac dzielniki do pierwiastka z n.
ALGORYTM CzyPierwsza_Optymalny(n):
1. JESLI n <= 1 ZWROC "NIE"
2. JESLI n = 2 ZWROC "TAK"
3. JESLI n MOD 2 = 0 ZWROC "NIE" (parzysta, a nie 2)
4. DLA i OD 3 DO sqrt(n), KROK 2:
a. JESLI n MOD i = 0 ZWROC "NIE"
5. ZWROC "TAK"
Przyklad dla n = 37:
sqrt(37) ≈ 6.08, wiec sprawdzamy do 6
37 MOD 3 = 1 (nie dzieli sie)
37 MOD 5 = 2 (nie dzieli sie)
=> 37 jest liczba pierwsza (tylko 3 sprawdzenia!)START -> Wczytaj n
|
v
n <= 1? --TAK--> "NIE jest pierwsza" -> KONIEC
| NIE
v
n = 2? --TAK--> "TAK, jest pierwsza" -> KONIEC
| NIE
v
n parzysta? --TAK--> "NIE jest pierwsza" -> KONIEC
| NIE
v
i = 3
|
v
i*i <= n? --NIE--> "TAK, jest pierwsza" -> KONIEC
| TAK
v
n MOD i = 0? --TAK--> "NIE jest pierwsza" -> KONIEC
| NIE
v
i = i + 2, wroc do sprawdzenia i*i <= nUzyj algorytmu zoptymalizowanego (z pierwiastkiem), aby sprawdzic, czy nastepujace liczby sa pierwsze. Zapisz kazdy krok:
a) 29
b) 51
c) 97
a) n = 29:
29 > 1, 29 != 2, 29 nieparzysta
sqrt(29) ≈ 5.39, sprawdzamy do 5
29 MOD 3 = 2 (nie dzieli sie)
29 MOD 5 = 4 (nie dzieli sie)
=> 29 JEST liczba pierwsza
b) n = 51:
51 > 1, 51 != 2, 51 nieparzysta
sqrt(51) ≈ 7.14, sprawdzamy do 7
51 MOD 3 = 0 (dzieli sie!)
=> 51 NIE JEST liczba pierwsza (51 = 3 * 17)
c) n = 97:
97 > 1, 97 != 2, 97 nieparzysta
sqrt(97) ≈ 9.85, sprawdzamy do 9
97 MOD 3 = 1 (nie dzieli sie)
97 MOD 5 = 2 (nie dzieli sie)
97 MOD 7 = 6 (nie dzieli sie)
97 MOD 9 = 7 (nie dzieli sie)
=> 97 JEST liczba pierwszaUzyj algorytmu, aby znalezc wszystkie liczby pierwsze w przedziale od 50 do 70.
Sprawdzamy nieparzyste liczby od 51 do 69:
51: 51 MOD 3 = 0 -> NIE (51=3*17)
53: sqrt(53)≈7.3 -> 53%3=2, 53%5=3, 53%7=4 -> TAK
55: 55 MOD 5 = 0 -> NIE (55=5*11)
57: 57 MOD 3 = 0 -> NIE (57=3*19)
59: sqrt(59)≈7.7 -> 59%3=2, 59%5=4, 59%7=3 -> TAK
61: sqrt(61)≈7.8 -> 61%3=1, 61%5=1, 61%7=5 -> TAK
63: 63 MOD 3 = 0 -> NIE (63=3*21)
65: 65 MOD 5 = 0 -> NIE (65=5*13)
67: sqrt(67)≈8.2 -> 67%3=1, 67%5=2, 67%7=4 -> TAK
69: 69 MOD 3 = 0 -> NIE (69=3*23)
Liczby pierwsze w [50,70]: 53, 59, 61, 67Ile sprawdzen (operacji MOD) wykona algorytm naiwny, a ile zoptymalizowany dla nastepujacych liczb?
a) n = 100 (nie jest pierwsza, 100 = 2 * 50)
b) n = 101 (jest pierwsza)
a) n = 100:
Naiwny: 1 sprawdzenie (100 MOD 2 = 0, koniec)
Optymalny: 1 sprawdzenie (100 jest parzysta, koniec)
(Dla liczb parzystych oba sa szybkie!)
b) n = 101:
Naiwny: 99 sprawdzen (od 2 do 100, zadne nie dzieli)
Optymalny: sqrt(101)≈10.05
101 nieparzysta, sprawdzamy: 3, 5, 7, 9
= 4 sprawdzenia
Roznica: 99 vs 4 sprawdzenia!
Wniosek: Dla duzych liczb pierwszych roznica
jest ogromna. Im wieksza liczba, tym wieksza
oszczednosc.Napisz pseudokod algorytmu, ktory wypisuje wszystkie liczby pierwsze od 2 do N (N podane przez uzytkownika). Uzyj funkcji CzyPierwsza jako podprogramu.
FUNKCJA CzyPierwsza(n):
JESLI n <= 1 ZWROC FALSZ
JESLI n = 2 ZWROC PRAWDA
JESLI n MOD 2 = 0 ZWROC FALSZ
DLA i OD 3 DO sqrt(n), KROK 2:
JESLI n MOD i = 0 ZWROC FALSZ
ZWROC PRAWDA
ALGORYTM WypiszPierwsze(N):
1. Wczytaj N
2. DLA k OD 2 DO N:
a. JESLI CzyPierwsza(k) = PRAWDA:
- Wypisz k
3. KONIEC
Przyklad dla N = 20:
Wynik: 2 3 5 7 11 13 17 19