```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n int
	fmt.Fscan(reader, &n)

	cnt := make([]int, 5005)
	for i := 0; i < n; i++ {
		var k int
		fmt.Fscan(reader, &k)
		if k > 5000 {
			k = 5000
		}
		cnt[k]++
	}

	// Prefix sums for O(1) range queries
	pref := make([]int, 5005)
	current := 0
	for i := 0; i <= 5000; i++ {
		current += cnt[i]
		pref[i] = current
	}

	getSum := func(l, r int) int {
		if l > r {
			return 0
		}
		res := pref[r]
		if l > 0 {
			res -= pref[l-1]
		}
		return res
	}

	// Sieve primes
	isPrime := make([]bool, 5005)
	for i := 2; i <= 5000; i++ {
		isPrime[i] = true
	}
	primes := []int{}
	for i := 2; i <= 5000; i++ {
		if isPrime[i] {
			primes = append(primes, i)
			for j := i * i; j <= 5000; j += i {
				isPrime[j] = false
			}
		}
	}

	// Legendre's formula
	getPrimeCount := func(n, p int) int {
		c := 0
		for n > 0 {
			c += n / p
			n /= p
		}
		return c
	}

	var currentCost int64 = 0
	// Calculate initial cost (sum of all path lengths to root)
	for _, p := range primes {
		var pCost int64 = 0
		for k := 1; k <= 5000; k++ {
			if cnt[k] > 0 {
				pCost += int64(cnt[k]) * int64(getPrimeCount(k, p))
			}
		}
		currentCost += pCost
	}

	L, R := 0, 5000

	// Iterate primes descending
	for i := len(primes) - 1; i >= 0; i-- {
		p := primes[i]
		currentTaken := 0

		for {
			// Find smallest M in [L, R] such that E_p(M!) > currentTaken
			low, high := L, R
			M := -1
			for low <= high {
				mid := (low + high) / 2
				if getPrimeCount(mid, p) > currentTaken {
					M = mid
					high = mid - 1
				} else {
					low = mid + 1
				}
			}

			if M == -1 {
				// No group supports taking more p, proceed to next prime
				break
			}

			// M found. Support group for taking p is [M, R].
			support := getSum(M, R)

			if support*2 > n {
				// Majority wants p
				currentCost -= int64(2*support - n)
				L = M
				currentTaken++
			} else {
				// Majority does not want p.
				// Check if majority wants to switch (next prime)
				// Switch group: [L, M-1]
				switchGroup := getSum(L, M-1)
				if switchGroup*2 > n {
					R = M - 1
					break // break inner loop, continue to next prime
				} else {
					// Median found
					fmt.Fprintln(writer, currentCost)
					return
				}
			}
		}
		if L > R {
			break
		}
	}

	fmt.Fprintln(writer, currentCost)
}
```