#!/usr/bin/env python3

import sys



from functools import reduce



import math



def is_prime(n):

    if n % 2 == 0 and n > 2: 

        return False

    for i in range(3, int(math.sqrt(n)) + 1, 2):

        if n % i == 0:

            return False

    return True



def sieve(n):

    n=int(n)

    # Create a boolean array "prime[0..n]" and initialize 

    # all entries it as true. A value in prime[i] will 

    # finally be false if i is Not a prime, else true. 

    prime = [True for i in range(n + 1)] 

    p = 2

    while (p * p <= n): 

          

        # If prime[p] is not changed, then it is a prime 

        if (prime[p] == True): 

              

            # Update all multiples of p 

            for i in range(p * 2, n + 1, p): 

                prime[i] = False

        p += 1

    prime[0]= False

    prime[1]= False



    return [i for i, p in enumerate(prime) if p]



def inthroot(x,n):

    "calculate floor(x**(1/n))"

    return math.floor(x**(1/n))



def is_a_power(n):

    "return (a,b) if n=a**b otherwise throw ValueError"

    for b in sieve( math.log2(n) +1 ):

        if b == 0:

            raise ValueError

            

        a = inthroot(n,b)

        if a**b == n:

            return a,b

    raise ValueError

    





def smooth_factorization(n):

    "return (p,e) where p is prime and n = p**e if such value exists, otherwise throw ValueError"

    e=1

    p=n

    while True:

        try:

            p,n = is_a_power(p)

            e = e*n

        except ValueError:

            break

    if is_prime(p): 

        return p,e





def factors(n):

    return set(

        reduce(

            list.__add__,

            ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0),

        )

    )

        

def solve(N: int):

    count = 0

    picked_z = set([])



    while True:

        zs = list(factors(N))

        zs.remove(1)



        for _ in range(len(zs)):

                    

            z = min(zs)

            i = zs.index(z)



            is_prime_power = smooth_factorization(z)

            if is_prime_power and z not in picked_z:

                picked_z.add(z)

                N = N / z

                count += 1

                del zs[i]

                break



            del zs[i]



        if len(zs) == 0:

            break



    print(count)

    return





# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)

def main():

    def iterate_tokens():

        for line in sys.stdin:

            for word in line.split():

                yield word



    tokens = iterate_tokens()

    N = int(next(tokens))  # type: int

    solve(N)





if __name__ == "__main__":

    main()

#!/usr/bin/env python3

import sys



from functools import reduce



import math





from collections import defaultdict

from math import sqrt



def is_prime(n):

    for i in range(2, int(sqrt(n))):

        if n % i == 0:

            return False

    return True



def prime_factors(n):

    primes = defaultdict(int)

    i = 2

    mx = sqrt(n)

    while n != 1:

        if n % i == 0:

            n = n // i

            primes[i] += 1

        elif i >= mx:

            if len(primes) == 0:

                primes[i] += 1

            elif is_prime(n):

                primes[i] += 1

            break

        else:

            i += 1

    return primes



def solve_n(x):

    return (-1 + sqrt(1 + 4 * 2* x)) / 2



def solve(N: int):

    fs = prime_factors(N)

    count = 0

    for key, value in list(fs.items()):

        val = solve_n(value)

        count += math.floor(val)



    print(count)

    return







# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)

def main():

    def iterate_tokens():

        for line in sys.stdin:

            for word in line.split():

                yield word



    tokens = iterate_tokens()

    N = int(next(tokens))  # type: int

    solve(N)





if __name__ == "__main__":

    main()

#!/usr/bin/env python3
import sys
from functools import reduce
import math


def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True


def sieve(n):
    n = int(n)
    # Create a boolean array "prime[0..n]" and initialize
    # all entries it as true. A value in prime[i] will
    # finally be false if i is Not a prime, else true.
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        # If prime[p] is not changed, then it is a prime
        if prime[p] == True:
            # Update all multiples of p
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0] = False
    prime[1] = False
    return [i for i, p in enumerate(prime) if p]


def inthroot(x, n):
    "calculate floor(x**(1/n))"
    return math.floor(x ** (1 / n))


def is_a_power(n):
    "return (a,b) if n=a**b otherwise throw ValueError"
    for b in sieve(math.log2(n) + 1):
        if b == 0:
            raise ValueError
        a = inthroot(n, b)
        if a**b == n:
            return a, b
    raise ValueError


def smooth_factorization(n):
    "return (p,e) where p is prime and n = p**e if such value exists, otherwise throw ValueError"
    e = 1
    p = n
    while True:
        try:
            p, n = is_a_power(p)
            e = e * n
        except ValueError:
            break
    if is_prime(p):
        return p, e


def factors(n):
    return set(
        reduce(
            list.__add__,
            ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0),
        )
    )


def solve(N: int):
    count = 0
    picked_z = set([])
    while True:
        zs = list(factors(N))
        zs.remove(1)
        for _ in range(len(zs)):
            z = min(zs)
            i = zs.index(z)
            is_prime_power = smooth_factorization(z)
            if is_prime_power and z not in picked_z:
                picked_z.add(z)
                N = N / z
                count += 1
                del zs[i]
                break
            del zs[i]
        if len(zs) == 0:
            break
    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == "__main__":
    main()

#!/usr/bin/env python3
import sys
from functools import reduce
import math
from collections import defaultdict
from math import sqrt


def is_prime(n):
    for i in range(2, int(sqrt(n))):
        if n % i == 0:
            return False
    return True


def prime_factors(n):
    primes = defaultdict(int)
    i = 2
    mx = sqrt(n)
    while n != 1:
        if n % i == 0:
            n = n // i
            primes[i] += 1
        elif i >= mx:
            if len(primes) == 0:
                primes[i] += 1
            elif is_prime(n):
                primes[i] += 1
            break
        else:
            i += 1
    return primes


def solve_n(x):
    return (-1 + sqrt(1 + 4 * 2 * x)) / 2


def solve(N: int):
    fs = prime_factors(N)
    count = 0
    for key, value in list(fs.items()):
        val = solve_n(value)
        count += math.floor(val)
    print(count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)


if __name__ == "__main__":
    main()

+from collections import defaultdict +from math import sqrt -    if n % 2 == 0 and n > 2: -        return False -    for i in range(3, int(math.sqrt(n)) + 1, 2): +    for i in range(2, int(sqrt(n))): -def sieve(n): -    n = int(n) -    # Create a boolean array "prime[0..n]" and initialize -    # all entries it as true. A value in prime[i] will -    # finally be false if i is Not a prime, else true. -    prime = [True for i in range(n + 1)] -    p = 2 -    while p * p <= n: -        # If prime[p] is not changed, then it is a prime -        if prime[p] == True: -            # Update all multiples of p -            for i in range(p * 2, n + 1, p): -                prime[i] = False -        p += 1 -    prime[0] = False -    prime[1] = False -    return [i for i, p in enumerate(prime) if p] +def prime_factors(n): +    primes = defaultdict(int) +    i = 2 +    mx = sqrt(n) +    while n != 1: +        if n % i == 0: +            n = n // i +            primes[i] += 1 +        elif i >= mx: +            if len(primes) == 0: +                primes[i] += 1 +            elif is_prime(n): +                primes[i] += 1 +            break +        else: +            i += 1 +    return primes -def inthroot(x, n): -    "calculate floor(x**(1/n))" -    return math.floor(x ** (1 / n)) - - -def is_a_power(n): -    "return (a,b) if n=a**b otherwise throw ValueError" -    for b in sieve(math.log2(n) + 1): -        if b == 0: -            raise ValueError -        a = inthroot(n, b) -        if a**b == n: -            return a, b -    raise ValueError - - -def smooth_factorization(n): -    "return (p,e) where p is prime and n = p**e if such value exists, otherwise throw ValueError" -    e = 1 -    p = n -    while True: -        try: -            p, n = is_a_power(p) -            e = e * n -        except ValueError: -            break -    if is_prime(p): -        return p, e - - -def factors(n): -    return set( -        reduce( -            list.__add__, -            ([i, n // i] for i in range(1, int(n**0.5) + 1) if n % i == 0), -        ) -    ) +def solve_n(x): +    return (-1 + sqrt(1 + 4 * 2 * x)) / 2 +    fs = prime_factors(N) -    picked_z = set([]) -    while True: -        zs = list(factors(N)) -        zs.remove(1) -        for _ in range(len(zs)): -            z = min(zs) -            i = zs.index(z) -            is_prime_power = smooth_factorization(z) -            if is_prime_power and z not in picked_z: -                picked_z.add(z) -                N = N / z -                count += 1 -                del zs[i] -                break -            del zs[i] -        if len(zs) == 0: -            break +    for key, value in list(fs.items()): +        val = solve_n(value) +        count += math.floor(val)