4. Potyczki Informatyczne Nowej Generacji

Zadanie eliminacyjne w konkursie WIPING4 organizowanym przez
Wydział Informatyki Zachodniopomorskiego Uniwersytetu Technologicznego w Szczecinie

Faktoryzacja

Faktoryzacja, czyli rozkład na czynniki, to proces, który dla pewnej liczby naturalnej n prowadzi do znalezienia wszystkich czynników różnych od 1 i od n, których iloczyn jest równy n.  Twoim zadaniem jest napisanie programu, który będzie faktoryzował liczbę naturalną podaną na wejście.

Wejś›cie

• jeden wiersz tekstu, zawierający liczbę naturalną n, 2 ≤ n ≤ 2³⁴  

Wyjś›cie

• lista znalezionych czynników, mająca postać wierszy, z których każdy zawiera wartość czynnika i jego liczność w rozkładzie, rozdzielone przecinkiem lub słowo PRIME, jeśli faktoryzacja nie może zostać wykonana
  

Przykł‚ad

Wejś›cie: 

120

Wyjście:

2,3
3,1
5,1

Wskazówka:

120 = 2 ∙ 2  ∙2 ∙ 3 ∙ 5 = 3 ∙ 2 + 1 ∙ 3 + 1 ∙ 5

Informacje dodatkowe

• program zostanie uruchomiony 10 razy dla różnych zestawów danych
  

• każde poprawne rozwią…zanie daje 10% punktacji zadania
• zadanie ma wartość‡ punktową… 3,0