A foundry casts n ingots, each starting with a positive integer mass. Call an ingot a reference ingot for a prime p if its starting mass is exactly p. For any ingot i, its current mass may be divided by a prime p, repeatedly, as long as it stays evenly divisible by p, provided at least one other ingot j (j != i) is a reference ingot for p; that reference role depends only on ingot j's starting mass, so it is permanent and unaffected by anything later done to ingot j itself (including reducing ingot j's own mass through other operations). An ingot can never use its own starting mass as its own reference — some other ingot must supply it, even when the two masses happen to coincide. These division operations may be applied to any ingot, using any eligible reference prime, any number of times, in any order. Find the minimum possible sum of all n ingots' masses achievable this way.
The first line contains an integer n. The second line contains n space-separated integers, the starting masses of the ingots.
Print a single integer: the minimum achievable total mass of all ingots.
Example 1
Input
4 18 2 2 25
Expected
36
Explanation
The starting masses are 18, 2, 2, and 25. Two ingots start at mass 2, a prime, so each is a valid reference for the other, meaning prime 2 is available to every ingot, including the two mass-2 ingots themselves. Ingot 18 = 2 x 3^2 loses its factor of 2, becoming 9. Each mass-2 ingot divides by the other's mass-2 reference, becoming 1. Ingot 25 = 5^2 has no reference for prime 5 anywhere among the other ingots, so it stays at 25. The total is 9 + 1 + 1 + 25 = 36.
Example 2
Input
3 9 3 3
Expected
3
Explanation
The starting masses are 9, 3, and 3. The two mass-3 ingots are each other's reference for prime 3 (a different ingot, so the rule is satisfied). Ingot 9 = 3^2 divides by 3 twice, becoming 1. Each mass-3 ingot divides by the other one's mass-3 reference, becoming 1 as well. The total is 1 + 1 + 1 = 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →