Matura próbna informatyka 2022 grudzień (poziom rozszerzony)

Treść zadania:

Hipoteza Goldbacha głosi, że każda liczba parzysta większa od 2 jest sumą dwóch liczb pierwszych. Nie wiemy, czy ta hipoteza jest prawdziwa dla wszystkich liczb parzystych dodatnich, ale została potwierdzona dla wszystkich liczb „rozsądnej wielkości”, zwłaszcza dla nie przekraczających 1018. Oczywiście liczba może mieć więcej niż jeden rozkład na sumę dwóch liczb pierwszych, np. 22 = 19 + 3 = 17 + 5 = 11 + 11. Dla każdej z liczb z pliku liczby.txt rozstrzygnij, na ile różnych sposobów da się ją przedstawić jako sumę dwóch liczb pierwszych.

Podaj:

• liczbę, która ma najwięcej różnych rozkładów na sumę dwóch liczb pierwszych, oraz liczbę takich rozkładów

• liczbę, która ma najmniej różnych rozkładów na sumę dwóch liczb pierwszych, oraz liczbę takich rozkładów.

Uwaga: przyjmujemy, że dwa rozkłady są różne, jeśli nie zawierają takiej samej pary składników. Przykładowo: rozkłady 22 = 19 + 3 i 22 = 3 + 19 są takie same.

Dla pliku liczby_przyklad.txt odpowiedzią jest: 996 37 4 1 (liczba 996 ma 37 rozkładów, a 4 tylko jeden)

Rozwiązanie:

Na początku zdefiniujmy funkcję, która powie nam, czy dana funkcja jest liczbą pierwszą. Liczba pierwsza , jest liczbą naturalną większą od 1 oraz dzieli się przez 1 i samą siebie.

def is_prime(n: int) -> bool:
    if n < 2:
        return False

    range_limit = int(sqrt(n)) + 1

    for i in range(2, range_limit):
        if n % i == 0:
            return False
    return True

Nie ma sensu szukać zatem liczby pierwszej w zbiorze liczb mniejszych od 2. Zakładam, że do funkcji zostanie podana tylko liczba naturalna. Szukanie dzielnika liczby można ograniczyć do zakresu pierwiastka kwadratowego +1 - dla pewności :)

Później zdefiniujmy funkcję o nazwie goldbach, która zwróci nam listę z wszystkimi parami liczb pierwszych, których suma wynosi liczbę z parametru. Szukamy par do połowy + 1 liczby - gdybyśmy szukali do końca, wartości zaczęłbyby się powtarzać (w odwrotnej kolejności, np.: [3, 5] <=> [5,3] co nie jest różnym składnikiem).

def goldbach(n: int) -> list[[int, int]]:
    results = []
    for i in range(2, n // 2 + 1):
        difference = n - i
        if is_prime(i) and is_prime(difference):
            results.append([i, difference])

    return results

Ważnym warunkiem jest sprawdzenie, czy obydwie liczby są liczbami pierwszymi :)

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

Następnie otwieramy plik z danymi i każdy wiersz przekształcamy na int.

unique_nums = set(nums)
even_nums = filter(lambda x: x % 2 == 0, unique_nums)

W dwóch kolejnych linijkach używamy set , co pozwoli nam pozbyć się duplikatów z listy nums a następnie dla zmiennej even_nums filtrujemy listę unique_nums , żeby zawierała tylko wartości parzyste.

goldbach_results = map(
    lambda num: {"number": num, "total_sums": len(goldbach(num))}, even_nums)

sorted_goldbach_results = sorted(
    goldbach_results, key=lambda res: res['total_sums'])

print(f"lower goldbach result: {sorted_goldbach_results[0]}")
print(f"higher goldbach result: {sorted_goldbach_results[-1]}")

Następnie dla każdego numeru w even_nums zwracamy dict o strukturze:

{"number": num, "total_sums": len(goldbach(num))}

gdzie do number jest przypisywany aktualny numer, a do total_sums ilość par, które sumują się do wskazanej liczby pod właściwością number.

Sortujemy wyniki po właściwości total_sums, żeby móc łatwo wydobyć
liczbę, która ma najmniej / najwięcej różnych rozkładów na sumę dwóch liczb pierwszych, oraz liczbę takich rozkładów , co robimy w print 'ach :)

Cały program:

from math import sqrt


def is_prime(n: int) -> bool:
    if n < 2:
        return False

    range_limit = int(sqrt(n)) + 1

    for i in range(2, range_limit):
        if n % i == 0:
            return False
    return True


def goldbach(n: int) -> list[[int, int]]:
    results = []
    for i in range(2, n // 2 + 1):
        difference = n - i
        if is_prime(i) and is_prime(difference):
            results.append([i, difference])

    return results


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

unique_nums = set(nums)
even_nums = filter(lambda x: x % 2 == 0, unique_nums)

goldbach_results = map(
    lambda num: {"number": num, "total_sums": len(goldbach(num))}, even_nums)

sorted_goldbach_results = sorted(
    goldbach_results, key=lambda res: res['total_sums'])

print(f"lower goldbach result: {sorted_goldbach_results[0]}")
print(f"higher goldbach result: {sorted_goldbach_results[-1]}")