---
title: WDI 4.4
---

"""
Specyfikacja
Wejście: n, k - dodatnie liczby całkowite, a1...ak - ciąd liczb naturalnych >1
Wyjście: p – największa liczba naturalna taka, że n jest podzielne przez a^p dla jakiegoś i{1, 2,…, k} oraz liczby ze zbioru { a1, …, ak } których p-ta potęga jest dzielnikiem n.

Idea rozwiązania:
1. Rozkładamy liczbę n na czynniki pierwsze:
    1.1 Sprawdzamy podzielność n przez każdą liczbę z zakresu [2, sqrt n]
    1.2 Jeśli n dzieli się przez wybraną liczbe, to wnosimy ją do słownika jako klucz i przypisujemy jej znaczenie +=1
    1.3. Jeśli n nie dzieli się przez liczbę, to przechodzimy do kolejnej
    1.4 Jeśli po zakończeniu pętli została nam liczba > 1, to ona jest liczbą pierwszą, którą też wnosimy do słownika
2. Z słownika wiebieramy p - największą potęgę
3. Sprawdzamy które czynniki piersze odpowiadają tej potędze i wnosimy je do listy
4. Wypisujęmy p oraz listę
"""

def primfacs(n):
    i = 2
    primfac = {}
    while i * i <= n:
        while n % i == 0:
            if i in primfac:
               primfac[i] += 1
            else:
                primfac[i] = 1
            n = int(n / i)
        i = i + 1 
    if n > 1:
        primfac[n] = 1
    p = max(primfac.values())
    print ("p =", p, "oraz n dzieli się przez", znajdz_mnoznik(p, primfac),"^",p)
    return primfac

def znajdz_mnoznik(p, primfac):
    result_list = []
    primfac_list = primfac.items()
    for num, q in primfac_list:
        if p == q:
            result_list.append(str(num))
    return "".join(result_list)
 

print(primfacs(16))


#v2
from wdi.lib.wdi import Array, printw


def get_index_by_name(source, name):
    for i in range(len(source)):
        if source[i][0] == name:
            return i
    return -1


def set_new_value(source, name):
    for i in range(len(source)):
        item = source[i]
        if item[0] == 0:
            item[0] = name
            item[1] = 1
            break


def get_max_value(source):
    max_value = source[0][1]
    for i in range(1, len(source)):
        value = source[i][1]
        if max_value < value:
            max_value = value
    return max_value


def primfacs(n, k):
    i = 2
    primfac = Array(k, 2)
    while i * i <= n:
        while n % i == 0:
            index = get_index_by_name(primfac, i)
            if index != -1:
               primfac[index][1] += 1
            else:
                set_new_value(primfac, i)
            n = n // i
        i = i + 1 
    if n > 1:
        set_new_value(primfac, n)
    p = get_max_value(primfac)
    print ("p =", p, "oraz n dzieli się przez", znajdz_mnoznik(p, primfac),"^",p)
    return primfac


def znajdz_mnoznik(p, primfac):
    result = ""
    for i in range(len(primfac)):
        if p == primfac[i][1]:
            result += str(primfac[i][0]) + ' '
    return result
 
result = primfacs(144 * 625, 5)

for i in range(len(result)):
    print(result[i][0], result[i][1])