Read problems statements [Mandarin] , [Bengali] , [Hindi] , [Russian] and [Vietnamese] as well.

You are given an integer sequence $A_{1}, A_{2}, \dots, A_{N}$. Let's define the *useful number* of a subsequence of $A$ as the number of distinct primes $p$ such that $p$ divides each member of the subsequence, multiplied by the length of the subsequence. Find the maximum of useful numbers of all subsequences of $A$.

------  Input ------
The first line of the 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$.
The second line contains $N$ space-seperated integers $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
Print a single line containing one integer — the maximum useful number.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{5}$ for each valid $i$

------  Subtasks ------
Subtask #1 (30 points):
$1 ≤ N ≤ 15$
$1 ≤ A_{i} ≤ 100$ for each valid $i$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
1
5
2 2 4 17 8
----- Sample Output 1 ------ 
4
----- explanation 1 ------ 
Example case 1: The subsequence $[2, 2, 4, 8]$ has the maximum useful number. The number of distinct primes that divide each member of the subsequence is $1$ (only the prime $2$) and the length of the subsequence is $4$, so the useful number of this subsequence is $1\cdot 4 = 4$.

Source: codechef | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
N1 = 100001
divisors = [[] for d in range(N1)]
lpf = [0] * N1
for d in range(2, N1):
	if lpf[d]:
		for n in range(d, N1, d):
			divisors[n].append(d)
	else:
		for n in range(d, N1, d):
			lpf[n] = d
			divisors[n].append(d)
disp = [0, 0]
for n in range(2, N1):
	disp.append(disp[n // lpf[n]] + (n % (lpf[n] * lpf[n]) != 0))
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(int)
	for s in input().split():
		for i in divisors[int(s)]:
			d[i] += 1
	ans = 0
	for i in d:
		x = disp[i] * d[i]
		if x > ans:
			ans = x
	print(ans)


def func(i, counterArr):
	ans = 0
	for j in range(i, n, i):
		ans += counterArr[j]
	return ans
n = int(100000.0 + 1)
primes = [0] * n
for i in range(2, n):
	if primes[i] == 0:
		for j in range(i, n, i):
			primes[j] += 1
t = int(input())
from collections import Counter
for aaa in range(t):
	xxx = int(input())
	counterArr = Counter(map(int, input().split()))
	print(max((func(i, counterArr) * primes[i] for i in range(2, n))))


from collections import Counter
n = int(100000.0 + 1)
pf = [0] * n
for i in range(2, n):
	if pf[i] == 0:
		for j in range(i, n, i):
			pf[j] += 1
test = int(input())
for _ in range(test):
	input()
	cnt = Counter(map(int, input().split()))
	s = lambda i: sum((cnt[j] for j in range(i, n, i)))
	print(max((s(i) * pf[i] for i in range(2, n))))


p = 10 ** 5 + 9
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	from collections import Counter
	c = Counter(l)
	f = [0] * p
	maxi = 0
	for i in range(2, p):
		if f[i] == 0:
			for j in range(i, p, i):
				f[j] += 1
		cnt = 0
		for j in range(i, p, i):
			cnt += c[j]
		maxi = max(maxi, cnt * f[i])
	print(maxi)


from collections import Counter
N = 100001
pf = [0] * N
for i in range(2, N):
	if pf[i] == 0:
		for j in range(i, N, i):
			pf[j] += 1
t = int(input())
for _ in range(t):
	input()
	cnt = Counter(map(int, input().split()))
	s = lambda i: sum((cnt[j] for j in range(i, N, i)))
	print(max((s(i) * pf[i] for i in range(2, N))))


t = int(input())

def factors(a):
	count = 0
	while a % 2 == 0:
		a = a // 2
		count = 1
	for i in range(3, int(a ** 0.5) + 1, 2):
		if a % i == 0:
			count += 1
			while a % i == 0:
				a = a // i
	if a > 2:
		count += 1
	return count
factor = {}
for g in range(2, 10 ** 5 + 1):
	factor[g] = factors(g)
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	val = {}
	for i in a:
		val[i] = val.get(i, 0) + 1
	m = max(a)
	ma = 0
	for g in range(2, m + 1):
		f = factor[g]
		c = 0
		for i in range(g, m + 1, g):
			if i in val:
				c += val[i]
		if c * f > ma:
			ma = c * f
	print(ma)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
lim = 10 ** 5
p = [0] * (lim + 3)
for i in range(2, lim + 1):
	if p[i] == 0:
		for k in range(i, lim + 1, i):
			p[k] += 1
for _ in range(int(input())):
	n = input()
	ns = list(map(int, input().split()))
	maxN = max(ns)
	vs = [0] * (maxN + 3)
	for i in ns:
		vs[i] += 1
	maxi = 0
	for g in range(2, maxN + 1):
		size = 0
		for k in range(g, maxN + 1, g):
			size += vs[k]
		if p[g] * size > maxi:
			maxi = p[g] * size
	print(maxi)


N = 100001
pfc = [0] * N
f = [[] for _ in range(N)]
for i in range(2, N):
	if pfc[i] == 0:
		for j in range(i, N, i):
			pfc[j] += 1
			t = f[j][:]
			f[j].append(i)
			f[j].extend((x * i for x in t))
t = int(input())
for _ in range(t):
	input()
	d = [0] * N
	ans = 0
	cnt = [0] * N
	for x in map(int, input().split()):
		cnt[x] += 1
	for i in range(2, N):
		if cnt[i]:
			for v in f[i]:
				d[v] += pfc[v] * cnt[i]
	print(max(d))


from collections import Counter
N = 100001
pfc = [0] * N
f = [[] for _ in range(N)]
for i in range(2, N):
	if pfc[i] == 0:
		for j in range(i, N, i):
			pfc[j] += 1
			t = f[j][:]
			f[j].append(i)
			f[j].extend((x * i for x in t))
t = int(input())
for _ in range(t):
	input()
	d = [0] * N
	ans = 0
	for (x, c) in Counter(map(int, input().split())).items():
		for v in f[x]:
			d[v] += pfc[v] * c
	print(max(d))


N = 100001
pf = [0] * N
for i in range(2, N):
	if pf[i] == 0:
		for j in range(i, N, i):
			pf[j] += 1
t = int(input())
for _ in range(t):
	input()
	cnt = [0] * N
	m = 0
	for x in map(int, input().split()):
		cnt[x] += 1
		m = max(m, x)
	m += 1
	s = lambda i: sum((cnt[j] for j in range(i, m, i)))
	print(max((s(i) * pf[i] for i in range(2, m))))


N = 100001
pf = [[] for _ in range(N)]
for i in range(2, N):
	if not pf[i]:
		for j in range(i, N, i):
			t = pf[j][:]
			pf[j].append((i, 1))
			pf[j].extend(((x * i, c + 1) for (x, c) in t))
t = int(input())
for _ in range(t):
	input()
	d = [0] * N
	for x in map(int, input().split()):
		for (v, c) in pf[x]:
			d[v] += c
	print(max(d))


for _ in range(int(input())):
	n = input()
	ns = list(map(int, input().split()))
	maxN = max(ns)
	vs = [0] * (maxN + 3)
	for i in ns:
		vs[i] += 1
	p = [0] * (maxN + 3)
	maxi = 0
	for g in range(2, maxN + 1):
		size = 0
		prime = False
		if p[g] == 0:
			prime = True
		for k in range(g, maxN + 1, g):
			size += vs[k]
			if prime:
				p[k] += 1
		if prime:
			p[g] = 1
		if p[g] * size > maxi:
			maxi = p[g] * size
	print(maxi)


n = 10 ** 5 + 5
count = [0 for i in range(n + 1)]

def Sieve():
	prime = [True for i in range(n + 1)]
	p = 2
	while p <= n:
		if prime[p] == True:
			count[p] = 1
			for i in range(p * 2, n + 1, p):
				prime[i] = False
				count[i] += 1
		p += 1
Sieve()
import math

def get_divisors(element):
	i = 1
	while i <= math.sqrt(element):
		if element % i == 0:
			if element // i == i:
				count_of_divisors[i] += 1
			else:
				count_of_divisors[i] += 1
				count_of_divisors[element // i] += 1
		i += 1
T = int(input())
vec = [[] for i in range(100005)]
for k in range(1, 10 ** 5 + 1):
	for l in range(k, 10 ** 5 + 1, k):
		vec[l].append(k)
for t in range(T):
	count_of_divisors = [0 for i in range(n + 1)]
	ans = 0
	N = int(input())
	a = list(map(int, input().split()))
	for element in a:
		for j in vec[element]:
			count_of_divisors[j] += 1
	for j in range(n + 1):
		x = count[j] * count_of_divisors[j]
		if x > ans:
			ans = x
	print(ans)