Rozkład na czynniki pierwsze

Zadanie 10 z 10 · rozdział 7Trudność: 2 z 3pętlepierwszośćdzielnikizłożoność

Treść zadania

Napisz funkcję wypisz_rozklad(n), która wypisuje rozkład liczby n na czynniki pierwsze: czynniki w kolejności niemalejącej, oddzielone znakiem *, bez spacji. Każdy czynnik powtarzamy tyle razy, ile razy dzieli n.

Program wczytuje n i wywołuje funkcję.

Dane wejściowe

  • 1. linia: n — liczba naturalna (n ≥ 2)

Dane wyjściowe

Jedna linia: czynniki pierwsze liczby n oddzielone znakiem *. Jeśli n jest liczbą pierwszą, wypisz samo n.

Ograniczenia

  • $2 \leq n \leq 10^{10}$

Uwagi

  • Sprawdzaj kolejne dzielniki d = 2, 3, 4, …. Dopóki d dzieli n, wypisz d i podziel n przez d. Złożone d (np. 4) nigdy nie podzielą n, bo ich czynniki pierwsze zostały już wcześniej „wydzielone”.
  • **Wystarczy sprawdzać dzielniki d, dla których $d \cdot d \leq n$.** Gdyby liczba n była złożona, czyli $n = a \cdot b$ dla $2 \leq a \leq b$, to $a \cdot a \leq a \cdot b = n$ — miałaby więc dzielnik nie większy niż $\sqrt{n}$. Jeśli po zakończeniu pętli zostało n > 1, to pozostała liczba jest pierwsza i jest ostatnim czynnikiem.
  • To ważna oszczędność: dla liczby pierwszej rzędu $10^{10}$ pętla aż do n wykonałaby ok. $10^{10}$ obrotów (zbyt długo), a pętla do $\sqrt{n}$ — tylko ok. $10^5$.
  • Aby wypisać czynniki w jednej linii, użyj print(d, end=""), a znak * wypisuj przed każdym czynnikiem poza pierwszym.

Przykład

Wejście
60
Wyjście
2*2*3*5

$60 = 2 \cdot 2 \cdot 3 \cdot 5$.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 7

Zadania w tym rozdziale łączą pętle z funkcjami: implementujesz klasyczne algorytmy matematyczne (potęgowanie, silnia, NWD, NWW, pierwiastek, test pierwszości) bez gotowych funkcji bibliotecznych.

Konwencje wspólne:

  • Każde zadanie (i każdy podpunkt) to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Jeśli zadanie mówi „napisz funkcję”, zaimplementuj funkcję o podanej nazwie, która zwraca wynik przez return. Program wczytuje dane, wywołuje funkcję i wypisuje wynik — gotowy szkielet znajdziesz w sekcji Kod startowy.
  • Dane wejściowe wczytuj dokładnie w podanej kolejności, każdą wartość z osobnej linii.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
2
Oczekiwane wyjście
2

Test 2

Nie uruchomiono
Wejście
97
Oczekiwane wyjście
97

Test 3

Nie uruchomiono
Wejście
1024
Oczekiwane wyjście
2*2*2*2*2*2*2*2*2*2

Test 4

Nie uruchomiono
Wejście
360
Oczekiwane wyjście
2*2*2*3*3*5

Test 5

Nie uruchomiono
Wejście
9999999967
Oczekiwane wyjście
9999999967

Test 6

Nie uruchomiono
Wejście
9998000099
Oczekiwane wyjście
99989*99991

Test 7

Nie uruchomiono
Wejście
10000000000
Oczekiwane wyjście
2*2*2*2*2*2*2*2*2*2*5*5*5*5*5*5*5*5*5*5
Uruchom z własnymi danymi