Problem:


Score : 400 points

Problem Statement

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 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

l = [0] * 1000001

ans = 0

for i in range(n):
    l[a[i]] += 1

for i in range(1, 1000001):
    if l[i] > 0:
        if l[i] == 1:
            ans += 1
        for j in range(2, 1000000//i + 1):
            l[i * j] = 0

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
lis = [False]*10**6
ans = 0
for i in range(N):
    if lis[A[i]-1]==False:
        if (i<N-1 and A[i]!=A[i+1]) or i==N-1:
            ans += 1
        a = A[i]
        while a<=10**6:
            lis[a-1] = True
            a += A[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from collections import Counter

def solve():
    N = int(readline())
    A = list(map(int, readline().split()))

    c = Counter(A)
    A = set(A)

    f = [0] * (10 ** 6 + 10)

    for a in A:
        for b in range(a * 2, len(f), a):
            f[b] = 1
    
    count = 0
    for a in A:
        if f[a] == 0 and c[a] == 1:
            count += 1

    print(count)

solve()

Submission status: Accepted

Solution code:
import collections

_ = input()
lst = list(map(int,input().split()))

lst = sorted(lst)
elim = [False for _ in range(10**6 + 1000)]
c = collections.Counter(lst)

for x in lst:
  if elim[x]:
    continue
  for i in range(x+x,10**6+1,x):
    elim[i] = True
  if c[x] > 1:
    elim[x] = True

cnt = 0
for x in lst:
  if not elim[x]:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
b = [0] * 1000001
chk = [0] * 1000001
s = set(a)

for x in a:
    chk[x] += 1

for x in s:
    for y in range(x, 1000001, x):
        b[y] += 1

cnt = 0

for x in s:
    if b[x] == 1 and chk[x] == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
#pyrival orz
import os
import sys
from io import BytesIO, IOBase

"""
    for _ in range(int(input())):
    n,m=map(int,input().split())
    n=int(input())
    a = [int(x) for x in input().split()]
"""

def main():
    n=int(input())
    a = [int(x) for x in input().split()]
    N = 10**6
    ans=[True]*(1+N)
    ct=[False]*(1+N)
    for x in a:
        if ct[x]:
            ans[x]=False
            continue
        ct[x]=True
        for j in range(2*x,N+1,x):
            ans[j]=False
    cnt=0
    for x in a:
        cnt+=ans[x]
    print(cnt)

# region fastio

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")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))+[10**7]
a.sort()
e = np.zeros(10**6+1)
ans = 0
for i in range(n):
    if e[a[i]] == 0:
        e[::a[i]] = 1
        if a[i] != a[i+1]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0 for _ in range(10**6+1)]
for x in a:
	num[x] += 1

ok = [True for _ in range(10**6+1)]
ans = 0
for i in range(1, 10**6+1):
	if num[i] == 1 and ok[i] == True:
		ans += 1
	if num[i]:
		for j in range(i, 10**6+1, i):
			ok[j] = False
print(ans)

Submission status: Accepted

Solution code:
import sys

n = input()
x = list(map(int, input().split()))
#x = [i for i in range(2, 10**5)]

MAXA = 10**6

used = [False for i in range(MAXA + 5)]
result = 0
counts = {}
for a in x:
	if a in counts:
		counts[a] += 1
	else: 
		counts[a] = 1

for x in range(MAXA + 1):
	if not used[x]:
		if x in counts:
			count = counts[x]		
			if count == 1:
				result += 1

			y = 2*x
			while y <= MAXA:
				used[y] = True
				y += x

print(result)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()

ma = 2 * 10 ** 6
tab = [False] * (ma)

mapp = {}
for i in a:
    if i in mapp:
        mapp[i] += 1
    else:
        mapp[i] = 1

ans = 0
for i in a:
    if not tab[i]:
        if mapp[i] == 1:
            ans += 1
        for j in range(i, ma, i):
            tab[j] = True
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
l = list(map(int,input().split()))
c = Counter(l)

l.sort()
check = [-1]*(10**6+2)

ans = 0
for i in l:
    if check[i] == -1:
        if c[i] == 1:
            ans += 1
        for j in range(i,10**6+2,i):
            check[j] = i
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np


def solve(n, a_list):
    count_a = Counter(a_list)
    res = 0
    # sieve
    sieve = np.ones(10 ** 6 + 1)
    for i in range(10 ** 6 + 1):
        if sieve[i]:
            if count_a[i] > 0:
                sieve[i::i] = 0
            if count_a[i] == 1:
                res += 1
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(5, [24, 11, 8, 3, 16]) == 3
    assert solve(4, [5, 5, 5, 5]) == 0
    assert solve(10, [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]) == 5


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

ok = [True]*1000005

a.sort()
ans=0
for i in range(n):
    if i<n-1 and a[i]!=a[i+1] and ok[a[i]]:
        ans+=1
    elif i==n-1 and ok[a[i]]:
        ans+=1
    if ok[a[i]]:
        for j in range(a[i],1000004,a[i]):
            ok[j]=False

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int,input().split()))

al.sort()
table = [False]*1000001
table2 = [False]*1000001

for a in al:
    if table2[a]:
        table[a]=True
    if not table[a]:
        table2[a] = True
        for i in range(a+a,1000001,a):
            table[i]=True
    

cnt=0
for a in al:
    if not table[a]:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int,input().split())

if N==1:
    print(1)
    exit()

A.sort()

L = [False]*(10**6+1)
for i,a in enumerate(A):
    if A[i-1] == a:
        L[a] = True
        continue
    if L[a]: continue
    for i in range(2,10**6+1):
        if a*i > 10**6: break
        L[a*i] = True

ans = 0
for a in A:
    if not L[a] : ans += 1
print(ans)

Submission status: Accepted

Solution code:

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

from collections import Counter

C = Counter(A)

K = list(C.keys())

D = [0]*(10**6 + 1)

for k in K:
    l = 2*k
    while l <= 10**6:
        D[l] = 1
        l+=k
count = 0
for k in K:
    if C[k]==1 and D[k]==0:
        count+=1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int,input().split()))

from collections import defaultdict
dic = defaultdict(int)


for a in al:
    dic[a] += 1

if dic[1]:
    if dic[1] == 1:
        print(1)
    else:
        print(0)
    exit()

al = sorted(al)
from math import sqrt
M = 10**6+1
p = [1]*(M+1)
p[0] = p[1] = 0
ans = 0
for x in al:
    if p[x]:
        if dic[x] == 1:
            ans += 1
        for y in range(x, M+1, x):
            p[y] = 0

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(A)
t = [True] * (10**6 + 1)

ans = 0
for k, v in c.items():
    if t[k]:
        if v == 1:
            ans += 1
        for j in range(k, 10**6+1, k):
            t[j] = False

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
s = set(A)
F = [False]*(10**6+100)
cnt = Counter(A)

for i in range(10**6+100):
    if i in s:
        F[i] = True

for i in range(1, 10**6+100):
    if i in s:
        for j in range(2*i, 10**6+100, i):
            F[j] = False
    
ans = 0

for i in range(10**6+100):
    if F[i] and cnt[i]==1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
from collections import Counter

n = int(input())
a = [int(item) for item in input().split()]
a.sort()

cnt = Counter(a)
if cnt[1] > 1:
    print(0)
    exit()
if cnt[1] == 1:
    print(1)
    exit()

MAX_SIZE = 10**6 + 10
is_divisible = [True] * MAX_SIZE 
ans = 0
for item in a:
    if is_divisible[item]:
        if cnt[item] == 1:
            ans += 1
        for i in range(MAX_SIZE):
            if i * item >= MAX_SIZE:
                break
            is_divisible[i * item] = False
    else:
        continue

print(ans)

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1<<32 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)


N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 1000001
for a in A:
    X[a] += 1

ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=0
    dic[A[i]]+=1
ban=set([])
res=0
for i in range(N):
    a=A[i]
    if a not in ban:
        if dic[A[i]]==1:
            res+=1
        for j in range(1,10**6//a+1):
            ban.add(a*j)

print(res)

Submission status: Accepted

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

Submission status: Accepted

Solution code:
# D - Not Divisible
from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
A = deque(A)
B = [0]*(10**6+1)
ans = 0
for _ in range(N):
    x = A.popleft()
    if B[x]==0:
        ans += 1
        B[x] = 2
        tmp = 2*x
        while tmp<=10**6:
            B[tmp] = 1
            tmp += x
    elif B[x]==2:
        B[x] = 1
        ans -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

LIST=[0]*(10**6+1)

for a in A:
    LIST[a]+=1
ANS=0

for i in range(10**6+1):
    if LIST[i]==1:
        ANS+=1
    if LIST[i]!=0:
        for j in range(2*i,10**6+1,i):
            if LIST[j]!=0:
                LIST[j]+=1
print(ANS)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=sorted([int(i) for i in input().split()])
ma=max(A)
C=[True]*(ma+1)

import collections
AA=collections.Counter(A)

AS=list(set(A))
AS.sort()
for a in AS:
  if AA[a]>1:
    ct=1
  else:
    ct=2
  while a*ct<=ma:
    C[a*ct]=False
    ct+=1
ans=0
for a in AA.keys():
  if C[a]:
    ans+=AA[a]
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4[::1],)', cache=True)
def solve(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

A = np.array(read().split(), np.int32)[1:]

print(solve(A))

Submission status: Accepted

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

D = [0] * (10 ** 6 + 1)
A.sort()
A = A + [10 ** 7]
cnt = 0
for i in range(N):
  if D[A[i]] == 0:
    if A[i] != A[i + 1]:
      cnt += 1
    for j in range(A[i], 10 ** 6 + 1, A[i]):
      D[j] = 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

import numpy as np

n, *aaa = map(int, sys.stdin.buffer.read().split())
cnt = Counter(aaa)
duplicated = {x for x, c in cnt.items() if c > 1}
aaa.sort()

can = np.ones(aaa[-1] + 1, np.int8)

ans = 0
for a in aaa:
    if can[a] == 0:
        continue
    if a not in duplicated:
        ans += 1
    can[a * 2::a] = 0

print(ans)

Submission status: Accepted

Solution code:
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
  if cnt[arr[i]]>=2:
    continue
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

M = 10**6+1
L = [0]*M

for a in A:
    if L[a] >= 1:
        L[a] = 2
        continue
    L[a] = 1
    i = 2
    while a*i < M:
        L[a*i] = 2
        i += 1

ans = 0
for a in A:
    if L[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
b = [0 for _ in range(10**6+1)]
ans = 0
for i in range(n):
  x = a[i]
  if b[x]:
    continue
  if i != n-1:
    if a[i+1] != x:
      ans += 1
      #print(x)
  else:
    ans += 1
  now = x
  while True:
    try:
      b[now] = 1
      now += x
    except:
      break
#print(a)
print(ans)

Submission status: Accepted

Solution code:
#Ai/Aj not integer
#5
#24 11 8 3 16
#のときは、24は8,3があるからダメ　16も8があるからダメ
N=int(input())
A=[int(i) for i in input().split()]
D=set()
S=set()
for i in range(N):
    if A[i] in S:
        D.add(A[i])
    else:
        S.add(A[i])
M=max(S)
X=[1 for i in range(M+1)]
for a in S:
    if a in D:
        X[a]=0
    for i in range(2*a,M+1,a):
        X[i]=0
ans=0
for i in range(N):
    if X[A[i]]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

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

C = Counter(A)
cannot = set()
L= max(A)
ans = 0
for a in A:
    if a in cannot: continue
    if C[a] == 1:
        ans += 1
    ind = 1
    while a*ind <= L:
        cannot.add(a*ind)
        ind += 1

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    M = 10**6

    A.sort()
    C = Counter(A)
    ans = 0
    seen = [0] * (M+1)
    A = set(A)
    for a in A:
        if C[a] == 1 and seen[a] == 0:
            ans += 1
        for j in range(1, M+1):
            if a * j > M:
                break
            seen[a*j] = 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
            x = i
            while x <= N:
                f[x] = 0
                x += i
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
            x = i
            while x <= N:
                f[x] = 0
                x += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()

f = [0] * 1000005
for v in a:
    f[v] += 1
for i in range(1000000, 0, -1):
    if f[i] == 0:
        continue
    j = i*2
    while j <= 1000000:
        f[j] += f[i]
        j += i
ct = 0
for v in a:
    if f[v] == 1:
        ct += 1
print(ct)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
import numpy as np
import sympy
#from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#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()  # ignore trailing spaces

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


N = ni()
A = na()
A.sort()
s = set()
ans = 0
for i in range(len(A)):
    ai = A[i]
    li = sympy.divisors(ai)
    flag = True
    for pn in li:
        if pn in s:
            flag = False
            break
    if flag:
        ans += 1
    s.add(ai)
if A.count(A[0]) == N:
    print(0)
else:
    print(ans)