Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.8 kB
3
Indexable
Never
package com.company;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> primes
            = new ArrayList<>();
    static int MAX = 2000000;
    static int[] sum_of_divisor = new int[MAX];

    static void steve() {
        boolean[] arr = new boolean[MAX];
        Arrays.fill(arr, true);
        arr[0] = arr[1] = false;

        for (int i = 2; i < Math.sqrt(MAX) + 1; i++) {
            if (arr[i]) {
                for (int j = i * 2; j < MAX; j += i) {
                    arr[j] = false;
                }
            }
        }
        for (int i = 2; i < MAX; i++) {
            if (arr[i]) {
                primes.add(i);
                sum_of_divisor[i] = i;
            }
        }
    }

    public static void phanTich() {
        sum_of_divisor[1] = 1;
        for (int i = 2; i < MAX; i++) {
            if (sum_of_divisor[i] != 0)
                continue;

            int smallest_divisor_index = 0;
            while (i % primes.get(smallest_divisor_index) != 0)
                smallest_divisor_index++;

            int smallest_divisor = primes.get(smallest_divisor_index);
            sum_of_divisor[i] = smallest_divisor + sum_of_divisor[i / smallest_divisor];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        Arrays.sort(arr);
        MAX = arr[n - 1] + 1;
        steve();
        phanTich();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += sum_of_divisor[arr[i]];
        }
        System.out.println(ans);
    }
}