#!/bin/python3 import sys import functools fs = {} def factor(n, startFrom=2): n2 = n if n not in fs: if n <= 1: return [ ] d = startFrom factors = [ ] while n >= d*d: if n % d == 0: factors.append(d) n = n/d else: d += 1 + d % 2 # 2 -> 3, odd -> odd + 2 factors.append(n) fs[n2] = factors return fs[n2] def listPrimes(n): '''Return a list of all primes < n using the Sieve of Eratosthenes.''' if n <= 2: return [] sieve = [True]*n # indices 0 ... n-1, ignore 1 and even. Entries at odd # indices greater than 2 will be changed to false when found not prime primes = [2] i = 3 while(i < n): if sieve[i]: # First number not eliminated must be prime primes.append(i) # next eliminate multiples of i: for mult in range(i*i, n, i): # Note multiples with a smaller sieve[mult] = False # factor are already eliminated i += 2 # skip even numbers return primes def factorGivenPrimes(n, primes): p = 0 # in case primes seq empty factors = [] for p in primes: while n % p == 0: n /= p factors.append(p) if n < p*p: if n > 1: factors.append(n) return factors return factors + factor(n, p+2) #revert to brute force if not enough primes ps = listPrimes(10**6) def ls(a): if a == 1: return 1 facs = factorGivenPrimes(a, ps) if len(facs) == 0: return a + 1 x = 1 for f in facs: while a % f == 0: a /= f x *= f x += 1 return int(x) def longestSequence(a): return sum([ls(x) for x in a]) # Return the length of the longest possible sequence of moves. if __name__ == "__main__": n = int(input().strip()) a = list(map(int, input().strip().split(' '))) result = longestSequence(a) print(result)