3.3 Rozkłady Goldbacha w pliku przykładowym

Matura próbna grudzień 2022 - Matura z informatyki: arkusze krok po kroku (Python)

Zadanie 3.3 (4 pkt): na ile sposobów każdą liczbę można zapisać jako sumę dwóch liczb pierwszych (\( 22 = 3 + 19 = 5 + 17 = 11 + 11 \), a \( 3 + 19 \) i \( 19 + 3 \) to ten sam rozkład). Pierwszy składnik \( p \) wystarczy brać do \( x / 2 \), drugi to \( x - p \). Podaj liczbę z największą liczbą rozkładów i tę z najmniejszą, z liczbami rozkładów. Dla pliku przykładowego: 996 37 4 1.

def sieve(n):
    is_prime = [True] * (n + 1)  # indeks = liczba
    is_prime[0] = is_prime[1] = False
    i = 2
    while i * i <= n:  # wystarczy do pierwiastka: mniejsze wielokrotności skreśliły mniejsze i
        if is_prime[i]:
            j = i * i  # mniejsze wielokrotności i są już skreślone
            while j <= n:
                is_prime[j] = False
                j = j + i
        i = i + 1
    return is_prime


with open("liczby_przyklad.txt") as f:
    numbers = [int(line) for line in f]  # liczby parzyste z [4, 1 000 000]
is_prime = sieve(max(numbers))

# 3.3 rozkłady x = p + q z p <= q: wystarczy p do połowy x, q = x - p
primes = [p for p in range(2, len(is_prime)) if is_prime[p]]
ways = {}
for x in numbers:
    count = 0
    for p in primes:
        if p > x // 2:
            break
        if is_prime[x - p]:
            count = count + 1
    ways[x] = count
most = max(numbers, key=lambda x: ways[x])
fewest = min(numbers, key=lambda x: ways[x])

print("3.3", most, ways[most], fewest, ways[fewest])

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Matura z informatyki: arkusze krok po kroku·Zaloguj się, aby zapisać postęp na koncie.