AtCoder Beginner Contest 170 - Not Divisible

Given is a number sequence A of length N.
Find the number of integers i \left(1 \leq i \leq N\right) with the following property:
 - For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^6

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N

-----Output-----
Print the answer.

-----Sample Input-----
5
24 11 8 3 16

-----Sample Output-----
3

The integers with the property are 2, 3, and 4.

Difficulty: MEDIUM

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
a.sort()
d = {}
for x in a:
	d[x] = d.get(x, 0) + 1
ans = 0
ok = [1] * (10 ** 6 + 1)
for x in list(d.keys()):
	if ok[x]:
		for j in range(2, 10 ** 6 // x + 1):
			ok[j * x] = 0
		if d[x] == 1:
			ans += 1
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())))
B = (10 ** 6 + 1) * [0]
for a in A:
	B[a] += 1
	if B[a] == 1:
		for n in range(2 * a, 10 ** 6 + 1, a):
			B[n] += 2
print(B.count(1))


n = int(input())
a = list(map(int, input().split()))
a.sort()
from collections import Counter
c = Counter(a)
f = [1] * (10 ** 6 + 1)
ans = 0
for ai in a:
	if c[ai] == 1 and f[ai] == 1:
		ans += 1
	if f[ai] == 1:
		for i in range(ai, 10 ** 6 + 1, ai):
			f[i] = 0
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
m_a = max(A)
check = [0] * (m_a + 2)
for i in A:
	check[i] += 1
	if check[i] == 1:
		for j in range(i * 2, m_a + 1, i):
			check[j] += 100
print(check.count(1))


n = int(input())
a = sorted(list(map(int, input().split())))
x = max(a)
dp = [0] * (x + 1)
for ai in a:
	i = 1
	while i * ai <= x:
		dp[i * ai] += 1
		i += 1
ans = 0
for ai in a:
	if dp[ai] <= 1:
		ans += 1
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
dp = [0] * (m := (a[-1] + 1))
for i in a:
	dp[i] += 1
for i in a:
	for j in range(i * 2, m, i):
		dp[j] += 1
ans = 0
for i in a:
	if dp[i] == 1:
		ans += 1
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
a_max = a[-1]
dp = [0] * (a_max + 1)
for i in a:
	dp[i] += 1
	if dp[i] == 1:
		for j in range(i * 2, a_max + 1, i):
			dp[j] = 2
print(dp.count(1))


n = int(input())
a = list(map(int, input().split()))
M = 10 ** 6 + 1
t = [0] * M
for i in sorted(a):
	t[i] += 1
	if t[i] == 1:
		for j in range(2 * i, M, i):
			t[j] += 10
print(t.count(1))


n = int(input())
A = list(map(int, input().split()))
A.sort()
mx = A[n - 1]
dp = [0] * (mx + 1)
for a in A:
	for j in range(a, mx + 1, a):
		dp[j] += 1
sum = 0
for i in A:
	if dp[i] == 1:
		sum += 1
print(sum)


N = input()
A = sorted(map(int, input().split()))
M = A[-1] + 1
B = [0] * M
for i in A:
	B[i] += 1
	if B[i] == 1:
		for j in range(i * 2, M, i):
			B[j] = 2
print(B.count(1))


N = int(input())
A = sorted(list(map(int, input().split())))
B = [0] * (A[-1] + 1)
for i in A:
	j = i
	while j <= A[-1]:
		B[j] += 1
		j += i
s = 0
for i in A:
	if B[i] == 1:
		s += 1
print(s)


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint

def ceil(a, b):
	return (a + b - 1) // b
inf = float('inf')
mod = 10 ** 9 + 7

def pprint(*A):
	for a in A:
		print(*a, sep='\n')

def INT_(n):
	return int(n) - 1

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

def MF():
	return map(float, input().split())

def MI_():
	return map(INT_, input().split())

def LI():
	return list(MI())

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return list(MF())

def LIN(n: int):
	return [I() for _ in range(n)]

def LLIN(n: int):
	return [LI() for _ in range(n)]

def LLIN_(n: int):
	return [LI_() for _ in range(n)]

def LLI():
	return [list(map(int, l.split())) for l in input()]

def I():
	return int(input())

def F():
	return float(input())

def ST():
	return input().replace('\n', '')

def main():
	N = I()
	A = sorted(LI())
	MAX = 10 ** 6
	divible = [False] * (MAX + 1)
	ans = 0
	for (i, a) in enumerate(A):
		if i + 1 < N and A[i + 1] == a or divible[a]:
			pass
		else:
			ans += 1
		b = a
		if not divible[a]:
			while b <= MAX:
				divible[b] = True
				b += a
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
from collections import Counter as co
l = co(list(map(int, input().split())))
ans = len(l)
ng = set()
for k in l:
	if l[k] >= 2:
		ng.add(k)
	for i in range(2 * k, 10 ** 6 + 1, k):
		if i in l:
			ng.add(i)
print(ans - len(ng))


def resolve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	M = int(1000000.0 + 1)
	f = [0] * M
	for x in a:
		if f[x] != 0:
			f[x] += 1
			continue
		for nx in range(x, M, x):
			f[nx] += 1
	ans = 0
	for x in a:
		if f[x] == 1:
			ans += 1
	print(ans)
resolve()


N = int(input())
A = list(map(int, input().split()))
A.sort()
M = 10 ** 6 + 5
cnt = [0] * M
for x in A:
	if cnt[x] != 0:
		cnt[x] = 2
		continue
	for i in range(x, M, x):
		cnt[i] += 1
ans = 0
for i in A:
	if cnt[i] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
b = sorted(list(A))
dp = [0] * (max(A) + 1)
m_a = max(A) + 1
for i in b:
	dp[i] += 1
	if dp[i] == 1:
		for j in range(i * 2, m_a, i):
			dp[j] += 100
print(dp.count(1))


n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * (a[-1] + 1)
for i in a:
	for j in range(i, a[-1] + 1, i):
		dp[j] += 1
ans = 0
for i in a:
	if dp[i] == 1:
		ans += 1
print(ans)


a = [0] * 1000001
m = 0
input()
for x in map(int, input().split()):
	m = max(m, x)
	a[x] += 1
m += 1
for i in range(1, m):
	if a[i]:
		for j in range(i + i, m, i):
			a[j] = 0
print(a.count(1))


def main():
	N = int(input())
	D = [0] * (10 ** 6 + 1)
	A = sorted(map(int, input().split()))
	m = max(A) + 1
	for a in A:
		if D[a] == 0:
			D[a] = 1
			for i in range(2 * a, m, a):
				D[i] = -1
		else:
			D[a] = -1
	print(D.count(1))
main()


(n, *a) = map(int, open(0).read().split())
m = max(a) + 10
li = [0] * m
for x in a:
	li[x] += 1
ans = 0
for i in range(1, m):
	if li[i]:
		if li[i] == 1:
			ans += 1
		for j in range(i, m, i):
			li[j] = 0
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
multiple = [0] * (A[-1] + 1)
for i in range(n):
	now = A[i]
	while now <= A[-1]:
		multiple[now] += 1
		now += A[i]
ans = 0
for i in range(n):
	if multiple[A[i]] == 1:
		ans += 1
print(ans)


(N, *A) = map(int, open(0).read().split())
A.sort()
lim = A[-1] + 1
dp = [0] * lim
for a in A:
	dp[a] += 1
	if dp[a] == 1:
		for j in range(2 * a, lim, a):
			dp[j] += 2
print(dp.count(1))


N = 1000001
a = [0] * N
input()
for x in input().split():
	a[int(x)] += 1
for i in range(1, N):
	if a[i]:
		for j in range(i + i, N, i):
			a[j] = 0
print(a.count(1))


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ma = a[-1]
dup = [0 for _ in range(ma + 1)]
div = [0 for _ in range(ma + 1)]
for i in range(n):
	dup[a[i]] += 1
for i in range(n):
	for j in range(a[i], ma + 1, a[i]):
		div[j] += 1
ans = 0
for i in range(n):
	if div[a[i]] == 1:
		ans += 1
print(ans)


import collections
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
s = set()
cnt = collections.Counter(arr)
for i in range(n):
	if arr[i] in s:
		continue
	if cnt[arr[i]] >= 2:
		s.add(arr[i])
	for j in range(2, 10 ** 6 // arr[i] + 1):
		s.add(arr[i] * j)
ans = 0
for i in range(n):
	if arr[i] in s:
		continue
	ans += 1
print(ans)


import numpy as np
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
b = np.array([0] * (max(A) + 1))
A.sort()
ans = 0
for a in A:
	if cnt[a] == 1 and (not b[a]):
		ans += 1
	b[a::a] = 1
print(ans)


def main():
	from collections import Counter
	import sys
	pin = sys.stdin.readline
	pout = sys.stdout.write
	perr = sys.stderr.write
	ans = 0
	N = int(pin())
	A = list(map(int, pin().split()))
	c = Counter(A)
	t = max(A)
	dp = [True] * t
	for i in A:
		if dp[i - 1]:
			n = 2 * i
			while n <= t:
				dp[n - 1] = False
				n += i
	for k in A:
		if c[k] == 1 and dp[k - 1]:
			ans += 1
	print(ans)
	return
main()


N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0] * (maxA + 1)
for ai in A:
	for m in range(ai, maxA + 1, ai):
		counter[m] += 1
ans = 0
for ai in A:
	ans += counter[ai] == 1
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, bisect
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
stdin = sys.stdin
ni = lambda : int(ns())
nf = lambda : float(ns())
na = lambda : list(map(int, stdin.readline().split()))
nb = lambda : list(map(float, stdin.readline().split()))
ns = lambda : stdin.readline().rstrip()

def make_divisors(n):
	(lower_divisors, upper_divisors) = ([], [])
	i = 1
	while i * i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n // i)
		i += 1
	return lower_divisors + upper_divisors[::-1]
N = ni()
A = na()
d = collections.Counter(A)
dp = [0] * (10 ** 6 + 10)
A.sort()
pre = -1
ans = 0
for ai in A:
	if pre == ai:
		continue
	pre = ai
	if dp[ai] == 0 and d[ai] == 1:
		ans += 1
	for j in range(ai, 10 ** 6 + 1, ai):
		dp[j] = 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)
for ai in a:
	for i in range(ai, m + 1, ai):
		c[i] += 1
ans = 0
for ai in a:
	if c[ai] == 1:
		ans += c[ai]
print(ans)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
s = set(a)
c = Counter(a)
t = [0] * (10 ** 6 + 1)
for i in s:
	for j in range(i, 10 ** 6 + 1, i):
		t[j] += 1
ans = len([1 for i in s if t[i] == 1 and c[i] == 1])
print(ans)


N = int(input())
A = list(map(int, input().split()))
l = max(A) + 1
li = [0] * l
A.sort()
for a in A:
	if li[a] == 0:
		li[a] = 1
		for i in range(a * 2, l, a):
			li[i] = 2
	elif li[a] == 1:
		li[a] = 2
print(li.count(1))


n = int(input())
A = list(map(int, input().split()))
dp = [0] * (10 ** 6 + 1)
for i in A:
	dp[i] += 1
for i in range(1, 10 ** 6 + 1):
	if dp[i] > 0:
		for j in range(2 * i, 10 ** 6 + 1, i):
			dp[j] = 0
print(dp.count(1))


M = 10 ** 6 + 1
(_, *l) = map(int, open(0).read().split())
a = [0] * M
for i in sorted(l):
	a[i] += 1
	if a[i] == 1:
		for j in range(2 * i, M, i):
			a[j] += 9
print(a.count(1))


n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
for x in a:
	if dp[x - 1] == 0:
		y = 2 * x
		while y <= a[-1]:
			dp[y - 1] = 1
			y += x
sum = 0
d = [0] * a[-1]
for i in a:
	if dp[i - 1] == 0:
		d[i - 1] += 1
for i in a:
	if d[i - 1] == 1:
		sum += 1
print(sum)


n = int(input())
l = list(map(int, input().split()))
counter = [0] * (10 ** 6 + 1)
l = sorted(l)
for i in l:
	counter[i] += 1
	if counter[i] < 2:
		for j in range(2 * i, 10 ** 6 + 1, i):
			counter[j] += 2
print(counter.count(1))


sieve = [0] * 1000009
n = int(input())
s = sorted(map(int, input().split()))
for i in s:
	if sieve[i] < 2:
		for j in range(i, 1000009, i):
			sieve[j] += 1
print(sum((sieve[i] == 1 for i in s)))


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
from collections import Counter

def main():
	(n, *a) = list(map(int, read().split()))
	if 1 in a:
		count1 = a.count(1)
		if count1 == 1:
			print(1)
			return
		else:
			print(0)
			return
	a = np.array(a)
	maxa = a.max()
	seq = np.zeros(maxa + 1, np.int32)
	(u, cnt) = np.unique(a, return_counts=True)
	for (ue, cnte) in zip(u, cnt):
		if cnte == 1:
			seq[ue] = 1
	for ae in a:
		t = ae * 2
		while t <= maxa:
			seq[t] = 0
			t += ae
	r = seq.sum()
	print(r)

def __starting_point():
	main()
__starting_point()


import sys
import math

def input():
	return sys.stdin.readline().rstrip()
from decimal import Decimal
M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))
count = [0] * M
for a in A:
	if count[a] != 0:
		count[a] = 2
		continue
	for i in range(1, M):
		if i * a >= M:
			break
		count[a * i] += 1
ans = 0
for a in A:
	if count[a] == 1:
		ans += 1
print(ans)


N = int(input())
A = [int(_) for _ in input().split()]
A.sort()
M = max(A)
X = [True for _ in range(M + 1)]
for a in set(A):
	if not X[a]:
		continue
	for v in range(2 * a, M + 1, a):
		X[v] = False
for i in range(N - 1):
	if A[i] == A[i + 1]:
		X[A[i]] = False
ans = 0
for a in A:
	if X[a]:
		ans += 1
print(ans)


N = 1000001
a = [0] * N
(_, s) = open(0)
for x in s.split():
	a[int(x)] += 1
for i in range(1, N):
	if a[i]:
		for j in range(i + i, N, i):
			a[j] = 0
print(a.count(1))


n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
b = {}
c = 0
for i in range(n):
	if a[i] not in b:
		for j in range(1, 10 ** 6 // a[i] + 1):
			b[a[i] * j] = 1
		if a[i] != a[i + 1]:
			c += 1
print(c)


n = int(input())
A = list(map(int, input().split()))
A.sort()
l = [0] * (10 ** 6 + 1)
for i in A:
	if l[i] <= 1:
		for j in range(0, 10 ** 6 + 1, i):
			l[j] += 1
count = 0
for i in A:
	if l[i] == 1:
		count += 1
print(count)


n = int(input())
A = sorted(list(map(int, input().split())))
B = [0] * (A[-1] + 1)
for i in A:
	B[i] += 1
	if B[i] >= 2:
		continue
	for j in range(2 * i, A[-1] + 1, i):
		B[j] += 1
ans = 0
for i in A:
	if B[i] == 1:
		ans = ans + 1
print(ans)


N = int(input())
A = sorted(list(map(int, input().split())))
Amax = max(A)
ans = [False] * (Amax + 1)
for x in A:
	for j in range(x, Amax + 1, x):
		ans[j] += 1
print(sum((ans[i] == 1 for i in A)))


n = int(input())
b = list(map(int, input().split()))
ans = 0
w = max(b)
a = [0] * (w + 1)
for i in b:
	x = i
	while x <= w:
		a[x] += 1
		x += i
for i in b:
	if a[i] == 1:
		ans += 1
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
MA = max(a) + 1
ans = [0] * MA
for i in range(n):
	for j in range(a[i], MA, a[i]):
		ans[j] += 1
print(sum((ans[i] == 1 for i in a)))


N = int(input())
A = list(map(int, input().split()))
dp = [0] * (10 ** 6 + 1)
ans = 0
for i in A:
	if dp[i] == 0:
		for j in range(i, 10 ** 6 + 1, i):
			dp[j] += 1
	else:
		dp[i] += 1
for i in A:
	if dp[i] == 1:
		ans += 1
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)
for ai in a:
	for multi in range(ai, max_a + 1, ai):
		cnt_d[multi] += 1
print(sum((cnt_d[ai] == 1 for ai in a)))


N = int(input())
arr = sorted(list(map(int, input().split())))
count_arr = [0] * arr[-1]
ans = 0
for i in arr:
	for j in range(1, arr[-1] // i + 1):
		count_arr[i * j - 1] += 1
for i in arr:
	if count_arr[i - 1] == 1:
		ans += 1
print(ans)


import sys
import collections
input = sys.stdin.readline

def ST():
	return input().rstrip()

def I():
	return int(input())

def MI():
	return list(map(int, input().split()))

def LI():
	return list(MI())
N = I()
A = LI()
A.sort()
cnt = collections.Counter(A)
end = A[-1] + 1
for a in A:
	if cnt[a] >= 2:
		del cnt[a]
	for i in range(a * 2, end, a):
		del cnt[i]
print(sum(cnt.values()))


from collections import Counter as c
n = int(input())
a = list(map(int, input().split()))
a.sort()
(count, a_max) = (0, a[-1])
li = [True] * (a_max + 1)
for i in a:
	if li[i] == 'x':
		count -= 1
		li[i] = 'y'
	if li[i] == True:
		count += 1
		li[i] = 'x'
	j = 2
	while i * j <= a_max:
		li[i * j] = False
		j += 1
print(count)


N = int(input())
A = list(map(int, input().split()))
LN = max(A) + 1
L = [0 for i in range(LN)]
count = 0
for i in A:
	for j in range(i, LN, i):
		L[j] += 1
for i in A:
	if L[i] == 1:
		count += 1
print(count)


import sys
input = sys.stdin.readline

def cal(n, li):
	lis = [True] * (n + 1)
	for item in li:
		if lis[item]:
			for i in range(item * 2, n + 1, item):
				lis[i] = False
	return lis
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
l = cal(a[-1], a)
ll = Counter(a)
ans = 0
for i in range(n):
	if ll[a[i]] == 1:
		if l[a[i]]:
			ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
b = list(set(a))
m = len(b)
p = [0] * (10 ** 6 + 1)
for i in b:
	if p[i] == 0:
		j = 2
		while i * j <= 10 ** 6:
			p[i * j] = 1
			j += 1
a.append(-1)
a.insert(0, -1)
ans = 0
for i in range(1, n + 1):
	if a[i] != a[i + 1] and a[i] != a[i - 1] and (p[a[i]] == 0):
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6 + 1
cnt = [0] * M
for a in A:
	if cnt[a] != 0:
		cnt[a] += 1
		continue
	for b in range(a, M, a):
		cnt[b] += 1
ans = 0
for a in A:
	if cnt[a] == 1:
		ans += 1
print(ans)


n = int(input())
a = sorted(map(int, input().split()))
cnt = [0] * (a[-1] + 1)
for i in a:
	cnt[i] += 1
for i in set(a):
	if cnt[i] >= 1:
		for j in range(i * 2, a[-1] + 1, i):
			cnt[j] = 0
print(cnt.count(1))


M = 10 ** 6 + 10
c = [0] * M
n = int(input())
a = sorted(list(map(int, input().split())))
for k in a:
	if c[k]:
		c[k] = 2
		continue
	for i in range(k, M, k):
		c[i] += 1
ans = 0
for i in a:
	if c[i] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
key = max(A) + 1
B = [0] * key
for a in A:
	for b in range(a, key, a):
		B[b] += 1
ans = 0
for a in A:
	if B[a] == 1:
		ans += 1
print(ans)


n = int(input())
nums = list(sorted(map(int, input().split())))
dq = [0] * (nums[-1] + 1)
for num in nums:
	dq[num] += 1
	if dq[num] == 1:
		for i in range(num * 2, nums[-1] + 1, num):
			dq[i] += 2
print(dq.count(1))


(_, *A) = map(int, open(0).read().split())
A.sort()
M = 10 ** 6 + 1
l = [0] * M
for a in A:
	if l[a] == 0:
		l[a] = 2
		for x in range(a * 2, M, a):
			l[x] = 1
	elif l[a] == 2:
		l[a] += 1
print(l.count(2))


N = int(input())
A = list(map(int, input().split(' ')))
a_max = max(A)
cnts = [0] * (a_max + 1)
for a in A:
	v = a
	while v <= a_max:
		cnts[v] += 1
		v += a
cnt = 0
for a in A:
	if cnts[a] == 1:
		cnt += 1
print(cnt)


n = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0] * 1000005
for i in nums:
	cnt[i] = cnt.get(i, 0) + 1
for i in nums:
	if flag[i] == 0 and cnt[i] == 1:
		ans += 1
	if flag[i] == 1:
		continue
	for j in range(i, 1000001, i):
		flag[j] = 1
print(ans)


n = int(input())
lis = list(map(int, input().split()))
maxL = max(lis) + 1
t = [0] * maxL
lis.sort()
for k in lis:
	t[k] += 1
	if t[k] == 1:
		for p in range(k * 2, maxL, k):
			t[p] += 2
print(t.count(1))


N = int(input())
AList = list(map(int, input().split()))
sortList = sorted(AList)
Amax = max(sortList)
dp = [0] * (Amax + 1)
for n in sortList:
	dp[n] += 1
	if dp[n] == 1:
		for i in range(n * 2, Amax + 1, n):
			dp[i] += 2
print(dp.count(1))


N = int(input())
a = list(map(int, input().split()))
a.sort()
k = max(a)
dp = [1] * (k + 1)
ans = 0
for i in range(N):
	if dp[a[i]] == 1:
		ans += 1
		if i < N - 1 and a[i + 1] == a[i]:
			ans -= 1
		for j in range(a[i], k + 1, a[i]):
			dp[j] = 0
print(ans)


n = int(input())
a = [int(i) for i in input().split(' ')]
max_a = max(a)
dp = [0] * (max_a + 1)
for i in a:
	for j in range(i, max_a + 1, i):
		dp[j] += 1
out = 0
for i in a:
	if dp[i] == 1:
		out += 1
print(out)


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np

def main():
	a = np.array(read().split(), np.int32)[1:]
	count = np.zeros(10 ** 6 + 1, np.int32)
	for ae in a:
		if count[ae] <= 1:
			count[::ae] += 1
	r = 0
	for ae in a:
		r += count[ae] == 1
	print(r)

def __starting_point():
	main()
__starting_point()


N = int(input())
A = [int(x) for x in input().split()]
A.sort()
A += [-1]
dp = [0] + [True] * 10 ** 6

def Solve():
	if A[0] == 1:
		if len(A) >= 2 and A[1] == 1:
			return 0
		else:
			return 1
	k = 0
	for i in range(1, 10 ** 6 + 1):
		if i == A[k]:
			tmp = A[k]
			cnt = 0
			while k <= N - 1 and A[k] == tmp:
				cnt += 1
				if cnt == 2:
					dp[tmp] = False
				k += 1
			for j in range(2 * i, 10 ** 6 + 1, i):
				dp[j] = False
	ans = 0
	for a in A[:-1]:
		if dp[a]:
			ans += 1
	return ans
ans = Solve()
print(ans)


N = int(input())
c = [0] * 8 ** 7
for a in input().split():
	c[int(a)] += 1
i = r = 0
for t in c:
	if t:
		c[::i] = [0] * -(-8 ** 7 // i)
	i += 1
	r += t == 1
print(r)


N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]
B = [0] * m
for a in A:
	B[a - 1] += 1
	if B[a - 1] == 1:
		for j in range(a * 2, m + 1, a):
			B[j - 1] = 2
print(B.count(1))


import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
A.sort()
MAXN = A[-1]
sieve = [1] * (MAXN + 1)
st = set()
for a in A:
	if a in st:
		sieve[a] = 0
	if sieve[a] == 1:
		for q in range(2 * a, MAXN + 1, a):
			if sieve[q] == 1:
				sieve[q] = 0
	st.add(a)
ans = 0
for a in A:
	ans += sieve[a]
print(ans)


import collections
n = int(input())
a = sorted([int(i) for i in input().split()])
cnt = collections.Counter(a)
max_i = a[-1] + 1
for i in a:
	if cnt[i] >= 2:
		del cnt[i]
	for j in range(i * 2, max_i, i):
		del cnt[j]
print(len(cnt))


N = int(input())
A = [int(x) for x in input().split()]
M = max(A)
count = [0] * (M + 1)
for i in range(N):
	count[A[i]] += 1
check = [True] * (M + 1)
for a in range(1, M + 1):
	if count[a] > 0 and check[a] == True:
		for k in range(2, M // a + 1):
			check[a * k] = False
ans = 0
for i in range(N):
	if count[A[i]] == 1 and check[A[i]] == True:
		ans += 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
M = 10 ** 6 + 1
cnt = [0] * M
for i in A:
	if cnt[i] != 0:
		cnt[i] = 2
		continue
	for j in range(i, M, i):
		cnt[j] += 1
ans = 0
for i in A:
	if cnt[i] == 1:
		ans += 1
print(ans)


n = int(input())
li = list(map(int, input().split()))
li.sort()
a_max = li[-1]
dp = [0] * (a_max + 1)
ans = 0
for a in li:
	for aj in range(a, a_max + 1, a):
		dp[aj] += 1
for a in li:
	if dp[a] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
AM = max(A) + 1
B = [0] * AM
for i in A:
	for j in range(i, AM, i):
		B[j] += 1
x = 0
for i in A:
	if B[i] == 1:
		x += 1
print(x)


n = int(input())
a = list(map(int, input().split()))
ans = 0
a.sort()
num = a[-1]
dp = [True] * num
seen = [0] * num
for i in range(n):
	num2 = a[i]
	if dp[num2 - 1] == True:
		if seen[num2 - 1] == 1:
			dp[num2 - 1] = False
		for j in range(2, num // num2 + 1):
			dp[j * num2 - 1] = False
	seen[a[i] - 1] = 1
ans = 0
for i in range(n):
	if dp[a[i] - 1] == True:
		ans += 1
print(ans)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
c = Counter(a)
for i in a:
	for j in range(i, a[-1] + 1, i):
		dp[j - 1] += 1
ans = 0
for i in a:
	if dp[i - 1] == 1 and c[i]:
		ans += 1
print(ans)


n = int(input())
A = [*map(int, input().split())]
mx = max(A)
c = [0] * (mx + 1)
l = [0] * (mx + 1)
for a in A:
	c[a] += 1
	for i in range(a * 2, mx + 1, a):
		l[i] = 1
ans = 0
for a in A:
	if not l[a] and c[a] <= 1:
		ans += 1
print(ans)


n = int(input())
(*l,) = map(int, input().split())
solv = 0
max = max(l) + 1
count = [0 for i in range(max)]
for i in l:
	for j in range(i, max, i):
		count[j] += 1
for k in l:
	if count[k] == 1:
		solv += 1
print(solv)


N = int(input())
A = list(map(int, input().split()))
dp = [0] * (10 ** 6 + 1)
A.sort()
A.append(10 ** 9 + 7)
ans = 0
for i in range(N):
	if dp[A[i]] == 0:
		if A[i] != A[i + 1]:
			ans += 1
		for j in range(1, int(10 ** 6 // A[i]) + 1):
			dp[A[i] * j] += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
max_A = A[-1]
arr = [0] * (max_A + 1)
for val in A:
	arr[val] += 1
	if arr[val] == 1:
		for j in range(2 * val, max_A + 1, val):
			arr[j] += 2
print(arr.count(1))


N = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = [0] * (A[-1] + 1)
for a in A:
	for i in range(a, A[-1] + 1, a):
		cnt[i] += 1
ans = 0
for a in A:
	if cnt[a] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)
for i in range(n):
	for j in range(a[i], m + 1, a[i]):
		c[j] += 1
ans = 0
for e in list(set(a)):
	if c[e] == 1:
		ans += 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
m = max(A)
X = [0] * (m + 1)
A.sort()
for i in range(n):
	for j in range(A[i], m + 1, A[i]):
		X[j] += 1
ans = 0
for i in range(n):
	if X[A[i]] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
B = [0] * (max(A) + 1)
count = 0
for i in A:
	for j in range(0, len(B), i):
		B[j] += 1
for k in A:
	if B[k] == 1:
		count += 1
print(count)


n = int(input())
A = list(map(int, input().split()))
m = max(A)
X = [0] * (m + 1)
A.sort()
for i in range(n):
	for j in range(A[i] * 2, m + 1, A[i]):
		X[j] = 2
	X[A[i]] += 1
print(X.count(1))


N = input()
A = sorted(map(int, input().split()))
M = A[-1] + 1
B = [True] * M
c = 0
x = 0
for i in A:
	if B[i] == True:
		if i != c:
			for j in range(i * 2, M, i):
				B[j] = False
			x += 1
			c = i
		else:
			B[i] = False
			x -= 1
print(x)


n = int(input())
a = list(map(int, input().split()))
m = max(a)
arr = [0] * (m + 1)
for i in a:
	for j in range(i, m + 1, i):
		arr[j] += 1
cnt = 0
for i in a:
	if arr[i] == 1:
		cnt += 1
print(cnt)


(n, *a) = map(int, open(0).read().split())
a.sort()
b = [0] * (10 ** 6 + 1)
for i in a:
	b[i] += 1
	if b[i] == 1:
		for j in range(2 * i, 10 ** 6 + 1, i):
			b[j] += 100
print(b.count(1))


N = int(input())
A = list(map(int, input().split()))
a_max = max(A)
B = [0] * (a_max + 1)
for ai in A:
	for multi in range(ai, a_max + 1, ai):
		B[multi] += 1
ans = 0
for ai in A:
	if B[ai] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
countList = [0] * (10 ** 6 + 1)
answer = 0
for i in A:
	countList[i] += 1
for j in range(10 ** 6 + 1):
	if countList[j] > 0:
		for k in range(2 * j, 10 ** 6 + 1, j):
			countList[k] = 0
	if countList[j] == 1:
		answer += 1
print(answer)


n = int(input())
l = list(map(int, input().split()))
m = max(l)
check = [0] * (m + 1)
for ll in l:
	for i in range(ll, m + 1, ll):
		check[i] += 2
	check[ll] -= 1
print(check.count(1))


from collections import Counter
M = 10 ** 7
(_, *l) = map(int, open(0).read().split())
d = [1] * M
C = Counter(sorted(l))
s = 0
for (a, b) in C.items():
	if b != 1:
		d[a] = 0
	elif d[a]:
		s += 1
	for j in range(a, M, a):
		d[j] = 0
print(s)


import sys
from itertools import chain
import numpy as np

def solve(N: int, A: 'List[int]'):
	check = np.zeros(max(A) + 1, dtype=np.uint8)
	for ai in A:
		if check[ai] == 0:
			check[ai::ai] += 1
		else:
			check[ai] = 2
	answer = 0
	for ai in A:
		if check[ai] == 1:
			answer += 1
	return answer

def main():
	tokens = chain(*(line.split() for line in sys.stdin))
	N = int(next(tokens))
	A = [int(next(tokens)) for _ in range(N)]
	answer = solve(N, A)
	print(answer)

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX
for x in a:
	cnt[x] += 1
ans = 0
for i in range(1, MAX):
	if cnt[i] > 0:
		for j in range(i * 2, MAX, i):
			ok[j] = False
		if ok[i] and cnt[i] == 1:
			ans += 1
print(ans)


from collections import Counter
(n, *a) = map(int, open(0).read().split())
s = set(a)
c = Counter(a)
m = max(s)
l = [True] * (m + 1)
ans = 0
for i in range(1, m + 1):
	if i in s and l[i]:
		if c[i] == 1:
			ans += 1
		for j in range(1, m // i + 1):
			l[i * j] = False
print(ans)


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


N = int(input())
A = list(map(int, input().split()))
M = max(A)
check = [0] * (M + 1)
for i in range(N):
	a = A[i]
	while a <= M:
		check[a] += 1
		a += A[i]
ans = 0
for i in range(N):
	if check[A[i]] == 1:
		ans += 1
print(ans)


import sys

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

def main():
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	max_A = max(A)
	dp = [True] * (max_A + 1)
	multi = [0] * (max_A + 1)
	for a in A:
		multi[a] += 1
		if multi[a] > 1:
			continue
		x = a
		while x + a <= max_A:
			x += a
			dp[x] = False
	ans = 0
	for a in A:
		if dp[a] and multi[a] == 1:
			ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
al = list(map(int, input().split()))
cnt = [0] * (10 ** 6 + 10)
for a in al:
	if cnt[a] > 1:
		continue
	for i in range(0, 10 ** 6 + 10, a):
		cnt[i] += 1
res = 0
for a in al:
	if cnt[a] == 1:
		res += 1
print(res)


N = int(input())
A = list(map(int, input().split()))
A.sort()
MAX = A[-1] + 1
num_tmp = [0] * MAX
for a in A:
	num_tmp[a] += 1
	if num_tmp[a] == 1:
		for i in range(2 * a, MAX, a):
			num_tmp[i] = 2
print(num_tmp.count(1))


import math
num = int(input())
arr = input().split()
arr = sorted([int(i) for i in arr])
lis1 = [0] * (arr[-1] + 1)
for num in arr:
	for j in range(0, len(lis1), num):
		lis1[j] += 1
cnt = 0
for num in arr:
	if lis1[num] == 1:
		cnt += 1
print(cnt)


n = int(input())
a = list(map(int, input().split()))
a.sort()
aMax = a[-1]
isAns = [0] * (aMax + 1)
for ai in a:
	isAns[ai] += 1
	if isAns[ai] == 1:
		for j in range(2 * ai, aMax + 1, ai):
			isAns[j] += 2
print(isAns.count(1))


(_, *a) = map(int, open(0).read().split())
a.sort()
m = -~a[-1]
c = [0] * m
for i in a:
	c[i] += 1
	if c[i] > 1:
		continue
	for j in range(i * 2, m, i):
		c[j] = 2
print(sum((c[i] == 1 for i in a)))


M = 10 ** 6 + 1
(_, *l) = map(int, open(0).read().split())
a = [0] * M
for i in sorted(l):
	if a[i]:
		a[i] = 2
		continue
	for j in range(i, M, i):
		a[j] += 1
print(sum((a[i] == 1 for i in l)))


n = int(input())
a = sorted(map(int, input().split()))
m = max(a) + 1
t = [0] * m
cnt = 0
for i in a:
	if t[i] == 0:
		cnt += 1
	elif t[i] == 1:
		cnt -= 1
	if t[i] < 2:
		t[i] += 1
		for j in range(i * 2, m, i):
			t[j] = 2
print(cnt)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
	for i in range(a, MAX_A + 1, a):
		X[i] += 1
ans = len([a for a in A if X[a] == 1 and C[a] == 1])
print(ans)


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


import numpy as np
import random
rand = False
if rand:
	N = 10 ** 5
	A = random.choices(list(range(1, 10 ** 6)), k=N)
else:
	N = int(input())
	A = list(map(int, input().split()))
A.sort()
MX = max(A)
ret = np.zeros(MX + 1, dtype=np.bool)
A = np.array(A, dtype=np.int32)
ret[A] = True
for i in range(N - 1):
	m = A[i] * 2
	if A[i] == A[i + 1]:
		m = A[i]
	ret[np.arange(m, MX + 1, A[i])] = False
print(np.sum(ret))


N = int(input())
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [True] * (Amax + 1)
ans = 0
for i in range(N - 1):
	p = A[i]
	if dp[p]:
		for j in range(1, Amax // p + 1):
			dp[p * j] = False
		if p != A[i + 1]:
			ans += 1
if dp[Amax]:
	ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a_max = max(a)
cnt = [0] * (max(a) + 1)
ans = 0
for ai in a:
	for multi in range(ai, a_max + 1, ai):
		cnt[multi] += 1
for ai in a:
	if cnt[ai] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
max_a = max(A) + 1
counter = [0 for _ in range(max_a)]
for i in A:
	for j in range(i, max_a, i):
		counter[j] += 1
res = 0
for a in A:
	if counter[a] == 1:
		res += 1
print(res)


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


(_, *l) = map(int, open(0).read().split())
a = [0] * 6 ** 8
for i in l:
	if a[i] < 1:
		for j in range(i * 2, 6 ** 8, i):
			a[j] = 2
	a[i] += 1
print(a.count(1))


n = int(input())
A = sorted(list(map(int, input().split())))
M = 10 ** 6 + 1
L = [0] * M
for a in A:
	L[a] += 1
	if L[a] == 1:
		for i in range(2 * a, M, a):
			L[i] += 2
print(L.count(1))


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = max(a)
arr = [0] * (m + 1)
flag = [True] * (m + 1)
ans = 0
for i in range(n):
	if flag[a[i]]:
		arr[a[i]] += 1
		if not arr[a[i]] == 1:
			continue
		for j in range(a[i] * 2, m + 1, a[i]):
			flag[j] = False
print(arr.count(1))


n = int(input())
l = list(map(int, input().split()))
l.sort()
j = [0] * (10 ** 6 + 1)
for i in l:
	j[i] += 1
	if j[i] == 1:
		for k in range(2 * i, 10 ** 6 + 1, i):
			j[k] += 100
print(j.count(1))


import sys

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

def main():
	n = int(input())
	A = list(map(int, input().split()))
	counts = [0] * (10 ** 6 + 5)
	for AA in A:
		counts[AA] += 1
	ans = 0
	for i in range(1, 10 ** 6 + 5):
		if counts[i] > 0:
			for j in range(i + i, 10 ** 6 + 5, i):
				counts[j] = -1
		if counts[i] == 1:
			ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


N = int(input())
ls = list(map(int, input().split()))
ls.sort()
M = max(ls)
A = [0] * (M + 1)
for i in range(N):
	a = M // ls[i]
	for j in range(1, a + 1):
		A[j * ls[i]] += 1
ans = 0
for i in range(len(ls)):
	if A[ls[i]] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
x = a[-1]
dp = [0 for _ in range(x + 1)]
for b in a:
	y = b
	while y <= x:
		dp[y] += 1
		y += b
ans = 0
for c in a:
	if dp[c] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1] * (10 ** 6 + 1)
ans = 0
for (idx, i) in enumerate(a):
	if ls[i] == 0:
		continue
	if idx == n - 1 or a[idx + 1] != i:
		ans += 1
	for j in range(i, 10 ** 6 + 1, i):
		ls[j] = 0
print(ans)


n = int(input())
a = list(map(int, input().split()))
m = max(a)
flag = [True] * (m + 1)
c = [0] * (m + 1)
b = list(sorted(a))
for i in b:
	x = i + i
	while x <= m:
		flag[x] = False
		x += i
	c[i] += 1
ans = 0
x = 0
l = []
ans = 0
for i in a:
	if flag[i] and c[i] <= 1:
		ans += 1
print(ans)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A = set(A)
B = [True] * (10 ** 6 + 1)
for a in A:
	for i in range(2 * a, 10 ** 6 + 1, a):
		B[i] = False
cnt = 0
for a in A:
	if B[a] == True and C[a] == 1:
		cnt += 1
print(cnt)


n = int(input())
data = list(map(int, input().split()))
mx = max(data)
marked = [0] * (mx + 1)
for a in data:
	for x in range(a, mx + 1, a):
		marked[x] += 1
ans = 0
for a in data:
	if marked[a] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
am = max(a)
dp = [[True, 0] for _ in range(am + 1)]
count = 0
for i in a:
	if dp[i][0] == False:
		continue
	elif dp[i][1] == 1:
		dp[i][0] = False
		count -= 1
	else:
		dp[i][1] = 1
		count += 1
		for j in range(2 * i, am + 1, i):
			dp[j][0] = False
print(count)


(n, *a) = map(int, open(0).read().split())
m = max(a) + 9
l = [0] * m
for x in a:
	l[x] += 1
r = 0
for i in range(m):
	if l[i]:
		r += l[i] == 1
		for j in range(i, m, i):
			l[j] = 0
print(r)


(n, *a) = map(int, open(0).read().split())
s = max(a) + 10
d = [0] * s
ans = 0
for i in a:
	d[i] += 1
for i in range(1, s):
	if d[i]:
		if d[i] == 1:
			ans += 1
		for j in range(i, s, i):
			d[j] = 0
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
M = 1000005
l = [0 for i in range(M)]
for i in a:
	if l[i] != 0:
		l[i] = 2
		continue
	for j in range(i, M, i):
		l[j] += 1
ans = 0
for i in a:
	if l[i] == 1:
		ans += 1
print(ans)


import collections
n = int(input())
line = list(map(int, input().split()))
arr = sorted(line)
coll = collections.Counter(arr)
Ma = arr[-1]
s = set()
for i in range(n):
	if coll[arr[i]] >= 2:
		s.add(arr[i])
	for j in range(2, Ma // arr[i] + 1):
		s.add(arr[i] * j)
cnt = 0
for a in arr:
	if a in s:
		continue
	cnt += 1
print(cnt)


(_, *a) = map(int, open(0).read().split())
a.sort()
p = [0] * a[-1]
for i in a:
	for j in range(1, a[-1] // i + 1):
		p[j * i - 1] += j
print(sum((i == 1 for i in p)))


N = int(input())
A = list(map(int, input().split()))
dp = [0] * (10 ** 6 + 1)
for a in A:
	dp[a] += 1
for i in range(1, len(dp)):
	if dp[i]:
		for j in range(i + i, len(dp), i):
			dp[j] = 0
print(dp.count(1))


N = input()
A = list(map(int, input().split()))
M = max(A) + 1
B = [True] * M
S = set()
x = 0
for i in A:
	if i not in S:
		S.add(i)
		for j in range(i * 2, M, i):
			B[j] = False
	else:
		B[i] = False
for i in A:
	if B[i] == True:
		x += 1
print(x)


n = int(input())
an = [int(i) for i in input().split()]
an.sort()
maxA = an[-1]
ans_table = [0] * (maxA + 1)
for ai in an:
	for k in range(1, int(maxA / ai) + 1):
		ans_table[ai * k] += 1
ans = 0
for ai in an:
	if ans_table[ai] == 1:
		ans += 1
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
am = a[-1] + 1
b = [0] * am
for i in a:
	b[i] += 1
	if b[i] == 1:
		for j in range(i * 2, am, i):
			b[j] = 2
print(b.count(1))


N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1] + 1
dp = [0] * (m * 2)
ans = 0
for a in A:
	for i in range(0, m // a + 1):
		dp[a * i] += 1
for a in A:
	if dp[a] == 1:
		ans += 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
c = 0
d = {}
f = [0] * (max(l) + 1)
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
x = sorted(list(set(l)))
for i in x:
	if d[i] == 1 and f[i] == 0:
		c += 1
	for j in range(2 * i, len(f), i):
		f[j] = 1
print(c)


N = int(input())
a = list(map(int, input().split()))
cnt = {}
for item in a:
	if item not in cnt:
		cnt[item] = 0
	cnt[item] += 1
A = list(set(a))
candidate = []
for item in A:
	if cnt[item] == 1:
		candidate.append(item)
judge = [True] * (10 ** 6 + 1)
for item in A:
	for i in range(2, 10 ** 6 // item + 1):
		judge[item * i] = False
ans = 0
for item in candidate:
	if judge[item]:
		ans += 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
mx = max(a)
mark = [0 for _ in range(mx + 1)]
for i in range(n):
	for x in range(a[i], mx + 1, a[i]):
		mark[x] += 1
ans = 0
for i in range(n):
	if mark[a[i]] == 1:
		ans += 1
print(ans)


from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))
m = A[-1]
C = Counter(A)
flags = [True for _ in range(m + 1)]
for a in A:
	if flags[a]:
		i = 2
		x = a * i
		while x <= m:
			flags[x] = False
			i += 1
			x = a * i
ans = 0
for a in set(A):
	if C[a] == 1 and flags[a]:
		ans += 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
l.sort()
max = l[n - 1]
dp = [0] * (max + 1)
for i in l:
	if dp[i] != 0:
		dp[i] += 1
		continue
	for j in range(i, max + 1, i):
		dp[j] += 1
sum = 0
for i in l:
	if dp[i] == 1:
		sum += 1
print(sum)


N = int(input())
A = list(map(int, input().split()))
ex = [0] * 1000001
for a in A:
	ex[a] += 1
cnt = 0
for i in range(1, 1000001):
	if ex[i] > 0:
		for j in range(i + i, 1000001, i):
			ex[j] = 0
		if ex[i] == 1:
			cnt += 1
print(cnt)


import numpy as np
n = int(input())
li_a = list(map(int, input().split()))
m = max(li_a)
e = np.zeros(m)
dup = []
for a in li_a:
	if e[a - 1] == 1:
		dup.append(a - 1)
		continue
	e[a - 1] = 1
for i in dup:
	e[i] = 0
for a in set(li_a):
	origin = a
	while a <= m:
		if a == origin:
			a += origin
			continue
		e[a - 1] = 0
		a += origin
print(int(sum(e)))


N = int(input())
A_list = list(map(int, input().split()))
yakusu = [0] * (10 ** 6 + 10)
for i in range(N):
	a = A_list[i]
	if yakusu[a] != 0:
		yakusu[a] = 2
		continue
	for j in range(a, 10 ** 6 + 10, a):
		yakusu[j] += 1
ans = 0
for a in A_list:
	if yakusu[a] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 1000005
for x in a:
	if cnt[x] != 0:
		cnt[x] = 2
	else:
		for i in range(x, 1000005, x):
			cnt[i] += 1
ans = 0
for x in a:
	if cnt[x] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(sorted(map(int, input().split())))
d = [0 for i in range(a[-1] + 1)]
c = 0
for i in range(len(a)):
	if d[a[i]]:
		continue
	if i == len(a) - 1 or a[i] != a[i + 1]:
		c += 1
	for j in range(a[i], a[-1] + 1, a[i]):
		d[j] = 1
print(c)


n = int(input())
a = list(map(int, input().split()))
a.sort()
e = [1] * (10 ** 6 + 1)
from collections import Counter
d = Counter(a)
ans = 0
for i in a:
	if d[i] == 1 and e[i] == 1:
		ans += 1
	if e[i] == 1:
		for j in range(i, 10 ** 6 + 1, i):
			e[j] = 0
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
flag = [0] * N
ans = 0
M = A[-1]
B = [0] * (M + 1)
for i in A:
	B[i] += 1
for i in A:
	if B[i] == 1:
		ans += 1
	for j in range(i, M + 1, i):
		B[j] += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
INF = 10 ** 6 + 1
lis = [1] * INF
exist = [0] * INF
for i in range(N):
	a = A[i]
	if lis[a] and exist[a] < 1:
		q = 2
		while a * q < INF:
			lis[a * q] = 0
			q += 1
	exist[a] += 1
cnt = 0
for a in A:
	if lis[a] and exist[a] == 1:
		cnt += 1
print(cnt)


def main():
	n = int(input())
	a = sorted([int(x) for x in input().split()])
	cnt = [0] * (10 ** 6 + 5)
	ans = 0
	for ai in a:
		(j, x) = (2, ai)
		while x <= 10 ** 6:
			if j == 2 and cnt[x] >= 1:
				cnt[x] += 1
				break
			cnt[x] += 1
			x = ai * j
			j += 1
	for ai in a:
		if cnt[ai] <= 1:
			ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


N = int(input())
A = list(map(int, input().split()))

def solve2(N, A):
	A.sort()
	amax = A[-1]
	dp = [True] * (amax + 1)
	cnt = [0] * (amax + 1)
	for a in A:
		cnt[a] += 1
	for i in range(amax):
		x = i + 1
		if cnt[x] > 1:
			dp[x] = False
		if cnt[x] > 0:
			y = x * 2
			while y <= amax:
				dp[y] = False
				y += x
	ansval = [x for x in A if dp[x]]
	ans = len(ansval)
	return ans

def solve1(N, A):
	ans = 0
	for i in range(N):
		is_ans = True
		for j in range(N):
			if i != j:
				if A[i] % A[j] == 0:
					is_ans = False
					break
		if is_ans:
			ans += 1
	return ans
print(solve2(N, A))


(n, *a) = map(int, open(0).read().split())
a.sort()
m = a[-1]
s = [0] * (m + 1)
ans = 0
for i in a:
	if s[i] <= 1:
		for j in range(i, m + 1, i):
			s[j] += 1
for k in a:
	if s[k] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
M = max(A)
memo = [0] * (M + 1)
i = 0
while i < N:
	a = A[i]
	memo[a] += 1
	x = a + a
	while x <= M:
		memo[x] += 2
		x += a
	i += 1
print(sum([1 if m == 1 else 0 for m in memo]))


n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0] * (m + 1)
cnt = 0
for i in arr:
	for j in range(i, m + 1, i):
		li[j] += 1
for i in arr:
	if li[i] == 1:
		cnt += 1
print(cnt)


N = int(input())
A = list(map(int, input().split()))
M = max(A)
X = [1] * (M + 1)
for a in A:
	X[a] -= 1
	for i in range(a * 2, M + 1, a):
		X[i] = -2
ans = 0
for a in A:
	if X[a] >= 0:
		ans += 1
print(ans)


from collections import Counter
(n, *A) = map(int, open(0).read().split())
A.sort()
(c, s) = (Counter(A), set())
M = max(A) + 1
ans = 0
for a in A:
	if a in s:
		continue
	ans += c[a] == 1
	for i in range(a, M, a):
		s.add(i)
print(ans)


import collections
n = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = collections.Counter(A)
for a in A:
	if cnt[a] >= 2:
		del cnt[a]
	for j in range(2 * a, A[-1] + 1, a):
		del cnt[j]
print(len(cnt))


n = int(input())
l = list(map(int, input().split()))
l.sort()
m = l[-1]
work = [0] * (m + 1)
for i in l:
	if work[i] <= 1:
		for j in range(i, m + 1, i):
			work[j] += 1
sm = 0
for s in l:
	if work[s] == 1:
		sm += 1
print(sm)


N = int(input())
A = list(map(int, input().split()))
A.sort()
M = A[-1] + 1
DP = [0] * M
for i in A:
	DP[i] += 1
	for j in range(i * 2, M, i):
		DP[j] = 2
print(DP.count(1))


N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
A_div = [0] * (10 ** 6 + 1)
for a in A:
	A_div[a] += 1
	if A_div[a] == 1:
		for j in range(2 * a, 10 ** 6 + 1, a):
			A_div[j] += 100
print(A_div.count(1))


N = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [False] * (10 ** 6 * 2)
ans = 0
for (idx, i) in enumerate(A):
	if dp[i]:
		continue
	tmp = i
	ans += 1
	while tmp < 10 ** 6 * 2 - 1:
		dp[tmp] = True
		tmp += i
	if idx != len(A) - 1 and A[idx + 1] == i:
		ans -= 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
m = max(A)
dp = [0] * (m + 1)
for a in A:
	if dp[a] >= 1:
		dp[a] += 1
	for i in range(2 * a, m + 1, a):
		dp[i] += 2
	dp[a] += 1
print(dp.count(1))


import collections
N = int(input())
a = list(map(int, input().split()))
a = sorted(a, reverse=False)
cnt = collections.Counter(a)
m = max(a) + 1
for i in a:
	if cnt[i] >= 2:
		del cnt[i]
	for j in range(i * 2, m, i):
		del cnt[j]
print(len(cnt.keys()))


from math import gcd
from itertools import combinations, permutations, accumulate, product
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import heapq
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
INF = float('inf')
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
n = I()
A = readInts()
is_ok = [0] * (10 ** 6 + 1)
se = set(A)
C = Counter(A)
for a in se:
	for b in range(a, 10 ** 6 + 1, a):
		is_ok[b] += 1
ans = 0
for i in range(n):
	if C[A[i]] >= 2:
		continue
	if is_ok[A[i]] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
dp = [0] * (max(A) + 1)
for a in A:
	for x in range(a, len(dp), a):
		dp[x] += 1
count = 0
for a in A:
	if dp[a] == 1:
		count += 1
print(count)


n = int(input())
a = list(map(int, input().split()))
l = [0] * (10 ** 6 + 1)
ans = 0
for i in a:
	if l[i] == 0:
		for j in range(i, 10 ** 6 + 1, i):
			l[j] += 1
	else:
		l[i] += 1
for i in a:
	if l[i] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
m = max(a)
y = [0] * (m + 1)
for i in a:
	x = i
	while x <= m:
		y[x] += 1
		x += i
ans = 0
for j in a:
	if y[j] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
maxA = max(a)
dp = [0] * (maxA + 1)
count = 0
for e in a:
	for i in range(e, maxA + 1, e):
		dp[i] += 1
for e in a:
	if dp[e] == 1:
		count += 1
print(count)


N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (A[-1] + 2)
c = 0
for a in A:
	if B[a] != 0:
		B[a] = 2
	for i in range(a, A[-1] + 1, a):
		B[i] += 1
for a in A:
	if B[a] == 1:
		c += 1
print(c)


N = int(input())
A = list(map(int, input().split()))
A.sort()
MAX = 10 ** 6 + 1
cnt = [0] * MAX
for x in A:
	if cnt[x] != 0:
		cnt[x] = 2
	else:
		for i in range(x, MAX, x):
			cnt[i] += 1
ans = 0
for x in A:
	if cnt[x] == 1:
		ans += 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
a_ = max(A)
A_ = list(set(A))
dp = [True] * (a_ + 1)
C = [0] * (a_ + 1)
for a in A:
	C[a] += 1
A_.sort()
ans = 0
for a in A_:
	tmp = a
	if dp[tmp]:
		tmp += a
		while tmp <= a_:
			dp[tmp] = False
			tmp += a
for a in A_:
	if dp[a]:
		if C[a] == 1:
			ans += 1
print(ans)


(n, a) = (int(input()), sorted(list(map(int, input().split()))))
m = a[-1] + 1
s = [0] * m
for i in a:
	s[i] += 1
for i in set(a):
	if s[i]:
		for j in range(i * 2, m, i):
			s[j] = 0
print(s.count(1))


n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a) + 1
c = [0] * m
for x in a:
	for i in range(x, m, x):
		if c[i] < 2:
			c[i] += 1
ans = 0
for i in a:
	if c[i] == 1:
		ans += 1
print(ans)


def abc170d_not_divisible():
	n = int(input())
	cnt = 0
	a = sorted(list(map(int, input().split())))
	flgs = [True] * (a[-1] + 1)
	if n == 1:
		print(1)
		return
	for i in range(n):
		if i != n - 1 and a[i] == a[i + 1]:
			flgs[a[i]] = False
			continue
		for j in range(a[i] * 2, a[-1] + 1, a[i]):
			flgs[j] = False
		if flgs[a[i]]:
			cnt += 1
	print(cnt)
abc170d_not_divisible()


n = int(input())
a = list(map(int, input().split()))
m = max(a)
lis = [0] * (m + 1)
for i in a:
	for j in range(i, m + 1, i):
		lis[j] += 1
count = 0
for i in a:
	if lis[i] == 1:
		count += 1
print(count)


import collections as c
(n, a1) = (int(input()), [*map(int, input().split())])
(a2, a3, b) = (set(a1), c.Counter(a1), [0] * (10 ** 6 + 1))
for i in a2:
	for j in range(i, 10 ** 6 + 1, i):
		b[j] += 1
print(sum((b[i] == 1 and a3[i] == 1 for i in a2)))


import math
ini = lambda : int(input())
inm = lambda : map(int, input().split())
inl = lambda : list(map(int, input().split()))
gcd = lambda x, y: gcd(y, x % y) if x % y else y

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	divisors.sort()
	return divisors

class UnionFind:

	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n

	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			(x, y) = (y, x)
		self.parents[x] += self.parents[y]
		self.parents[y] = x

	def size(self, x):
		return -self.parents[self.find(x)]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def members(self, x):
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i) == root]

	def roots(self):
		return [i for (i, x) in enumerate(self.parents) if x < 0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()}

	def __str__(self):
		return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))
mod = 10 ** 9 + 7
n = ini()
a = inl()
A = 10 ** 6 + 5
b = [0] * A
ans = 0
for i in a:
	if b[i] != 0:
		b[i] = 2
		continue
	for i in range(i, A, i):
		b[i] += 1
for i in a:
	if b[i] == 1:
		ans += 1
print(ans)


import math
from math import gcd, pi, sqrt
INF = float('inf')
MOD = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
import bisect
from collections import Counter, deque

def i_input():
	return int(input())

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

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	N = i_input()
	A = i_list()
	P = [True] * (10 ** 6 + 1)
	C = Counter(A)
	s = list(set(A))
	for x in s:
		t = x * 2
		while t <= 10 ** 6:
			P[t] = False
			t += x
	ans = 0
	for x in A:
		if C[x] == 1 and P[x] == True:
			ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


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


(n, *a) = map(int, open(0).read().split())
a.sort()
m = a[-1] + 1
cnt = [0] * m
for ai in a:
	if cnt[ai] != 0:
		cnt[ai] += 1
		continue
	for i in range(ai, m, ai):
		cnt[i] += 1
ans = 0
for ai in a:
	ans += cnt[ai] == 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
baisuu = [0] * (10 ** 6 + 1)
for i in a:
	if baisuu[i] >= 1:
		baisuu[i] = 2
		continue
	for j in range(i, 10 ** 6 + 1, i):
		baisuu[j] += 1
ans = 0
for i in a:
	if baisuu[i] == 1:
		ans += 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
dp = [0] * (max(a) + 1)
a.sort()
for i in a:
	temp = i
	while temp <= a[-1]:
		dp[temp] += 1
		temp += i
ans = 0
for i in a:
	if dp[i] == 1:
		ans += 1
print(ans)


import sys
n = int(input())
arr = list(map(int, sys.stdin.readline().split()))
arr = sorted(arr)
max_num = max(arr)
dp = [0 for i in range(max_num + 1)]
for i in arr:
	j = i
	while j <= max_num:
		dp[j] += 1
		j += i
ans = 0
for i in arr:
	if dp[i] == 1:
		ans += 1
print(ans)


from collections import Counter
N = int(input())
dp = [1] * 10 ** 7
C = Counter(sorted(list(map(int, input().split()))))
ans = 0
for (a, b) in C.items():
	if b != 1:
		dp[a] = 0
	elif dp[a]:
		ans += 1
	for j in range(a, 10 ** 6 + 1, a):
		dp[j] = 0
print(ans)


N = input()
A = list(map(int, input().split()))
N = int(N)
MA = max(A)
s = 0
LS = [0 for i in range(0, MA)]
for i in range(0, N):
	k = 1
	while A[i] * k <= MA:
		LS[A[i] * k - 1] += 1
		k += 1
for j in range(0, N):
	if LS[A[j] - 1] == 1:
		s += 1
print(s)


N = int(input())
MAX = 10 ** 6
table = [0] * (MAX + 1)
for x in map(int, input().split()):
	table[x] += 1
for i in range(MAX + 1):
	if table[i]:
		for j in range(2 * i if table[i] == 1 else i, MAX + 1, i):
			table[j] = 0
print(sum(table))


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
k = sorted(list(c.keys()))
kl = k[-1]
b = [1] * kl
cnt = 0
for i in k:
	if c[i] == 1 and b[i - 1] == 1:
		cnt += 1
	for j in range(1, kl + 1):
		if i * j > kl:
			break
		else:
			b[i * j - 1] = 0
print(cnt)


n = int(input())
a = list(map(int, input().split()))
ln = max(a) + 1
l = [0] * ln
ans = 0
for i in a:
	for j in range(i, ln, i):
		l[j] += 1
for i in a:
	if l[i] == 1:
		ans += 1
print(ans)


import bisect
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A)
maxA = max(A)
ans = 0
so_list = [1] * (maxA + 1)
index = 0
i = 0
while i < N:
	flag = 0
	now = A[i]
	if so_list[now] == 1:
		index = 0
		flag = 1
		while index + now <= maxA:
			so_list[index + now] = 0
			index += now
	right = bisect.bisect_right(A, now)
	if right - i == 1:
		if flag == 1:
			ans += 1
		i = right
	else:
		i += 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
m = [0] * (max(a) + 1)
lm = len(m)
cnt = 0
for i in a:
	j = 1
	while i * j < lm:
		m[i * j] += 1
		j += 1
for i in a:
	if m[i] == 1:
		cnt += 1
print(cnt)


n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0] * (a[-1] + 1)
for x in a:
	for i in range(x, a[-1] + 1, x):
		cnt[i] += 1
res = 0
for x in a:
	if cnt[x] == 1:
		res += 1
print(res)


n = int(input())
l = list(map(int, input().split()))
num = max(l) + 1
rcd = [0 for _ in range(num)]
for x in l:
	for y in range(x, num, x):
		rcd[y] += 1
ans = 0
for k in l:
	if rcd[k] == 1:
		ans += 1
print(ans)


M = 10 ** 6 + 1
(_, *l) = map(int, open(0).read().split())
b = [0] * M
for i in l:
	b[i] += 1
a = []
for i in sorted(l):
	if b[i]:
		if b[i] == 1:
			a += [i]
		for j in range(i, M, i):
			b[j] = 0
print(len(a))


N = int(input())
A = sorted(list(map(int, input().split())))
lim = max(A)
B = [0] * (lim + 1)
for i in range(N):
	B[A[i]] += 1
ans = N
for i in range(1, lim + 1):
	if B[i] == 0:
		continue
	if B[i] >= 2:
		ans -= B[i]
		B[i] = 0
	for j in range(i * 2, lim + 1, i):
		ans -= B[j]
		B[j] = 0
print(ans)


def main():
	N = int(input())
	A = list(map(int, input().split()))
	A = sorted(A)
	Amax = A[-1]
	count = [0 for _ in range(Amax + 1)]
	for a in A:
		for i in range(1, Amax // a + 1):
			count[i * a] += 1
	ans = 0
	for i in range(N):
		a = A[i]
		if count[a] == 1:
			ans += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


import collections
a = int(input())
b = [int(s) for s in input().split()]
b = sorted(b)
mod = int(1000000)
d = {}
e = collections.Counter(b)
X = int(0)
ans = int(0)
for i in range(a):
	if d.get(b[i]) == None:
		if e.get(b[i]) != 1:
			d[b[i]] = 1
		X = b[i]
		while X <= mod - b[i]:
			X += b[i]
			d[X] = 1
		X = 0
	else:
		pass
for i in range(a):
	if d.get(b[i]) == None:
		ans += 1
print(ans)


(n, *a) = map(int, open(0).read().split())
ma = 1001001
nums = [0] * ma
for i in a:
	nums[i] += 1
	if nums[i] == 1:
		for j in range(i + i, ma, i):
			nums[j] += 2
ans = nums.count(1)
print(ans)


n = int(input())
ar = list(map(int, input().split()))
ar.sort()
div = [0 for i in range(ar[-1] + 1)]
for i in ar:
	if div[i] <= 1:
		for j in range(i, ar[-1] + 1, i):
			div[j] += 1
ans = 0
for i in ar:
	if div[i] == 1:
		ans += 1
print(ans)


(n, *a) = map(int, open(0).read().split())
ma = 1001001
nums = [0] * ma
for q in a:
	nums[q] += 1
	if nums[q] == 1:
		for j in range(2 * q, ma, q):
			nums[j] += 2
cnt = 0
for elem in nums:
	if elem == 1:
		cnt += 1
print(cnt)


INF = 10 ** 6 + 1
(n, *l) = map(int, open(0).read().split())
from collections import *
c = Counter(l)
l = sorted(c.keys())
a = []
b = [0] * INF
for i in l:
	b[i] = 1
for i in l:
	if b[i]:
		if c[i] < 2:
			a += [i]
		for j in range(2 * i, INF, i):
			b[j] = 0
print(len(a))


N = int(input())
A = list(map(int, input().split()))
A.sort()
b = [0] * (10 ** 6 + 1)
for a in A:
	b[a] += 1
	if b[a] == 1:
		for i in range(2 * a, 10 ** 6 + 1, a):
			b[i] += 100
print(b.count(1))


N = int(input())
A = list(map(int, input().split()))
M = max(A)
F = [0] * (M + 1)
for i in range(N):
	a = A[i]
	b = a
	while b <= M:
		F[b] += 1
		b += a
T = 0
for i in range(N):
	if F[A[i]] == 1:
		T += 1
print(T)


def main():
	N = int(input())
	A = [int(a) for a in input().split(' ')]
	A.sort()
	l = A[-1]
	p = [1] * l
	for i in range(len(A)):
		a = A[i]
		if p[a - 1] == 1:
			p[a - 1] = 2
			for j in range(2 * a - 1, l, a):
				p[j] = 0
		elif p[a - 1] == 2:
			p[a - 1] = 0
	print(len([x for x in A if p[x - 1] in [1, 2]]))
main()


import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
maxa = max(a)
arr = [0] * (maxa + 1)
for i in a:
	if arr[i] == 0:
		t = math.ceil((maxa + 1) / i)
		for j in range(t):
			arr[i * j] += 1
	elif arr[i] == 1:
		arr[i] = 2
ans = 0
for i in a:
	if arr[i] == 1:
		ans += 1
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
max_A = A[-1] + 1
ans = [0] * max_A
for i in A:
	ans[i] += 1
	if ans[i] == 1:
		for j in range(i * 2, max_A, i):
			ans[j] = 2
print(ans.count(1))


N = int(input())
a_list = sorted(list(map(int, input().split())))
a_max = a_list[-1]
count = [0] * (a_max + 1)
for a in a_list:
	for j in range(a, a_max + 1, a):
		count[j] += 1
ans = 0
for a in a_list:
	if count[a] == 1:
		ans += 1
print(ans)


N = int(input())
(*A,) = map(int, input().split())
A = sorted(A)
if N == 1:
	print(1)
	return
flag = [0] * (10 ** 6 + 5)
for i in range(N):
	flag[A[i]] = 1
for i in range(N):
	if flag[A[i]] == 0:
		continue
	if i > 0 and A[i] == A[i - 1]:
		flag[A[i]] = 0
		continue
	for num in range(A[i] * 2, A[-1] + 1, A[i]):
		flag[num] = 0
print(sum(flag))


n = int(input())
a = sorted(map(int, input().split()))
l = [0] * (10 ** 6 + 1)
M = max(a)
for i in a:
	if l[i] == 0:
		l[i] = 1
		for j in range(i * 2, M + 1, i):
			l[j] = -1
	else:
		l[i] = -1
print(l.count(1))


n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)
b = [1] * m
c = [0] * m
for i in a:
	c[i - 1] += 1
	if b[i - 1]:
		for j in range(i * 2 - 1, m, i):
			b[j] = 0
x = 0
for i in range(m):
	if b[i] and c[i] == 1:
		x += 1
print(x)


n = int(input())
a = sorted(map(int, input().split()))
s = [0] * (m := (a[-1] + 1))
for x in a:
	s[x] += 1
for x in a:
	for j in range(x * 2, m, x):
		s[j] = 0
print(s.count(1))


N = int(input())
A = [int(x) for x in input().split()]
m = max(A) + 2
cnt = [0] * m
for a in A:
	cnt[a] += 1
	if cnt[a] == 1:
		for i in range(a + a, m, a):
			cnt[i] += 1
ans = 0
for a in A:
	ans += cnt[a] == 1
print(ans)


import math
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
b = [0 for _ in range(a[-1])]
c = 0
for i in a:
	x = i - 1
	while len(b) > x:
		b[x] += 1
		x += i
for i in a:
	if b[i - 1] == 1:
		c += 1
print(c)


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


N = int(input())
A = sorted(map(int, input().split()))
dp = [1] * 10 ** 6
for a in A:
	if dp[a - 1] == 1:
		dp[a - 1] = 2
		for i in range(a * 2, 10 ** 6 + 1, a):
			dp[i - 1] = 0
	elif dp[a - 1] == 2:
		dp[a - 1] = 0
print(sum([1 for a in A if dp[a - 1]]))


N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
L = [0] * (A[-1] + 1)
for a in A:
	L[a] = 1
for p in A:
	if not L[p]:
		continue
	L[p] += 1
	n = 2
	while p * n <= A[-1]:
		L[p * n] = 0
		n += 1
ans = L.count(2)
print(ans)


n = int(input())
arr = list(map(int, input().split()))
dp = [0] * (10 ** 6 + 1)
for i in sorted(arr):
	dp[i] += 1
	if dp[i] == 1:
		for j in range(2 * i, len(dp), i):
			dp[j] += 2
print(dp.count(1))


n = int(input())
arr = list(map(int, input().split()))
max_arr = max(arr)
dp = [0] * (max_arr + 1)
for i in arr:
	for j in range(i, max_arr + 1, i):
		dp[j] += 1
print([dp[i] for i in arr].count(1))


n = int(input())
a = list(map(int, input().split()))
m = max(a)
l = [0 for i in range(m + 1)]
for i in range(n):
	for j in range(a[i], m + 1, a[i]):
		l[j] += 1
c = 0
for i in range(n):
	if l[a[i]] == 1:
		c += 1
print(c)