Implementacja testu pierwszosci i konwersji systemow liczbowych w Pythonie
ð Podstawa programowa: II.1+I.2aLiczba pierwsza to liczba naturalna wieksza od 1, ktora ma dokladnie dwa dzielniki: 1 i samej siebie. Przyklady: 2, 3, 5, 7, 11, 13, 17, 19, 23...
Aby sprawdzic, czy liczba n jest pierwsza, musimy sprawdzic, czy nie dzieli sie przez zadna liczbe od 2 do pierwiastka z n. Dlaczego wystarczy sprawdzac do pierwiastka? Jezeli n = a * b, to przynajmniej jeden z czynnikow a lub b musi byc mniejszy lub rowny pierwiastkowi z n.
# Algorytm badania pierwszosci - wersja podstawowa
def czy_pierwsza(n):
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
# Wersja zoptymalizowana - sprawdzanie do sqrt(n)
import math
def czy_pierwsza_opt(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
# Test
liczba = int(input("Podaj liczbe: "))
if czy_pierwsza_opt(liczba):
print(f"{liczba} jest liczba pierwsza")
else:
print(f"{liczba} NIE jest liczba pierwsza")Na poprzednich lekcjach poznalismy systemy liczbowe (DEC, BIN, OCT, HEX). Teraz napiszemy wlasne programy realizujace konwersje miedzy nimi. Skupimy sie na konwersji z systemu dziesietnego na dwojkowy.
Algorytm konwersji DEC na BIN: Dzielimy liczbe przez 2 i zapisujemy reszty z dzielenia. Nastepnie odczytujemy reszty od konca - to jest nasz wynik w systemie dwojkowym.
# Konwersja DEC na BIN - wlasna implementacja
def dec_na_bin(n):
if n == 0:
return "0"
wynik = ""
while n > 0:
reszta = n % 2
wynik = str(reszta) + wynik
n = n // 2
return wynik
# Test
liczba = int(input("Podaj liczbe dziesietna: "))
print(f"{liczba} w systemie binarnym to: {dec_na_bin(liczba)}")
print(f"Sprawdzenie (wbudowana): {bin(liczba)}")Python posiada rowniez wbudowane funkcje do konwersji:
bin(n) - konwersja na system binarny (z przedrostkiem 0b)oct(n) - konwersja na system osemkowy (z przedrostkiem 0o)hex(n) - konwersja na system szesnastkowy (z przedrostkiem 0x)int("101", 2) - konwersja z dowolnego systemu na dziesietny# Wbudowane funkcje konwersji
n = 42
print(f"DEC: {n}")
print(f"BIN: {bin(n)}") # 0b101010
print(f"OCT: {oct(n)}") # 0o52
print(f"HEX: {hex(n)}") # 0x2a
# Konwersja z BIN na DEC
print(int("101010", 2)) # 42Napisz program, ktory wczytuje liczbe od uzytkownika i sprawdza, czy jest ona pierwsza. Wyswietl odpowiedni komunikat.
import math
n = int(input("Podaj liczbe: "))
if n < 2:
print("To nie jest liczba pierwsza")
else:
pierwsza = True
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
pierwsza = False
break
if pierwsza:
print(f"{n} jest liczba pierwsza")
else:
print(f"{n} NIE jest liczba pierwsza")Napisz program, ktory wypisuje wszystkie liczby pierwsze z zakresu od 2 do n (n podane przez uzytkownika).
import math
def czy_pierwsza(n):
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
n = int(input("Podaj gorny zakres: "))
print(f"Liczby pierwsze od 2 do {n}:")
for i in range(2, n + 1):
if czy_pierwsza(i):
print(i, end=" ")Napisz program, ktory konwertuje liczbe z systemu dziesietnego na binarny BEZ uzycia wbudowanej funkcji bin(). Uzyj algorytmu dzielenia przez 2.
n = int(input("Podaj liczbe dziesietna: "))
if n == 0:
print("Wynik binarny: 0")
else:
wynik = ""
temp = n
while temp > 0:
wynik = str(temp % 2) + wynik
temp = temp // 2
print(f"{n} (DEC) = {wynik} (BIN)")
print(f"Sprawdzenie: {bin(n)}")Napisz program, ktory konwertuje liczbe z dowolnego systemu (2-16) na dowolny inny system. Uzyj wbudowanych funkcji Pythona int() i odpowiedniego algorytmu.
def konwertuj(liczba_str, baza_z, baza_na):
# Konwersja na system dziesietny
dec = int(liczba_str, baza_z)
# Konwersja z dziesietnego na docelowy
if dec == 0:
return "0"
cyfry = "0123456789ABCDEF"
wynik = ""
while dec > 0:
wynik = cyfry[dec % baza_na] + wynik
dec = dec // baza_na
return wynik
liczba = input("Podaj liczbe: ")
z = int(input("System zrodlowy (2-16): "))
na = int(input("System docelowy (2-16): "))
print(f"Wynik: {konwertuj(liczba, z, na)}")