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 samej siebie. Liczby, ktore nie sa pierwsze (i sa wieksze od 1), nazywamy liczbami zlozonymi.
Najprostszy sposob sprawdzenia, czy liczba n jest pierwsza: sprawdzamy podzielnosc przez wszystkie liczby od 2 do n-1.
ALGORYTM: Czy n jest liczba pierwsza? (naiwny)
WEJSCIE: liczba naturalna n
1. JESLI n < 2, ZWROC "NIE" (nie jest pierwsza)
2. DLA i = 2, 3, 4, ..., n-1:
3. JESLI n mod i == 0:
4. ZWROC "NIE" (n dzieli sie przez i)
5. ZWROC "TAK" (n jest pierwsza)
KONIECImplementacja w Pythonie:
def czy_pierwsza_naiwna(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
# Test
print(czy_pierwsza_naiwna(17)) # True
print(czy_pierwsza_naiwna(15)) # FalseKluczowa obserwacja: jesli liczba n ma dzielnik d, to n/d tez jest dzielnikiem. Jeden z nich musi byc mniejszy lub rowny sqrt(n) (pierwiastek z n). Dlatego wystarczy sprawdzac podzielnosc do sqrt(n)!
Przyklad: Czy 97 jest pierwsza? sqrt(97) = 9.85, wiec sprawdzamy dzielniki 2, 3, 4, 5, 6, 7, 8, 9. Zaden nie dzieli 97, wiec 97 jest pierwsza.
ALGORYTM: Czy n jest liczba pierwsza? (zoptymalizowany)
WEJSCIE: liczba naturalna n
1. JESLI n < 2, ZWROC "NIE"
2. JESLI n == 2 lub n == 3, ZWROC "TAK"
3. JESLI n mod 2 == 0, ZWROC "NIE" (parzysta > 2)
4. DLA i = 3, 5, 7, ..., dopoki i*i <= n:
5. JESLI n mod i == 0:
6. ZWROC "NIE"
7. ZWROC "TAK"
KONIECImplementacja zoptymalizowana w Pythonie:
import math
def czy_pierwsza(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
# Testy
for x in range(1, 30):
if czy_pierwsza(x):
print(x, end=" ")
# Wynik: 2 3 5 7 11 13 17 19 23 29Dla liczby n = 1 000 003 (jest pierwsza):
Przeledzmy dzialanie algorytmu dla n = 29:
n = 29
n >= 2? TAK
n == 2 lub n == 3? NIE
n % 2 == 0? NIE (29 jest nieparzysta)
sqrt(29) = 5.39, wiec sprawdzamy i = 3, 5
i = 3: 29 % 3 = 2 (nie dzieli sie)
i = 5: 29 % 5 = 4 (nie dzieli sie)
i = 7: 7*7 = 49 > 29 (koniec petli)
Wynik: 29 jest liczba pierwsza!Sprawdz, czy nastepujace liczby sa pierwsze (uzyj metody z pierwiastkiem - sprawdzaj dzielniki do sqrt(n)):
a) 37
b) 51
c) 83
d) 91
a) 37: sqrt(37) = 6.08
37%2=1, 37%3=1, 37%5=2 -> PIERWSZA
b) 51: sqrt(51) = 7.14
51%2=1, 51%3=0 -> NIE PIERWSZA (51 = 3 x 17)
c) 83: sqrt(83) = 9.11
83%2=1, 83%3=2, 83%5=3, 83%7=6, 83%9=2 -> PIERWSZA
d) 91: sqrt(91) = 9.54
91%2=1, 91%3=1, 91%5=1, 91%7=0 -> NIE PIERWSZA (91 = 7 x 13)Przelecz (trace) dzialanie zoptymalizowanego algorytmu dla n = 47. Zapisz kazdy krok: wartosc i, wynik dzielenia n % i, decyzje.
n = 47
Krok 1: n < 2? NIE (47 >= 2)
Krok 2: n == 2 lub n == 3? NIE
Krok 3: n % 2 == 0? NIE (47 jest nieparzysta)
Krok 4: sqrt(47) = 6.86, sprawdzamy i = 3, 5
i = 3: 47 % 3 = 2 -> kontynuuj
i = 5: 47 % 5 = 2 -> kontynuuj
i = 7: 7*7 = 49 > 47 -> koniec petli
Wynik: 47 JEST liczba pierwszaNapisz program w Pythonie, ktory wypisuje wszystkie liczby pierwsze z zakresu od 1 do 100. Uzyj zoptymalizowanej funkcji czy_pierwsza().
import math
def czy_pierwsza(n):
if n < 2:
return False
if n == 2 or n == 3:
return True
if n % 2 == 0:
return False
for i in range(3, int(math.sqrt(n)) + 1, 2):
if n % i == 0:
return False
return True
print("Liczby pierwsze od 1 do 100:")
pierwsze = []
for n in range(1, 101):
if czy_pierwsza(n):
pierwsze.append(n)
print(pierwsze)
print(f"Liczba liczb pierwszych: {len(pierwsze)}")
# Wynik: [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]
# Liczba: 25Napisz program w Pythonie, ktory rozklada podana liczbe na czynniki pierwsze. Na przyklad: 60 = 2 x 2 x 3 x 5 = 2^2 x 3 x 5.
def rozklad(n):
czynniki = []
dzielnik = 2
while n > 1:
while n % dzielnik == 0:
czynniki.append(dzielnik)
n = n // dzielnik
dzielnik += 1
return czynniki
# Testy
liczba = int(input("Podaj liczbe: "))
wynik = rozklad(liczba)
print(f"{liczba} = {' x '.join(map(str, wynik))}")
# Przyklad: 360 = 2 x 2 x 2 x 3 x 3 x 5