from math import log
import sys
sys.path.insert(0,'X:\\Users\\Raphael\\Documents\\primes\\')
from prime_loader import get_prime
p_list = []
for i in range(10**3):
    p_list += get_prime(i*10**6)


def factor(n,skip = False):
    f = {}
    if n in p_list and not skip:
        f[n] = 1
        return f
    for p in p_list:
        if n%p == 0:
            max_p = int(log(n,p))
            for i in range(max_p,-1,-1):
                if n%(p**i) == 0:
                    f[p] = i
##                    print('{}**{}'.format(p,f[p]))
                    n //= p**i
                    break
        if n == 1:
            return f
def ff(n):
    main = {}
    for i in range(2,n+1):
        l = factor(i)
        for p in l.keys():
            try:
                main[p] += l[p]
            except KeyError:
                main[p] = l[p]
    return main
def prod(val,func = lambda x:x):
    v = 1
    for i in val:
        v *= func(i)
    return v
def toitent(n):
    f = factor(n)
    c = n//prod(f.keys())
    return c*prod(f.keys(),lambda x: x-1)