Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases.

But Zulu warns him that a group of k > 1 Pokemon with strengths {s_1, s_2, s_3, ..., s_{k}} tend to fight among each other if gcd(s_1, s_2, s_3, ..., s_{k}) = 1 (see notes for gcd definition).

Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take? 

Note: A Pokemon cannot fight with itself.


-----Input-----

The input consists of two lines.

The first line contains an integer n (1 ≤ n ≤ 10^5), the number of Pokemon in the lab.

The next line contains n space separated integers, where the i-th of them denotes s_{i} (1 ≤ s_{i} ≤ 10^5), the strength of the i-th Pokemon.


-----Output-----

Print single integer — the maximum number of Pokemons Bash can take.


-----Examples-----
Input
3
2 3 4

Output
2

Input
5
2 3 4 6 7

Output
3



-----Note-----

gcd (greatest common divisor) of positive integers set {a_1, a_2, ..., a_{n}} is the maximum positive integer that divides all the integers {a_1, a_2, ..., a_{n}}.

In the first sample, we can take Pokemons with strengths {2, 4} since gcd(2, 4) = 2.

In the second sample, we can take Pokemons with strengths {2, 4, 6}, and there is no larger group with gcd ≠ 1.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
M = 10 ** 5
n = int(input())
ss = [int(s) for s in input().split()]
prime_factor = [set() for i in range(M + 1)]
for p in range(2, M + 1):
	if prime_factor[p] != set():
		continue
	else:
		for i in range(p, M + 1, p):
			prime_factor[i].add(p)
cnt = [0] * (M + 1)
for s in ss:
	for p in prime_factor[s]:
		cnt[p] += 1
print(max(1, max(cnt)))


import functools

@functools.lru_cache(maxsize=10000)
def factor(n):
	res = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			res.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		res.append(n)
	return set(res)
num = int(input())
poks = list(map(int, input().split()))[:num]
c = dict()
for p in poks:
	for d in factor(p):
		if d in c.keys():
			c[d] += 1
		else:
			c[d] = 1
if c:
	print(max(c.values()))
else:
	print(1)


n = int(input())
s = map(int, input().split())
pf = [[] for _ in range(10 ** 5 + 1)]
for i in range(2, 10 ** 5 + 1):
	if len(pf[i]) > 0:
		continue
	for j in range(i, 10 ** 5 + 1, i):
		pf[j].append(i)
f = [0] * (10 ** 5 + 1)
for x in s:
	for i in pf[x]:
		f[i] += 1
print(max(1, max(f)))


dict = {}
ans = {}
for i in range(-1, 100110):
	dict[i] = []
	ans[i] = 0
for i in range(2, 100010):
	if dict[i] == []:
		j = i + i
		while j <= 100010:
			tmp = dict[j]
			tmp += [i]
			dict[j] = tmp
			j += i
		dict[i] = [i]
n = input()
n = input()
n = n.split(' ')
banyak = 0
for i in n:
	tmp = int(i)
	for j in dict[tmp]:
		ans[j] += 1
		if ans[j] > banyak:
			banyak = ans[j]
if banyak == 0:
	banyak = 1
print(banyak)


from sys import stdin, stdout
size = 10 ** 5
n = int(stdin.readline())
value = list(map(int, stdin.readline().split()))
counting = [0 for i in range(size + 1)]
ans = 1
for i in range(n):
	counting[value[i]] += 1
value = sorted(list(set(value)))
for i in range(2, size + 1):
	cnt = 0
	j = 1
	while i * j <= size:
		cnt += counting[i * j]
		j += 1
	ans = max(ans, cnt)
stdout.write(str(ans))


import math
N = int(input())
S = [int(s) for s in input().split()]
max_s = max(S)
factors = [set() for i in range(max_s + 1)]
fact_cnt = [0] * (max_s + 1)
for p in range(2, max_s + 1):
	if factors[p] != set():
		continue
	else:
		for i in range(p, max_s + 1, p):
			factors[i].add(p)
for s in S:
	for p in factors[s]:
		fact_cnt[p] += 1
ans = max(1, max(fact_cnt))
print(ans)


from collections import defaultdict
np = 10 ** 5 + 100
prime = [[] for _ in range(np)]
for i in range(2, np, 2):
	prime[i].append(2)
for i in range(3, np, 2):
	if not prime[i]:
		for j in range(i, np, i):
			prime[j].append(i)
ans = [0] * np
ans[0] = 1
n = int(input())
nums = list(map(int, input().split()))
for i in nums:
	for j in prime[i]:
		ans[j] += 1
print(max(ans))


def genprimes(limit):
	lim12 = max(limit, 12)
	lim = lim12 // 6
	sieve = [False, True, True] * lim
	lim = lim * 3 - 1
	for (i, s) in enumerate(sieve):
		if s:
			(p, pp) = (i * 2 + 3, (i + 3) * i * 2 + 3)
			le = (lim - pp) // p + 1
			if le > 0:
				sieve[pp::p] = [False] * le
			else:
				break
	sieve[0] = sieve[3] = True
	res = [i for (i, s) in zip(range(3, lim12, 2), sieve) if s]
	res[:4] = (2, 3, 5, 7)
	while res[-1] >= limit:
		del res[-1]
	return res

def main():
	n = int(input())
	ss = list(map(int, input().split()))
	mx = max(ss) + 1
	l = [0] * mx
	for s in ss:
		l[s] += 1
	res = [1]
	for p in genprimes(mx + 1):
		res.append(sum(l[::p]))
	print(max(res))
main()


def prime_t(t):
	i = 2
	while i ** 2 <= t:
		if t % i == 0:
			return 0
		i += 1
	return 1

def prime_list(tt):
	p_list = []
	for i in range(2, tt + 1):
		if prime_t(i):
			p_list.append(i)
	return p_list
n = int(input())
l = [int(i) for i in input().split()]
d = {}
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
l = list(set(l))
l.sort()
chk = prime_list(max(l))
ans = [0] * (len(chk) + 1)
for i in l:
	tmp = i
	for (j, k) in enumerate(chk):
		if i % k == 0:
			ans[j] += d[tmp]
			while i % k == 0:
				i //= k
		if i < k:
			break
print(max(max(ans), 1))


def function1(n, s):
	if n == 1:
		return 1
	sn = max(s)
	pokemonj = 0
	pokecage = [0 for i in range(sn + 1)]
	for i in range(n):
		pokecage[s[i]] += 1
	maxyincage = min(pokecage[1], 1)
	sqrt = int(sn ** 0.5) + 1
	a = [i for i in range(sn + 1)]
	a[1] = 0
	i = 2
	for i in range(sqrt):
		if a[i] != 0:
			for j in range(i ** 2, sn + 1, i):
				a[j] = 0
	for i in range(sn + 1):
		if a[i] != 0:
			maxyincage = max(sum(pokecage[i:sn + 1:i]), maxyincage)
		i += 1
	return maxyincage

def main():
	n = int(input())
	s = list(map(int, input().split()))
	print(function1(n, s))
main()


import sys
from collections import defaultdict
import math
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(1)
	sys.exit(0)
div = defaultdict(lambda : 0)
for x in a:
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			if i ** 2 == x:
				div[i] += 1
			else:
				div[i] += 1
				div[x / i] += 1
	div[x] += 1
maxi = 1
for x in div:
	if x != 1:
		maxi = max(div[x], maxi)
print(maxi)


from collections import Counter
x = int(input())
a = list(map(int, input().split()))
lol = []
for i in a:
	for j in range(2, int(pow(i, 0.5)) + 1):
		if i % j == 0:
			while i % j == 0:
				i //= j
			lol.append(j)
	if i > 1:
		lol.append(i)
c = Counter(lol)
k = 1
for i in lol:
	k = max(k, c[i])
print(k)


from collections import Counter
n = int(input())
a = [int(_) for _ in input().split()]
f = Counter(a)
N = 10 ** 5 + 10
p = [0 for i in range(N)]
ans = Counter()
for i in range(2, N):
	if p[i]:
		continue
	for j in range(i, N, i):
		p[j] = 1
		ans[i] += f[j]
print(max(1, ans.most_common(1)[0][1]))


n = int(input())
(s, cnt) = (list(map(int, input().split())), [0] * 100001)
for i in range(n):
	cnt[s[i]] += 1
print(max(1, max([sum([cnt[i] for i in range(j, 100001, j)]) for j in range(2, 100001)])))


import sys
input = sys.stdin.readline
from collections import Counter
MAX = 10 ** 5
factors = [0] * (MAX + 1)
n = int(input())
s = Counter(map(int, input().split()))
for (item, count) in s.items():
	mx = int(item ** 0.5) + 1
	d = 2
	while d <= mx and item > 1:
		if item % d == 0:
			factors[d] += count
			while item % d == 0:
				item //= d
		d += 1
	if item > 1:
		factors[item] += count
best = 1
for i in range(MAX + 1):
	best = max(best, factors[i])
print(best)


n = int(input())
d = {}
l = list(map(int, input().split()))
for i in range(n):
	x = int(l[i] ** 0.5) + 1
	for j in range(2, x):
		if l[i] % j == 0:
			d[j] = d.get(j, 0) + 1
		while l[i] % j == 0:
			l[i] //= j
	if l[i] > 1:
		d[l[i]] = d.get(l[i], 0) + 1
if d == {}:
	print(1)
	exit(0)
print(max(1, max(d.values())))


n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 100100
for i in a:
	cnt[i] += 1
ans = 1
for i in range(2, 100001):
	p = 0
	for j in range(i, 100001, i):
		p += cnt[j]
	ans = max(ans, p)
print(ans)


def prime_t(t):
	i = 2
	while i ** 2 <= t:
		if t % i == 0:
			return 0
		i += 1
	return 1
p = []
for i in range(2, 100001):
	if prime_t(i):
		p.append(i)
n = int(input())
ol = [int(i) for i in input().split()]
l = [i for i in ol if int(i) % 2]
ans = max(1, n - len(l))
pd = {i: 0 for i in p}
for i in ol:
	if i in pd:
		pd[i] += 1
		ans = max(ans, pd[i])
l = [i for i in ol if i not in pd]
ld = {}
for i in l:
	if i in ld:
		ld[i] += 1
	else:
		ld[i] = 1
setl = set(l)
mol = list(setl)
mol.sort()
for i in mol:
	so = i
	for j in p:
		tmp = 1
		if j / 2 > so:
			break
		elif so % j == 0:
			pd[j] += ld[i]
			while so % j == 0:
				so //= j
			ans = max(ans, pd[j], tmp)
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = 1
count = [0] * 100001
for i in a:
	count[i] += 1
for i in range(2, 100001):
	s = 0
	for j in range(i, 100001, i):
		s += count[j]
	ans = max(ans, s)
print(ans)


n = int(input())
l = [int(i) for i in input().split()]
res = 1
p = 10 ** 5 + 1
cnt = [0] * p
for i in l:
	cnt[i] += 1
for i in range(2, p):
	c = 0
	for j in range(i, p, i):
		c += cnt[j]
	res = max(c, res)
print(res)


n = int(input())
a = list(map(int, input().split()))
k = 1
s = [0] * 100001
for i in a:
	s[i] += 1
for i in range(2, 100001):
	p = 0
	for j in range(i, 100001, i):
		p += s[j]
	k = max(k, p)
print(k)


import functools
import sys
input = lambda : sys.stdin.readline()

@functools.lru_cache(maxsize=10000)
def factor(n):
	res = []
	d = 2
	while d * d <= n:
		if n % d == 0:
			res.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		res.append(n)
	return set(res)

def Main(n):
	A = list(map(int, input().split()))[:n]
	dic = dict()
	for p in A:
		for d in factor(p):
			if d in dic.keys():
				dic[d] += 1
			else:
				dic[d] = 1
	if dic:
		print(max(dic.values()))
	else:
		print(1)

def __starting_point():
	n = int(input())
	Main(n)
__starting_point()


n = int(input())
ip = list(map(int, input().split()))
m = max(ip)
arr = [0 for i in range(m + 1)]
for i in ip:
	arr[i] += 1
ans = 0
for i in range(2, m + 1):
	j = i
	count = 0
	while j <= m:
		count += arr[j]
		j += i
	if count > ans:
		ans = count
print(max(ans, 1))


val = int('1' + '0' * 5)
freequency = [0] * (val + 1)
n = int(input())
l = list(map(int, input().split()))
for x in range(n):
	freequency[l[x]] += 1
ans = 1
for x in range(2, val + 1):
	count = 0
	for y in range(x, val + 1, x):
		count += freequency[y]
	ans = max(ans, count)
print(ans)


from math import sqrt
from collections import defaultdict
n = int(input())
l = list(map(int, input().split()))
d = defaultdict(int)
for p in l:
	a = int(sqrt(p))
	for i in range(2, a + 1):
		if p % i == 0:
			d[i] += 1
			while p % i == 0:
				p //= i
	if p > 1:
		d[p] += 1
ans = 1
for p in d.values():
	ans = max(ans, p)
print(ans)


from collections import OrderedDict
import collections

def prime_factors(n):
	i = 2
	factors = []
	count = 0
	while i * i <= n:
		count += 1
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors

def primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
n = int(input())
pokemons = []
pokemons = [int(x) for x in input().split(' ')]
counter = collections.Counter(pokemons)
pokemons_reduced = list(counter.keys())
frequency = list(counter.values())
prime_numbers = primes(max(pokemons) + 1)
ans = [0] * len(prime_numbers)
i = 0
while i < len(pokemons_reduced):
	test = pokemons_reduced[i]
	factors = list(OrderedDict.fromkeys(prime_factors(test)))
	for factor in factors:
		ans[prime_numbers.index(factor)] += 1 * frequency[i]
	i += 1
if max(ans) == 0:
	print(1)
else:
	print(max(ans))


n = int(input())
a = list(map(int, input().split()))
b = [0] * 100001
c = []
for i in a:
	b[i] += 1
for i in range(2, 100001):
	sum = 0
	for j in range(i, 100001, i):
		sum += b[j]
	c.append(sum)
print(max(max(c), 1))


import math
import sys, string, bisect
input = sys.stdin.readline
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
MAXN = 100001
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return set(ret)
sieve()
n = I()
l = L()
d = defaultdict(int)
m = 1
for i in l:
	if i != 1:
		t = getFactorization(i)
		for k in t:
			d[spf[k]] += 1
			if m < d[spf[k]]:
				m = d[spf[k]]
print(m)


def function1(n, s):
	if n == 1:
		return 1
	sn = max(s)
	pokecage = [0] * (sn + 1)
	for i in range(n):
		pokecage[s[i]] += 1
	maxyincage = min(pokecage[1], 1)
	a = [True] * 100001
	a[2 * 2::2] = [False] * len(a[2 * 2::2])
	y = (3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317)
	if sn > 2:
		for y in y:
			a[y * y::y + y] = [False] * len(a[y * y::y + y])
	for i in range(2, sn + 1):
		if a[i]:
			maxyincage = max(sum(pokecage[i:sn + 1:i]), maxyincage)
	return maxyincage

def main():
	n = int(input())
	s = list(map(int, input().split()))
	print(function1(n, s))
main()


def main():
	n = input()
	L = [int(x) for x in input().split()]
	print(solver(L))

def solver(L):
	n = max(L)
	nums = [0] * (n + 1)
	for x in L:
		nums[x] += 1
	highestCount = 1
	for i in range(2, n + 1):
		count = sum(nums[i:n + 1:i])
		highestCount = max(highestCount, count)
	return highestCount

def maxCount(L):
	d = dict()
	for x in L:
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	d[1] = 1
	return max([d[x] for x in d])
main()


def function1(n, s):
	if n == 1:
		return 1
	pokemonj = 0
	pokecage = [0 for i in range(100001)]
	for i in range(n):
		pokecage[s[i]] += 1
	maxyincage = min(pokecage[1], 1)
	a = [i for i in range(100001)]
	a[1] = 0
	i = 2
	while i <= 100000:
		if a[i] != 0:
			pokemonj = 0
			for j in range(i, 100001, i):
				a[j] = 0
				pokemonj += pokecage[j]
			if pokemonj > maxyincage:
				maxyincage = pokemonj
		i += 1
	return maxyincage

def main():
	n = int(input())
	s = list(map(int, input().split()))
	print(function1(n, s))

def __starting_point():
	main()
__starting_point()


def function1(n, s):
	if n == 1:
		return 1
	sn = max(s)
	pokecage = [0] * (sn + 1)
	for i in range(n):
		pokecage[s[i]] += 1
	maxyincage = min(pokecage[1], 1)
	a = [True, True, True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False] + [False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False] * (sn // 30 + 1)
	b = [1, 2, 3, 5]
	for i in range(7, sn + 1):
		if a[i]:
			b.append(i)
			for j in range(i ** 2, sn + 1, i * 2):
				a[j] = False
		i += 1
	for b in b[1:]:
		maxyincage = max(sum(pokecage[b:sn + 1:b]), maxyincage)
	return maxyincage

def main():
	n = int(input())
	s = list(map(int, input().split()))
	print(function1(n, s))
main()


import math
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def primefactorization(n):
	pf = []
	while n % 2 == 0:
		pf.append(2)
		n //= 2
	for i in range(3, int(math.sqrt(n)) + 1):
		while n % i == 0:
			pf.append(i)
			pf.append(n // i)
			n //= i
	if n > 2:
		pf.append(n)
	return list(set(pf))
n = int(input())
arr = [int(z) for z in input().split()]
rollingcd = arr[0]
primes = {}
if list(set(arr)) == [1]:
	print(1)
	exit()
for i in arr:
	pf = primefactorization(i)
	for j in pf:
		if not primes.get(j):
			primes[j] = 1
		else:
			primes[j] += 1
print(max(primes.values()))


primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313}
count = {p: 0 for p in primes}
n = int(input())
for x in map(int, input().split()):
	for p in primes:
		if not x % p:
			count[p] += 1
			while not x % p:
				x //= p
	if x > 1 and x not in primes:
		count[x] = count.get(x, 0) + 1
print(max(1, max(count.values())))


n = int(input())
arr = list(map(int, input().split()))
N = int(100000.0 + 3)
(res, s) = (1, [0] * N)
for i in arr:
	s[i] += 1
for i in range(2, N):
	p = 0
	for j in range(i, N, i):
		p += s[j]
	res = max(res, p)
print(res)


from collections import Counter
newn = int(input())
unfs = list(map(int, input().split()))
s = []
n = 0
p = [2, 3]
for i in range(1, 55):
	p.append(6 * i - 1)
	p.append(6 * i + 1)
if newn == 1 and unfs[0] == 1:
	print(1)
else:
	for i in unfs:
		if i != 1:
			s.append(i)
			n += 1
	a = []
	for i in range(n):
		found = False
		for j in range(1, 1 + int(s[i] ** 0.5)):
			if s[i] % j == 0:
				if j != 1:
					a.append(j)
				if s[i] // j != 1 and s[i] // j != j:
					a.append(s[i] // j)
	c = Counter(a).most_common()
	if len(c) == 0:
		print(1)
	else:
		print(c[0][1])


n = int(input())
ip = list(map(int, input().split()))
m = max(ip)
ans = 0
x = [0] * (m + 1)
p = []
p.append(1)
for i in ip:
	x[i] += 1
for k in range(2, m + 1, 1):
	l = k
	z = 0
	while l <= m:
		z += x[l]
		l += k
	if ans < z:
		p.append(z)
print(max(p))


from collections import Counter
(n, ss) = (int(input()), map(int, input().split()))
counts = Counter(ss)
limit = max(counts) + 1
for i in range(2, limit):
	for j in range(2 * i, limit, i):
		counts[i] += counts[j]
counts[1] = min(counts[1], 1)
print(counts.most_common(1)[0][1])


n = int(input().strip())
a = [int(i) for i in input().strip().split()]
f = [0 for i in range(max(a) + 1)]
l = len(f)
for i in a:
	f[i] += 1
if f[1]:
	f[1] = 1
for i in range(2, l):
	for j in range(2 * i, l, i):
		f[i] += f[j]
print(max(f))


n = int(input())
powers = list(map(int, input().split()))
counter_d = {}
for powe in powers:
	power = powe
	for i in range(2, int(power ** 0.5) + 20):
		if powe != i:
			if power % i == 0:
				try:
					counter_d[i] += 1
				except:
					counter_d[i] = 1
			while power % i == 0:
				power //= i
	if power > 1:
		try:
			counter_d[power] += 1
		except:
			counter_d[power] = 1
ans = 1
for a in counter_d:
	ans = max(ans, counter_d[a])
print(ans)


m = 10 ** 5 + 5
cri = [0] * m
for i in range(2, m):
	if cri[i] == 0:
		cri[i] = i
		for j in range(i * i, m, i):
			cri[j] = i
cri[1] = 1
n = int(input())
res = [0] * m
lista = [int(x) for x in input().split()]
for num in lista:
	a = num
	while cri[a] > 1:
		d = cri[a]
		res[d] += 1
		while a % d == 0:
			a //= d
resp = max(res)
if resp == 0:
	resp = 1
print(resp)


N = int(input())
lst2 = list(map(int, input().split()))
M = max(lst2)
N = M + 100
lst = [True for _ in range(N)]
lst[0] = False
lst[1] = False
i = 2
while i < N:
	if lst[i]:
		for j in range(2, 1 + (N - 1) // i):
			lst[i * j] = False
	i += 1
primes = [i for i in range(N) if lst[i]]
auxlst = [0] * (M + 1)
for i in lst2:
	auxlst[i] += 1
result = [0] * (M + 1)
for p in primes:
	if p > M:
		break
	n = p
	for _ in range(M // p):
		result[p] += auxlst[n]
		n += p
result = max(1, max(result))
print(result)


import math
factor = [0] * 100001

def factors(x):
	i = 0
	for i in range(2, int(math.sqrt(x)) + 1):
		if x % i == 0:
			factor[i] += 1
			if x // i != i:
				factor[x // i] += 1
	if x != 1 and i < x:
		factor[x] += 1
n = int(input())
s = list(map(int, input().split()))
for x in s:
	factors(x)
print(max(max(factor), 1))


def primes(n):
	primfac = set()
	d = 2
	while d * d <= n:
		while n % d == 0:
			primfac.add(d)
			n //= d
		d += 1
	if n > 1:
		primfac.add(n)
	return primfac
n = int(input())
a = list(map(int, input().split()))
c = {}
for i in a:
	for j in primes(i):
		c[j] = c.get(j, 0) + 1
if c:
	print(max(c.values()))
else:
	print(1)


import math
from collections import *
import sys
import operator as op
from functools import reduce
ii = lambda : list(map(int, sys.stdin.readline().strip().split()))
ist = lambda : list(sys.stdin.readline().strip().split())
arr = [k for k in range(100001)]
for k in range(2, 100001):
	if arr[k] == k:
		for j in range(k, 100001, k):
			arr[j] = k
(n,) = ii()
ar = ii()
if ar.count(1) == n:
	print(1)
else:
	d = defaultdict(lambda : 0)
	for k in ar:
		s = set()
		h = k
		while h != 1:
			s.add(arr[h])
			h = h // arr[h]
		for f in s:
			d[f] += 1
	ma = 0
	for j in d.values():
		ma = max(ma, j)
	print(ma)


def isPrime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
primes = set()
for i in range(2, 100000):
	if isPrime(i):
		primes.add(i)
c = [1] + [0] * 100000
n = input()
s = list(map(int, input().split()))
x = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313]
for i in s:
	for p in x:
		if i in primes:
			c[i] += 1
			break
		if p ** 2 > i:
			break
		if i % p == 0:
			c[p] += 1
			while i and i % p == 0:
				i //= p
m = max(c)
print(m)


import sys
input = sys.stdin.readline
from math import *
n = int(input())
a = [int(x) for x in input().split()]
d = [0 for i in range(10 ** 5 + 9)]
for i in range(n):
	for j in range(1, int(sqrt(a[i])) + 1):
		if a[i] % j == 0:
			if a[i] // j == j:
				d[j] += 1
			else:
				d[j] += 1
				d[a[i] // j] += 1
print(max(1, max(d[2:])))


mx = 10 ** 5 + 1
cnt = [0] * mx
n = int(input())
for c in map(int, input().split()):
	cnt[c] += 1
f = [0] * mx
ans = 1
for i in range(2, mx):
	if f[i] == 0:
		f[i] = 1
		for j in range(i + i, mx, i):
			f[j] = 1
			cnt[i] += cnt[j]
		ans = max(ans, cnt[i])
print(ans)


from math import *
n = int(input())
l = [int(j) for j in input().split()]
d = dict()
mx = 1
for i in range(n):
	t = l[i]
	k = 2
	p = []
	while k * k <= t:
		if t % k == 0:
			t //= k
			if not k in p:
				if k in d:
					d[k] += 1
				else:
					d[k] = 1
				p.append(k)
		elif k == 2:
			k = 3
		else:
			k += 2
	if t > 1 and (not t in p):
		if t in d:
			d[t] += 1
		else:
			d[t] = 1
for i in d:
	if i != 1:
		mx = max(d[i], mx)
print(mx)


n = int(input())
a = list(map(int, input().split()))
ans = 1
b = [0] * 100001
for x in a:
	b[x] += 1
for x in range(2, 100001):
	k_del = 0
	for j in range(x, 100001, x):
		k_del += b[j]
	ans = max(ans, k_del)
print(ans)


from math import *
from bisect import *
from collections import Counter, defaultdict
from sys import stdin, stdout
input = stdin.readline
I = lambda : int(input())
SI = lambda : input()
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
n = I()
a = LI()
d = defaultdict(int)

def num(n):
	i = 2
	global d
	while i * i <= n:
		if n % i == 0:
			d[i] += 1
			while n % i == 0:
				n //= i
		i += 1
	if n > 1:
		d[n] += 1
o = 0
for i in range(n):
	num(a[i])
	if a[i] == 1:
		o += 1
if len(d) == 0:
	print(1)
else:
	print(max(d.values()))


from math import sqrt, floor
n = int(input())
a = map(int, input().split())
ans = 1
c = [0] * 100100
for i in a:
	c[i] += 1
for i in range(2, 100100):
	ans = max(ans, sum(c[i::i]))
print(ans)


n = int(input())
s = [int(i) for i in input().split()]
ans = 1
p = [0] * 100002
for i in s:
	p[i] += 1
for i in range(2, 100002):
	c = 0
	for j in range(i, 100002, i):
		c += p[j]
	ans = max(ans, c)
print(ans)


from collections import Counter
(n, ss) = (int(input()), map(int, input().split()))
counts = Counter(ss)
sieve = [counts[i] for i in range(max(counts) + 1)]
for i in range(2, len(sieve)):
	for j in range(2 * i, len(sieve), i):
		sieve[i] += sieve[j]
sieve[1] = min(sieve[1], 1)
print(max(sieve))


from sys import stdin, stdout
from math import gcd, sqrt, ceil
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007

def primeFactors(n):
	d = set()
	while n % 2 == 0:
		d.add(2)
		n = n // 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			d.add(i)
			n = n // i
	if n > 2:
		d.add(n)
	return d
n = iia()
arr = sorted(iia())
d = {}
for i in arr:
	cur = primeFactors(i)
	for i in cur:
		d.setdefault(i, [0])[0] += 1
res = 1
for i in d:
	res = max(res, d[i][0])
print(res)


import math
n = int(input())
arr = [int(x) for x in input().split(' ')]
a = [0] * 100005
for i in arr:
	if i != 1:
		a[i] += 1
	for j in range(2, int(math.floor(math.sqrt(i)) + 1)):
		if i % j == 0:
			a[j] += 1
			if j * j != i:
				a[int(i / j)] += 1
k = max(a)
if k == 0:
	print(1)
else:
	print(k)


import math

def seive(a):
	l = [0] * a
	for i in range(a):
		l[i] = i
	for i in range(2, a, 2):
		l[i] = 2
	for i in range(3, int(math.sqrt(a)) + 1):
		if l[i] == i:
			for j in range(i * i, a, i):
				if l[j] == j:
					l[j] = i
	return l

def cal(a, d, p):
	s = set()
	while a != 1:
		if p[a] not in s:
			s.add(p[a])
			d[p[a]] = d[p[a]] + 1
		a = a // p[a]
n = int(input())
arr = [int(i) for i in input().split()]
d = dict()
for i in range(2, 10 ** 5 + 1):
	d[i] = 0
p = seive(10 ** 5 + 1)
for i in range(n):
	cal(arr[i], d, p)
maxi = 1
for i in range(2, 10 ** 5 + 1):
	if maxi < d[i]:
		maxi = d[i]
print(maxi)


from sys import stdin, stdout
from math import sqrt

class Solve:

	def sieve(self, prime, cnt):
		prime.append(2)
		cnt[2] = 0
		check = [1 for i in range(317)]
		for i in range(3, 317, 2):
			if check[i]:
				cnt[i] = 0
				prime.append(i)
				for j in range(i + 2 * i, 317, 2 * i):
					check[j] = 0
		return 0

	def __init__(self):
		R = stdin.readline
		W = stdout.write
		(prime, cnt) = ([], {})
		self.sieve(prime, cnt)
		l = len(prime)
		n = int(input())
		a = [int(x) for x in R().split()]
		mx = 1
		for i in range(n):
			for j in range(l):
				if a[i] % prime[j] == 0:
					cnt[prime[j]] += 1
					mx = max(mx, cnt[prime[j]])
					while a[i] % prime[j] == 0:
						a[i] //= prime[j]
			if a[i] > 1:
				if a[i] not in cnt:
					cnt[a[i]] = 1
				else:
					cnt[a[i]] += 1
					mx = max(mx, cnt[a[i]])
		W('%d\n' % mx)

def main():
	s = Solve()
main()


import math
N = int(input())
S = [int(s) for s in input().split()]
factors = {}
for s in S:
	root_s = math.sqrt(s)
	for i in range(2, math.ceil(root_s) + 1, 1):
		if s % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			while s % i == 0:
				s //= i
	if s > 1 and s in factors:
		factors[s] += 1
	elif s > 1 and s not in factors:
		factors[s] = 1
if len(factors.values()) == 0:
	ans = 1
else:
	ans = max(factors.values())
print(ans)


from collections import defaultdict

def main():
	n = int(input())
	s = list(map(int, input().split()))
	pokemons = defaultdict(int)
	for i in s:
		pokemons[i] += 1
	if len(pokemons.keys()) == 1 and list(set(pokemons.keys()))[0] == 1:
		print(1)
		return
	answer = defaultdict(int)
	for (s, count) in pokemons.items():
		max_n = s
		if s > 100:
			max_n = int(s ** 0.5) + 1
			answer[s] += 1 * count
		for j in range(2, max_n + 1):
			if s % j == 0:
				answer[j] += 1 * count
				quotient = s / j
				if quotient > max_n:
					answer[quotient] += 1 * count
	print(max(answer.values()))
main()


n = int(input())
entree = list(map(int, input().split()))
compter = 1
t = [0 for i in range(10 ** 5 + 1)]
for i in entree:
	t[i] += 1
for i in range(2, 10 ** 5 + 1):
	compteur = 0
	for j in range(i, 10 ** 5 + 1, i):
		compteur = compteur + t[j]
	compter = max(compter, compteur)
print(compter)


(res, N) = (1, int(100000.0 + 16))
n = int(input())
M = {}
for i in map(int, input().split()):
	M[i] = M.get(i, 0) + 1
for i in range(2, N):
	num = 0
	for k in range(i, N, i):
		num += M.get(k, 0)
	res = max(res, num)
print(res)


n = int(input())
a = list(map(int, input().split(' ')))
t = max(a)
k = [0] * (t + 2)
for el in a:
	k[el] += 1
if k[1]:
	k[1] = 1
for j in range(2, t + 2):
	for i in range(2 * j, t + 2, j):
		k[j] += k[i]
print(max(k))


def solve(A):
	N = max(A)
	primediv = list(range(N + 1))
	for p in range(2, int(N ** 0.5) + 1):
		if primediv[p] == p:
			for i in range(2 * p, N + 1, p):
				primediv[i] = p
	count = [0] * (N + 1)
	for n in A:
		while n != 1:
			p = primediv[n]
			count[p] += 1
			while primediv[n] == p:
				n //= p
	return max(1, max(count))
n = int(input())
A = [int(x) for x in input().split()]
print(solve(A))


a = int(input())
ara = list(map(int, input().split()))
list = [0] * 100001
count = 1
for i in ara:
	list[i] += 1
for i in range(2, 100001):
	po = 0
	for j in range(0, 100001, i):
		if not list[j] == 0:
			po += list[j]
	count = max(count, po)
print(count)


import sys
import math
import itertools
import functools
import collections
import operator
import fileinput
import copy
ORDA = 97

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return [int(i) for i in input().split()]

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=2):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	new_number = 0
	while number > 0:
		new_number += number % base
		number //= base
	return new_number

def cdiv(n, k):
	return n // k + (n % k != 0)

def ispal(s):
	for i in range(len(s) // 2 + 1):
		if s[i] != s[-i - 1]:
			return False
	return True
rr = sieve(100001)
dd = collections.defaultdict(int)
dd[1] = 1

def main():
	n = ii()
	arr = li()
	f = [0] * 100001
	for a in arr:
		f[a] += 1
	if f[1]:
		f[1] = 1
	a = max(arr)
	for i in range(2, a + 1):
		for j in range(2 * i, a + 1, i):
			f[i] += f[j]
	print(max(f))
main()


import itertools
import bisect
import math
from collections import *
import os
import sys
from io import BytesIO, IOBase
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def main():
	n = ii()
	a = lmii()
	d = defaultdict(int)
	a.sort()
	if len(set(a)) == 1:
		if a[0] == 1:
			print(1)
		else:
			print(n)
	else:
		for i in range(n):
			if a[i] % 2 == 0:
				d[2] += 1
			while a[i] % 2 == 0:
				a[i] //= 2
			for k in range(3, int(math.sqrt(a[i])) + 1, 2):
				if a[i] % k == 0:
					f = 1
					d[k] += 1
				while a[i] % k == 0:
					a[i] //= k
			if a[i] > 2:
				d[a[i]] += 1
		print(max(d.values()))
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
import math

def prime_factors(n):
	l = set()
	while n % 2 == 0:
		l.add(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.add(i)
			n = n / i
	if n > 2:
		l.add(int(n))
	return l
n = int(stdin.readline().rstrip())
l = list(map(int, stdin.readline().rstrip().split(' ')))
d = {}
for i in range(n):
	if l[i] == 1:
		if not d.get(1, 0):
			d[1] = 0
		d[1] = 1
	else:
		a = list(prime_factors(l[i]))
		for i in a:
			if not d.get(i, 0):
				d[i] = 0
			d[i] += 1
print(max(d.values()))


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for i in range(n):
	k = a[i]
	j = 2
	while j * j <= a[i]:
		if k % j == 0:
			d[j] += 1
			while k % j == 0:
				k //= j
		j += 1
	if k > 1:
		d[k] += 1
if len(d) == 0:
	print(1)
else:
	print(max(d.values()))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
n = int(data())
arr = l()
dp = dd(int)
for i in range(n):
	if 1 < arr[i] <= 3:
		dp[arr[i]] += 1
		continue
	j = 2
	while j * j <= arr[i]:
		if arr[i] % j == 0:
			dp[j] += 1
		while arr[i] % j == 0:
			arr[i] //= j
		j += 1
	if arr[i] > 1:
		dp[arr[i]] += 1
answer = 1
for i in dp.values():
	answer = max(answer, i)
out(answer)


(n, list) = (int(input()), list(map(int, input().split())))
max = max(list)
seive = [0] * (max + 3)
count = 1
for i in list:
	seive[i] += 1
for i in range(2, max + 3):
	rslt = 0
	for j in range(0, max + 3, i):
		if seive[j] != 0:
			rslt += seive[j]
	if rslt > count:
		count = rslt
print(count)


n = input()
s = list(map(int, input().split()))
mxx = max(s)
res = 1
mpp = [0] * 100005
for i in s:
	mpp[i] += 1
for i in range(2, mxx + 1):
	sm = 0
	for j in range(i, 100001, i):
		sm += mpp[j]
		res = max(res, sm)
print(res)


bignum = 123456
n = int(input())
strengths = [int(a) for a in input().split(' ')]
cnt = [0] * bignum
for strength in strengths:
	cnt[strength] += 1
ans = 1
for gcd in range(2, bignum):
	curr = 0
	for val in range(gcd, bignum, gcd):
		curr += cnt[val]
	ans = max(ans, curr)
print(ans)


input()
s = list(map(int, input().split()))
MAX = max(s)
l = [0] * (MAX + 1)
for i in s:
	l[i] += 1
res = 1
for i in range(2, MAX + 1):
	m = 0
	for j in range(i, MAX + 1, i):
		m += l[j]
	res = max(res, m)
print(res)


n = int(input())
a = map(int, input().split())
ans = 1
c = [0] * 100100
for i in a:
	c[i] += 1
for i in range(2, 100100):
	ans = max(ans, sum(c[i::i]))
print(ans)


import collections
import math
cnt = collections.Counter()
n = int(input())
a = [int(x) for x in input().split()]
for x in a:
	for i in range(1, int(math.sqrt(x)) + 1):
		if x % i == 0:
			cnt[i] += 1
			if x // i != i:
				cnt[x // i] += 1
maxi = 1
for x in cnt:
	if x != 1:
		maxi = max(maxi, cnt[x])
print(maxi)


from collections import Counter

def f(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n //= 2
	for x in range(3, int(n ** 0.5) + 1, 2):
		while n % x == 0:
			l.append(x)
			n //= x
	if n != 1:
		l.append(n)
	return set(l)
n = int(input())
s = list(map(int, input().split()))
if set(s) == {1}:
	print(1)
	quit()
(m, a) = (0, [])
for x in s:
	a += f(x)
print(Counter(a).most_common(1)[0][1])


from collections import defaultdict

def factorize(n):
	res = set()
	d = 2
	while d * d <= n:
		while n % d == 0:
			n //= d
			res.add(d)
		d += 1
	if n > 1:
		res.add(n)
	return res
n = int(input())
a = list(map(int, input().split()))
factors = [1]
for v in a:
	factors.extend(factorize(v))
cnt = defaultdict(int)
for v in factors:
	cnt[v] += 1
print(max(cnt.values()))


n = int(input())
arr = list(map(int, input().split()))
if n == 1:
	print(1)
	exit()
freq = [0] * (10 ** 5 + 1)
for i in arr:
	freq[i] += 1
ans = 1
for i in range(2, 10 ** 5 + 1):
	j = i
	cnt = 0
	for k in range(j, 10 ** 5 + 1, j):
		cnt += freq[k]
	ans = max(cnt, ans)
print(ans)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
l = il()
lcnt = [0] * (10 ** 5 + 15)
for i in l:
	lcnt[i] += 1
lnum = [0] * (10 ** 5 + 10)
for i in range(2, 10 ** 5 + 10 + 1):
	for j in range(i, 10 ** 5 + 10, i):
		lnum[i] += lcnt[j]
lnum[1] = 1
print(max(lnum))


input()
count = {}
for x in map(int, input().split()):
	d = 2
	while d * d <= x:
		if x % d == 0:
			count[d] = count.get(d, 0) + 1
			while x % d == 0:
				x //= d
		else:
			d += 1
	if x > 1:
		count[x] = count.get(x, 0) + 1
print(max([1] + list(count.values())))


from collections import defaultdict
from math import sqrt

def solve():
	n = int(input())
	numbers = list(map(int, input().split(' ')))
	if n == 1:
		print(1)
		return
	amount = {}
	for number in numbers:
		if number not in amount:
			amount[number] = 1
		else:
			amount[number] += 1
	freq = defaultdict(int)
	for (key, value) in sorted(amount.items()):
		if key == 1:
			freq[key] += value
			continue
		freq[key] += value
		for j in range(2, int(sqrt(key)) + 1):
			if key % j == 0:
				freq[j] += value
				if key // j != j:
					freq[key // j] += value
	highest = sorted(freq.items(), key=lambda x: x[1])[-1]
	if highest[0] == 1:
		print(1)
	else:
		print(highest[1])
solve()


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def main():
	n = int(input())
	raw = input()
	pk = [int(x) for x in raw.split()]
	ans = get_ans(pk)
	print(ans)

def get_ans(arr):
	t = max(arr)
	factors = [0] * (t + 2)
	for i in arr:
		factors[i] += 1
	ans = 1
	for i in range(2, t + 2):
		count = 0
		for k in range(i, t + 2, i):
			count += factors[k]
		if count > ans:
			ans = count
	return ans
main()


import sys
from math import gcd
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def sieve():
	for i in range(2 * 2, 10 ** 5 + 1, 2):
		prime[i] = False
		sp[i] = 2
	p = 3
	while p * p <= 10 ** 5 + 1:
		if prime[p]:
			for j in range(p * p, 10 ** 5 + 1, p):
				if prime[j]:
					prime[j] = False
					sp[j] = p
		p += 2
n = int(ri())
a = Ri()
prime = [True] * (10 ** 5 + 1)
sp = [i for i in range(0, 10 ** 5 + 2)]
sieve()
dic = {}
for i in a:
	while i > 1:
		p = sp[i]
		while i % p == 0:
			i = i // p
		if p in dic:
			dic[p] += 1
		else:
			dic[p] = 1
		p = sp[i]
maxx = 1
for i in dic:
	if i != 1:
		maxx = max(maxx, dic[i])
else:
	print(maxx)


n = int(input())
ln = sorted([int(i) for i in input().split(' ')])
dct = [0] * (10 ** 5 + 2)
for i in ln:
	if i > 1:
		dct[i] += 1
	for j in range(2, int(i ** 0.5) + 1):
		if i % j == 0:
			if j == i // j:
				dct[j] += 1
			else:
				dct[j] += 1
				dct[i // j] += 1
print(max(max(dct), 1))


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
factors = defaultdict(int)
for i in range(n):
	root = int(a[i] ** 0.5)
	for j in range(2, root + 1):
		if a[i] % j == 0:
			factors[j] += 1
		while a[i] % j == 0:
			a[i] //= j
	if a[i] > 1:
		factors[a[i]] += 1
ans = 1
for i in factors:
	ans = max(ans, factors[i])
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
answer = 1
s = [0] * 100001
for i in a:
	s[i] += 1
for i in range(2, 100001):
	num = 0
	for j in range(i, 100001, i):
		num += s[j]
	answer = max(answer, num)
print(answer)


the_len = int(input())
s2 = input()
import math
nums = s2.split(' ')
groups = [0] * 100001
max = 1
for n in nums:
	groups[int(n)] += 1
for i in range(2, 100001):
	res = 0
	for j in range(i, 100001, i):
		res += groups[j]
	if res > max:
		max = res
print(max)


def primefactor(n):
	l = []
	x = n
	if n % 2 == 0:
		l.append(2)
	while n % 2 == 0:
		n = n // 2
	for i in range(3, int(x ** 0.5 + 1), 2):
		if n % i == 0:
			l.append(i)
		while n % i == 0:
			n = n // i
	if n != 1:
		l.append(n)
	return l
from collections import defaultdict
n = int(input())
s = list(map(int, input().split()))
d = defaultdict(int)
d[1] = 1
for i in range(n):
	if s[i] != 1:
		l = primefactor(s[i])
		for j in range(len(l)):
			d[l[j]] += 1
print(max(1, max(d.values())))