Pierwszosc, NWD (Euklides), systemy liczbowe - programowanie w Pythonie
ð Podstawa programowa: II.1+I.2aLiczba pierwsza to liczba naturalna wieksza od 1, ktora dzieli sie tylko przez 1 i przez siebie. Aby sprawdzic, czy n jest pierwsza, wystarczy sprawdzic dzielniki do √n.
import math
def czy_pierwsza(n):
"""Sprawdza, czy liczba n jest pierwsza."""
if n < 2:
return False
if n == 2:
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
# Test
for i in range(2, 30):
if czy_pierwsza(i):
print(i, end=" ") # 2 3 5 7 11 13 17 19 23 29Najwiekszy Wspolny Dzielnik (NWD) dwoch liczb mozna obliczyc algorytmem Euklidesa opartym na dzieleniu z reszta:
# Wersja z odejmowaniem
def nwd_odejmowanie(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return a
# Wersja z modulo (szybsza)
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
# NWW (Najmniejsza Wspolna Wielokrotnosc)
def nww(a, b):
return a * b // nwd(a, b)
print(f"NWD(48, 18) = {nwd(48, 18)}") # 6
print(f"NWW(48, 18) = {nww(48, 18)}") # 144Konwersja z systemu dziesietnego na dowolny system (2-16):
def na_system(n, podstawa):
"""Konwertuje liczbe n na system o danej podstawie."""
if n == 0:
return "0"
cyfry = "0123456789ABCDEF"
wynik = ""
while n > 0:
reszta = n % podstawa
wynik = cyfry[reszta] + wynik
n = n // podstawa
return wynik
print(na_system(255, 2)) # 11111111
print(na_system(255, 8)) # 377
print(na_system(255, 16)) # FF
# Wbudowane funkcje Pythona:
print(bin(255)) # 0b11111111
print(oct(255)) # 0o377
print(hex(255)) # 0xffdef rozklad(n):
"""Rozklada liczbe n na czynniki pierwsze."""
czynniki = []
dzielnik = 2
while n > 1:
while n % dzielnik == 0:
czynniki.append(dzielnik)
n = n // dzielnik
dzielnik += 1
return czynniki
print(rozklad(360)) # [2, 2, 2, 3, 3, 5]Napisz program, ktory wyswietla wszystkie liczby pierwsze w zakresie od a do b (podanych przez uzytkownika). Uzyj funkcji czy_pierwsza(n).
import math
def czy_pierwsza(n):
if n < 2:
return False
if n == 2:
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
a = int(input("Podaj poczatek zakresu: "))
b = int(input("Podaj koniec zakresu: "))
print(f"Liczby pierwsze od {a} do {b}:")
for n in range(a, b + 1):
if czy_pierwsza(n):
print(n, end=" ")Napisz program obliczajacy NWD i NWW trzech liczb podanych przez uzytkownika. Wskazowka: NWD(a, b, c) = NWD(NWD(a, b), c).
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
def nww(a, b):
return a * b // nwd(a, b)
a = int(input("Podaj a: "))
b = int(input("Podaj b: "))
c = int(input("Podaj c: "))
nwd3 = nwd(nwd(a, b), c)
nww3 = nww(nww(a, b), c)
print(f"NWD({a}, {b}, {c}) = {nwd3}")
print(f"NWW({a}, {b}, {c}) = {nww3}")Napisz program, ktory wczytuje liczbe dziesietna i wyswietla ja w systemie binarnym, osemkowym i szesnastkowym. Uzyj wlasnej funkcji na_system(n, podstawa).
def na_system(n, podstawa):
if n == 0:
return "0"
cyfry = "0123456789ABCDEF"
wynik = ""
while n > 0:
wynik = cyfry[n % podstawa] + wynik
n = n // podstawa
return wynik
liczba = int(input("Podaj liczbe dziesietna: "))
print(f"Binarnie (2): {na_system(liczba, 2)}")
print(f"Osemkowo (8): {na_system(liczba, 8)}")
print(f"Szesnastkowo (16): {na_system(liczba, 16)}")Napisz funkcje, ktora rozklada liczbe na czynniki pierwsze i wyswietla wynik w formie potegowej. Np. 360 = 2^3 * 3^2 * 5^1.
def rozklad_potegowy(n):
czynniki = {}
dzielnik = 2
while n > 1:
while n % dzielnik == 0:
czynniki[dzielnik] = czynniki.get(dzielnik, 0) + 1
n //= dzielnik
dzielnik += 1
return czynniki
liczba = int(input("Podaj liczbe: "))
czynniki = rozklad_potegowy(liczba)
czesci = []
for czynnik, potega in sorted(czynniki.items()):
czesci.append(f"{czynnik}^{potega}")
print(f"{liczba} = {' * '.join(czesci)}")
# Np. 360 = 2^3 * 3^2 * 5^1