# Matura informatyka 2022 maj (poziom rozszerzony) - zadanie 4.2

## 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:

```python
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

```python
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](https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/).

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:

```python
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:

```python
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:

```python
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)}")
```

## Wynik:

```markdown
99792 10
62790 6
```

%[https://replit.com/@Onix95/42-1#4/4_2.py] 

Źródło: [**https://arkusze.pl/matura-informatyka-2022-maj-poziom-rozszerzony/**](https://arkusze.pl/matura-informatyka-2022-maj-poziom-rozszerzony/)