Matura informatyka 2022 maj (poziom rozszerzony)

Treść zadania:

Znajdź w pliku liczby.txt:

liczbę, która ma w rozkładzie najwięcej czynników pierwszych (podaj tę liczbę oraz liczbę jej czynników pierwszych)
liczbę, która ma w rozkładzie najwięcej różnych czynników pierwszych (podaj tę liczbę oraz liczbę jej różnych czynników pierwszych).

Przykład: liczba 420=2·2·3·5·7 ma w rozkładzie 5 czynników pierwszych, w tym 4 różne czynniki pierwsze (2, 3, 5, 7).

Odpowiedź dla danych z pliku przyklad.txt: 144 6 210 4

(Liczba 144 ma najwięcej czynników pierwszych; liczba czynników pierwszych liczby 144 wynosi 6. Liczba 210 ma najwięcej różnych czynników pierwszych; liczba różnych czynników pierwszych liczby 210 wynosi 4).

Rozwiązanie:

Odczytujemy dane z pliku i konwertujemy je na int'y:

with open("dane/liczby.txt", "r") as f:
    nums = [int(num) for num in f.readlines()]

Następnie definiujemy funkcję get_prime_factors , której zadaniem jest zwrócenie listy czynników pierwszych

def get_prime_factors(n: int) -> list[int]:
    current_divider = 2
    factors = []
    while n > 1:
        if n % current_divider == 0:
            factors.append(current_divider)
            n = n / current_divider
        else:
            current_divider += 1

    return factors

Jej działanie opiera się na podobieństwie z sitem Eratostenesa. Więcej o algorytmie możesz przeczytać tutaj.

Z treści zadania wynika:

W pliku liczby.txt danych jest 200 różnych liczb całkowitych z zakresu [10, 100000]. Każda z tych liczb zapisana jest w osobnym wierszu. , że liczby są w zakresie [10, 100000], więc można bezpiecznie założyć, że naszymi minimami mogą być 0 i puste listy:

prime_factors = 0
prime_factors_list = []

unique_prime_factors = 0
unique_prime_factors_list = []

Dla każdej liczby wyznaczamy jej listę czynników pierwszych i tą listę bez duplikatów. Kolejne linijki sprowadzają się do porównania z poprzednimi wynikami i wypisaniem ich na ekran:

for num in nums:
    prime_factors_result = get_prime_factors(num)
    unique_prime_factors_result = set(prime_factors_result)
    if len(prime_factors_result) > len(prime_factors_list):
        prime_factors = num
        prime_factors_list = prime_factors_result
    if len(unique_prime_factors_result) > len(unique_prime_factors_list):
        unique_prime_factors = num
        unique_prime_factors_list = unique_prime_factors_result

print(f"{prime_factors} {len(prime_factors_list)}")
print(f"{unique_prime_factors} {len(unique_prime_factors_list)}")

Cały program:

with open("dane/liczby.txt", "r") as f:
    nums = [int(num) for num in f.readlines()]

def get_prime_factors(n: int) -> list[int]:
    current_divider = 2
    factors = []
    while n > 1:
        if n % current_divider == 0:
            factors.append(current_divider)
            n = n / current_divider
        else:
            current_divider += 1

    return factors

prime_factors = 0
prime_factors_list = []

unique_prime_factors = 0
unique_prime_factors_list = []

for num in nums:
    prime_factors_result = get_prime_factors(num)
    unique_prime_factors_result = set(prime_factors_result)
    if len(prime_factors_result) > len(prime_factors_list):
        prime_factors = num
        prime_factors_list = prime_factors_result
    if len(unique_prime_factors_result) > len(unique_prime_factors_list):
        unique_prime_factors = num
        unique_prime_factors_list = unique_prime_factors_result

print(f"{prime_factors} {len(prime_factors_list)}")
print(f"{unique_prime_factors} {len(unique_prime_factors_list)}")