Read problems statements in Mandarin Chinese  and Russian. 

Roma gave Chef an array of intergers.

Chef wants to make all integers in the array equal to 1.

In a single operation, he can select a prime number p and a subset of the integers, and then divide all of the integers in the subset by p.

Chef can make this operation only if every integer in the selected subset is divisible by p.

Please help Chef to make all the integers in the array equal to 1 with minimum number of operations.

------ Input ------ 

The first line of input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the length of the array that Roma gave Chef.
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the integers in the array.

------ Output ------ 

For each test case, output a single line containing one integer - the minimum number of operations needed to make all numbers equal to 1.

------ Constraints ------ 

$Subtask 1 (10 points): T = 5, 1 ≤ N ≤ 10^{5}, 1 ≤ A_{i} ≤ 3$
$Subtask 2 (40 points): T = 3, 1 ≤ N ≤ 10, 1 ≤ A_{i} ≤ 10^{6}$
$Subtask 3 (50 points): T = 3, 1 ≤ N ≤ 10^{5}, 1 ≤ A_{i} ≤ 10^{6}$

----- Sample Input 1 ------ 
1
3
1 2 4
----- Sample Output 1 ------ 
2

Source: codechef | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
from collections import defaultdict
from sys import *

def input():
	return stdin.readline()
a = [True] * 1000100

def primes_sieve2(limit):
	a[0] = a[1] = False
	l = []
	for (i, isprime) in enumerate(a):
		if isprime:
			l.append(i)
			for n in range(i * i, limit, i):
				a[n] = False
	return l
prime = primes_sieve2(1000100)
fac = [[] for i in range(1000100)]
for i in prime:
	for j in range(i, 1000100, i):
		fac[j].append(i)

def get(divisors):
	div = fac[divisors]
	new = defaultdict(int)
	tar = divisors
	ind = 0
	while tar > 1:
		fir = div[ind]
		while tar > 1 and tar % fir == 0:
			tar //= fir
			new[fir] += 1
		ind += 1
	return new
for _ in range(int(input())):
	n = int(input())
	lis = [int(i) for i in input().split()]
	vis = defaultdict(list)
	it = 0
	for i in lis:
		for (i, j) in get(i).items():
			vis[i].append(j)
	for j in vis.values():
		it += max(j)
	print(it)


primes = [i for i in range(10 ** 6 + 4)]
prime = []

def seive():
	for i in range(2, len(primes)):
		if primes[i] == i:
			prime.append(i)
			j = 2 * i
			while j < len(primes):
				primes[j] = i
				j += i
seive()
for _ in range(int(input())):
	n = int(input())
	arr = [int(c) for c in input().split()]
	all = [0 for i in range(10 ** 6 + 5)]
	ans = 0
	for i in arr:
		x = i
		while x > 1:
			d = primes[x]
			cnt = 0
			while x % d == 0:
				x = x // d
				cnt += 1
			if all[d] < cnt:
				ans += cnt - all[d]
				all[d] = cnt
	print(ans)


from collections import defaultdict
f = list(range(10 ** 6 + 1))
for i in range(2, 10 ** 3):
	if f[i] != i:
		continue
	j = i << 1
	while j <= 10 ** 6:
		f[j] = i
		j += i
for _ in range(int(input())):
	input()
	max_prime_powers = defaultdict(int)
	xs = map(int, input().split())
	for x in xs:
		while x > 1:
			c = 0
			d = f[x]
			while x % d == 0:
				c += 1
				x //= d
			max_prime_powers[d] = max(max_prime_powers[d], c)
	print(sum(max_prime_powers.values()))


from collections import defaultdict
F = [0] * 1000005
ans = 0
for i in range(1, 1000001):
	F[i] = i
for i in range(2, 1000):
	if F[i] != i:
		continue
	j = i + i
	while j <= 1000000:
		F[j] = i
		j += i
for _ in range(int(input())):
	ALL = defaultdict(int)
	n = int(input())
	arr = list(map(int, input().split()))
	for ele in arr:
		while ele > 1:
			cnt = 0
			div = F[ele]
			while ele % div == 0:
				ele //= div
				cnt += 1
			if ALL[div] < cnt:
				ALL[div] = cnt
	print(sum(ALL.values()))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	if all((i <= 3 for i in l)):
		l = [i for i in l if i == 2 or i == 3]
		print(len(set(l)))
		continue
	from collections import Counter
	c = Counter(l)
	from collections import defaultdict
	ind = defaultdict(list)
	for i in range(n):
		ind[l[i]].append(i)
	m = max(l)
	ans = 0
	prm = [1] * (m + 1)
	for i in range(2, m + 1):
		if not prm[i]:
			continue
		maxi = 0
		for j in range(i, m + 1, i):
			prm[j] = 0
			if c[j]:
				for z in ind[j]:
					cnt = 0
					while l[z] % i == 0:
						l[z] = l[z] // i
						cnt += 1
					maxi = max(maxi, cnt)
					cnt = 0
		ans += maxi
	print(ans)


import sys
data = sys.stdin.read().split()
data.reverse()

def read():
	return int(data.pop())

def readStr():
	return data.pop()
N = 10 ** 6 + 5
sv = [i for i in range(N)]
for i in range(2, N):
	if i * i > N:
		break
	if sv[i] < i:
		continue
	for j in range(i * i, N, i):
		sv[j] = min(sv[j], i)
T = read()
for test in range(T):
	n = read()
	M = {}
	for i in range(n):
		a = read()
		while a > 1:
			(cur, tot) = (sv[a], 0)
			while not a % cur:
				a //= cur
				tot += 1
			if cur in M:
				M[cur] = max(M[cur], tot)
			else:
				M[cur] = tot
	print(sum(M.values()))


MAX = int(1000000.0) + 1
factors = [list() for x in range(MAX)]
isprime = [True for x in range(MAX)]
for i in range(2, MAX):
	if isprime[i]:
		for j in range(i, MAX, i):
			(counter, k) = (0, j)
			isprime[j] = False
			while k % i == 0:
				k /= i
				counter += 1
			factors[j].append((i, counter))
t = int(input().strip())
m = dict()
while t:
	n = int(input().strip())
	m.clear()
	for x in input().strip().split():
		for (f, e) in factors[int(x)]:
			m[f] = max(e, m.get(f, 0))
	print(sum(m.values()))
	t -= 1


from math import sqrt
from collections import defaultdict

def primes(n):
	pr = [True] * (n + 1)
	for p in range(2, int(sqrt(n))):
		if pr[p]:
			for i in range(p * 2, n + 1, p):
				pr[i] = False
	for p in range(2, n + 1):
		if pr[p]:
			prime.append(p)
			primer[p] = 1
prime = []
primer = [0] * 1000001
primes(1000000)
t = int(input())
while t > 0:
	n = int(input())
	hashmap = defaultdict(lambda : 0)
	a = [int(x) for x in input().split()]
	for num in a:
		if num is 1:
			continue
		hasher = defaultdict(lambda : 0)
		if primer[num] is 1:
			hasher[num] = 1
		else:
			index = 0
			while num > 1:
				if primer[num] is 1:
					hasher[num] += 1
					break
				if num % prime[index] is 0:
					num //= prime[index]
					hasher[prime[index]] += 1
				else:
					index += 1
		for key in hasher:
			if hasher[key] > hashmap[key]:
				hashmap[key] = hasher[key]
	count = 0
	for key in hashmap:
		count += hashmap[key]
	print(count)
	t -= 1