import java.lang.Math; import java.io.*; import java.util.*; public class Solution { static BufferedReader in; static PrintStream out; static StringTokenizer tok; static int[] Primos; static int count = 0; static boolean[] mask; static void Criba(int n) { if(n%6==0)n++; mask = new boolean[n+1]; int raiz = (int)Math.sqrt(n); Primos = new int[n/2+1]; for (int i= 2; i <= 3; i++) for (int j = i*i; j <= n; j+=i) mask[j] = true; for(int i = 6; i<=raiz; i+=6) { i--; if(!mask[i]) for (int j = i*i; j <= n; j += i) mask[j] = true; i += 2; if(!mask[i]) for (int j = i*i; j <= n; j += i) mask[j] = true; i--; } Primos[0] = 2; Primos[1] = 3; count = 2; for(int i = 6; i <= n; i+=6) { if(!mask[i-1])Primos[count++] = i-1; if(!mask[i+1])Primos[count++] = i+1; } } static ArrayListdPrimos; //static ArrayListdMult; static void DescFact(long n) { dPrimos = new ArrayList(); //dMult = new ArrayList(); int raiz = (int)Math.sqrt(n); int mult = 0; int len = Primos.length; for (int i = 0; i (); cache.put(1l,1l); long result = 0; for (int i = 0; i < a.length; i++) { result += calc(a[i]); } return result; } static HashMap cache; static long calc(long n) { if(cache.containsKey(n)) return cache.get(n); DescFact(n); List copy = new ArrayList(dPrimos.size()); for (int i = 0; i < dPrimos.size(); i++) { copy.add(dPrimos.get(i)); } long best = 0; for (int i = 0; i < copy.size(); i++) { long p = copy.get(i); long d = n/p; long temp = 1l + p * calc(d); best = Math.max(best, temp); } cache.put(n, best); return best; } @SuppressWarnings("empty-statement") public static void main(String[] args) throws NumberFormatException, IOException { //in = new BufferedReader(new InputStreamReader(System.in)); //in = new BufferedReader(new FileReader("metro.txt")); //out = System.out; Scanner in = new Scanner(System.in); int n = in.nextInt(); long[] a = new long[n]; for(int a_i = 0; a_i < n; a_i++){ a[a_i] = in.nextLong(); } Criba((int)1e7); //Random r = new Random(); //cache = new HashMap(); //while(cache.size() < 1000000) //{ //long next = (long)1e11 + r.nextInt((int)1e9); //if(next > (long)1e12) //continue; //long[] a = new long[]{next}; //if(cache.size() > 500) // System.out.println(next + ": " + result + " cache: " + cache.size()); //} long result = longestSequence(a); System.out.println(result); in.close(); } static String nextToken() throws IOException { String line = ""; while(tok == null || !tok.hasMoreTokens()) { if((line = in.readLine()) != null) tok = new StringTokenizer(line); else return null; } return tok.nextToken(); } static int nextInt() throws NumberFormatException, IOException { return Integer.parseInt(nextToken()); } static long nextLong() throws NumberFormatException, IOException { return Long.parseLong(nextToken()); } }