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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
bai = [0 for _ in range(max(a)+1)]
i = 2
for i in a:
    j = i
    while j < len(bai):
        bai[j] += 1
        j += i

res = 0
if n <= 1:
    print(n)
    exit()

for i in range(n):
    if bai[a[i]] == 1:
        res += 1

print(res)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
bai = [0 for _ in range(max(a)+1)]
i = 2
for i in a:
    j = i
    while j < len(bai):
        bai[j] += 1
        j += i

res = 0
if n <= 1:
    print(n)
    exit()

for i in range(n):
    if i == 0:
        if a[i] != a[i+1] and bai[a[i]] == 1:
            res += 1
    elif i == n-1:
        if a[i] != a[i-1] and bai[a[i]] == 1:
            res += 1
    else:
        if a[i] != a[i-1] and a[i] != a[i+1] and bai[a[i]] == 1:
            res += 1

print(res)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
num_list = [0] * 1000001
 
def solve():
    ans = 0
    for i in range(n):
        if num_list[a[i]] == 0:
            num_list[a[i]] += 1
            for j in range(2, (1000000 // a[i]) + 1):
                num_list[j * a[i]] += 1
        elif num_list[a[i]] == 1:
            num_list[a[i]] += 1
    for i in range(n):
        if num_list[a[i]] == 1:
            ans += 1
    return ans
 
print(solve())

Solution (Python):


import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return x if y == 0 else gcd(y, x%y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
A = LI()

A.sort()

dp = [0] * (10**6+1)
for a in A:
    if dp[a] != 0:
        dp[a] = 2
        continue

    for i in range(a, 10**6+1, a):
        dp[i] += 1

ans = 0
for a in A:
    if dp[a] == 1:
        ans += 1

print(ans)

Solution (Python):
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)

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
cnt=[0]*((10**6)+1)
unique=[]

for num in a:
    cnt[num]+=1

for i in range(10**6 +1):
    if cnt[i]==1:
        unique.append(i)

table=[0]*((10**6)+1)
a=list(set(a))

for elem in a:
    for i in range(2*elem, 10**6 +1, elem):
        table[i]=1

ans=0

for elem in unique:
    if table[elem]==0:
        ans+=1

print(ans)

Solution (Python):
n=int(input())
a=list(map(int, input().split()))
cnt=[0]*((10**6)+1)
unique=[]

for num in a:
    cnt[num]+=1

for i in range(10**6 +1):
    if cnt[i]==1:
        unique.append(i)

table=[0]*((10**6)+1)
a=list(set(a))

for elem in a:
    for i in range(2*elem, 10**6 +1, elem):
        table[i]=1

ans=0

for elem in unique:
    if table[elem]==0:
        ans+=1

print(ans)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split(' ')]

a.sort()
a_max = a[-1] + 1   
lst = [0] * a_max   

for x in a:
    lst[x] += 1                         
    if lst[x] == 1:                     
        for i in range(x*2, a_max, x):
            lst[i] += 1

output = 0
for x in a:
    if lst[x] == 1:
        output += 1
print(output)

Solution (Python):
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break

ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

Solution (Python):
N = int(input())
ls = list(map(int,input().split()))
    
Pls = [0] * (10**6+1)

for i in ls:
    Pls[i] += 1

ii = 0
for j in range(len(Pls)):
    if Pls[j] == 0:
        continue
    elif Pls[j] == 1:
        ii += 1
        t = 2*j
        while t <= 10**6:
            Pls[t] = 0
            t += j
    else:
        t = 2*j
        while t <= 10**6:
            Pls[t] = 0
            t += j

print(ii)

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import sys 
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@jit(cache=True)
def solve(A):
  count = np.zeros(10**6+10)
  for x in A:
    if count[x] > 1:
      continue
    count[::x] += 1
  ans = 0
  for x in A:
    ans += count[x] == 1
  return ans

N = int(readline())
A = list(map(int,readline().split()))
A = np.array(A)
print(solve(A))

Solution (Python):
N = int(input())
a = list(map(int, input().split()))

seen = set()

kago = [False for _ in range(1000001)]
double = set()
for i in range(N):
    if a[i] in seen:
        double.add(a[i])
        continue
    seen.add(a[i])
    if kago[a[i]] == True:
        continue
    
    now = a[i]*2
    while now<1000001:
        kago[now] = True
        now += a[i]

answer = 0
for i in range(N):
    if kago[a[i]] == True:
        continue
    if a[i] in double:
        continue
    answer += 1
    
print(answer)

Solution (Python):
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)

Solution (Python):
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    div = [0 for i in range(max(A)+1)]

    for a in A:
        if div[a] == 0:
            div[a] += 1
            idx = 2*a

            for i in range(10**6):
                if idx >= len(div):
                    break
                else:
                    div[idx] += 1
                    idx += a
                    
        else:
            div[a] += 1

    ans = 0
    for a in A:
        if div[a] == 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    ma = A[-1]
    B = [0] * (ma + 1)

    ans = 0
    prev = 0
    for a in A:
        if B[a] == 1:
            if prev == a:
                prev = 0
                ans -= 1
            continue
        for aa in range(a, ma + 1, a):
            B[aa] = 1

        prev = a
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    ma = A[-1]
    B = [False] * (ma + 1)

    ans = 0
    for i, a in enumerate(A):
        if B[a]:
            continue
        for aa in range(a, ma + 1, a):
            B[aa] = True

        if i != len(A) - 1 and A[i] == A[i + 1]:
            continue

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))

if np.count_nonzero(a==1)  >= 1:
    if np.count_nonzero(a==1)  >1:
        print(0)
    else:
        print(1)
else:
    for i in a:
        for j in np.arange(i, max_num, i):
            dp[j] += 1
    print(np.count_nonzero(dp[a] == 1))

Solution (Python):

def main():

    MAX_VALUE = 10**6 + 5

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

    cnt = [0] * MAX_VALUE

    ans = 0

    for x in a:

        if cnt[x] != 0:
            cnt[x] = 2
            continue

        for i in range(x, MAX_VALUE, x):
            cnt[i]+=1

    for x in a:
        if cnt[x] == 1:
            ans += 1 

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    N = max(a)+1
    tab = [1 for _ in range(N)]
    for i in range(n):
        x = a[i]
        if i < n-1 and a[i] == a[i+1]:
            tab[a[i]] = 0
        if tab[x]:
            ans += 1
        for i in range(N):
            if x*i >= N:
                break
            tab[x*i] = 0        
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
A = [*map(int, input().split())]
mx = max(A)
c = [0]*(mx+1)
for a in A:
    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)

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

m = max(a) + 1
a = sorted(a)

count = [0] * m

for x in a:
    if count[x] != 0:
        count[x] = 2
        continue

    for i in range(x, m, x):
        count[i] += 1

ans = 0
for x in a:
    if count[x] == 1:
        ans += 1

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    B = [0] * (A[-1] + 1)

    ans = 0
    for i, a in enumerate(A):
        if B[a] == 1:
            continue
        for aa in range(a, len(B), a):
            B[aa] = 1

        if i != len(A) - 1 and A[i] == A[i + 1]:
            continue

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = [*map(int, input().split())]
mx = max(A)
c = [0]*(1000000+1)
for a in A:
    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)

Solution (Python):
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))

if np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in a:
        for j in np.arange(i, max_num, i):
            dp[j] += 1
    print(np.count_nonzero(dp[a] == 1))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    B = [0] * (A[-1] + 1)

    ans = 0
    for i, a in enumerate(A):
        if B[a] == 1:
            continue
        for aa in range(a, A[-1] + 1, a):
            B[aa] = 1

        if i != len(A) - 1 and A[i] == A[i + 1]:
            continue

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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

m = 10 ** 6 + 7

count = [0] * m

for x in a:
    if count[x] != 0:
        count[x] = 2
        continue

    for i in range(x, m, x):
        count[i] += 1

ans = 0
for x in a:
    if count[x] == 1:
        ans += 1

print(ans)

Solution (Python):
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))

if n == 1:
    print(1)
elif np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in a:
        for j in np.arange(i, max_num, i):
            dp[j] += 1
    print(np.count_nonzero(dp[a] == 1))

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

MAX_N = max(A)+1
cnt = [0] * MAX_N 

for a in A:
  for i in range(a, MAX_N, a):
    if cnt[i] <= 2: cnt[i] += 1

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

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

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
d_set = set()
for i in range(N):
  if i == 0 and N > 1:
    if A[i] == A[i+1]:
      d_set.add(A[i])
  elif i < N - 1 and A[i-1] != A[i] and A[i] == A[i+1]:
    d_set.add(A[i])

print( len(c_set - d_set) )

Solution (Python):
N = int(input().strip())
A = list(map(int, input().strip().split()))
A.sort()
AMAX = max(A)
ans = 0
is_div = [True for i in range(AMAX+1)]
for i in range(N):
  a = A[i]
  if is_div[a]:
    if not ((i > 0 and A[i] == A[i-1]) or (i < N-1 and A[i] == A[i+1])):
      ans += 1
    for j in range(a, AMAX+1, a):
      is_div[j] = False
print(ans)

Solution (Python):


n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
maxi = a[-1]
boo = [True]*(maxi+1)

for i in range(n):
    k = a[i]
    if not boo[k]:
        continue
    if i != n-1 and k == a[i+1]:
        boo[k] = False
    for j in range(2,maxi//k+1):
        boo[k*j] = False
    
count = 0
for k in a:
    if boo[k] == True:
        count += 1

print(count)

Solution (Python):
N=int(input())
A=list(map(int,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)

Solution (Python):
import sys

def solve(a,n):
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]:
            for i in range(2*rep,m,rep):
                ava[i] += 2
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))

Solution (Python):
N = int(input())
*A, = map(int, input().split())
m = max(A)
cnt = [0] * (m + 1)
for elem in A:
    cnt[elem] += 1
unique = []
for i in range(m + 1):
    if cnt[i] == 1:
        unique.append(i)
cnt = [0] * (m + 1)
A = list(set(A))
for elem in A:
    for mul in range(elem * 2, m + 1, elem):
        cnt[mul] = 1
ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1
print(ans)

Solution (Python):

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] <= 100:  
        for j in range(i, m+1, i):
            s[j] += 1  


for k in a:
    if s[k] == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

    ma = max(A)
    B = [True] * (ma+1)
    for a in list(set(A)):
        for i in range(a+a, ma+1, a):
            B[i] = False

    import collections
    ans = 0
    for k, v in collections.Counter(A).items():
        if B[k] and v == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):




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)

Solution (Python):
import sys
input = sys.stdin.readline

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

    ma = max(A)
    B = [True] * (ma+1)
    A.sort()
    for a in A:
        for i in range(a+a, ma+1, a):
            B[i] = False

    import collections
    ans = 0
    for k, v in collections.Counter(A).items():
        if B[k] and v == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
n = int(input())
data = list(map(int, input().split()))
mx = max(data)
marked = [0]*(mx + 1)
for a in data:
    if marked[a] != 0:
        marked[a] += 1
    else:
        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)

Solution (Python):
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)

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

a = sorted(a)

dp  = [0] * (a[-1]+1)

for ai in a:
    if dp[ai]:
        dp[ai] += 1
        continue

    i = 1
    while True:
        if ai*i >= len(dp):
            break
        dp[ai*i] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai] == 1:
        ans += 1

print(ans)

Solution (Python):
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)

Solution (Python):
import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
 
@njit
def solve(A):
  count = np.zeros(10**6+10, np.int32)
  for x in A:
    if count[x] > 1:
      continue
    else:
      count[::x] += 1
  ret = 0
  for x in A:
    if count[x] == 1:
      ret += 1
  return ret
 
 
A = np.array(read().split(),np.int32)[1:]
print(solve(A))

Solution (Python):
n = int(input())
a_list = sorted(map(int, input().split()))

max_num = max(a_list)

is_ans = [False]*(max_num+1)
memo = [0]*(max_num+1)
for i in a_list:
    is_ans[i] = True
    memo[i] += 1

for i in range(1, max_num+1):
    if is_ans[i]:
        for j in range(2*i, max_num+1, i):
                is_ans[j] = False

    if memo[i] > 1:
        is_ans[i] = False

ans = is_ans.count(True)
print(ans)

Solution (Python):


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

a_dic = {}
for n in range(N):
    if A[n] in a_dic:
        a_dic[A[n]] += 1
    else:
        a_dic[A[n]] = 1

A = list(set(A))
A.sort()

maxA = max(A)
dp = [1 for i in range(maxA+1)]
ans = 0
for a in A:
    if dp[a] == 1 and a_dic[a] == 1:
        ans += 1
    j = a + a
    while j <= maxA:
        dp[j] = 0
        j += a
        

print(ans)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
D=[1]*(A[-1]+1)
for i in A:
  if D[i]==1:
    for j in range(A[-1]//i):
      D[i*(j+1)]=0
    D[i]=1
dic={}
for i in A:
  if i not in dic:
    dic[i]=1
  else:
    dic[i]+=1

for i in dic:
  if dic[i]>1:
    D[i]=0
    
ans=0
for i in A:
  if D[i]==1:
    ans+=1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 0
M = 1000005
cnt = [0 for _ in range(M)]
mx = max(a)+1
for x in a:
    for j in range(x,mx,x):
        cnt[j] += 1
    
for x in a:
    if cnt[x] == 1:
        ans += 1


print(ans)

Solution (Python):
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
def slove(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(slove(A))

Solution (Python):
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


def slove(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(slove(A))

Solution (Python):
def main():
    _ = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a = tuple(a)

    ans = 0
    mx = max(a) + 1
    dp = [0] * mx
    for i in a:
        if dp[i] == 2:
            continue
        else:
            for j in range(i, mx, i):
                dp[j] += 1
    for i in a:
        if dp[i] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

sieve = [True] * MAX
counts = [0] * MAX
a.sort()
ans = 0
sieve[0] = False
sieve[1] = False
for i in range(n):
  counts[a[i]] += 1
  if not sieve[a[i]]:
    continue
  for j in range(a[i]*2, MAX, a[i]):
    sieve[j] = False
  if counts[a[i]] == 1:
    ans += 1
  elif counts[a[i]] == 2:
    ans -= 1
    
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
M=max(A)+1
table=[0 for _ in range(M)]

for i in range(N):
    if i>0 and A[i]==A[i-1]:
        table[A[i]]=0
        continue
    table[A[i]]=1
    for n in range(2,M):
        if A[i]*n>=M:
            break
        table[A[i]*n]=0
print(sum(table))

Solution (Python):
n = int(input())

a = list(map(int, input().split()))

M = 1000005

cnt = [0 for i in range(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 x in a:
    if cnt[x] == 1:
        ans += 1
    
print(ans)

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

m = max(A)+1
dp = [1]*m
for a in A:
  if dp[a-1] == 1:
    dp[a-1] = 2
    for i in range(a*2, m, 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]]))

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
data = list(map(int, stdin.readline().rstrip().split()))

m = max(data)
l = [0] * (m + 1)
count = 0

for i in data:
    tmp = 1
    j = 1
    while tmp  <=  m:
        l[i * j] += 1
        j += 1
        tmp = i * j

for i in data:
    if l[i] == 1:
        count  += 1

print(count)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
memo = [0]*(10**6+1)

for a in A:
    memo[a] += 1
    if memo[a] < 2:
        for i in range(2*a, 10**6+1, a):
            memo[i] += 1

ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
A = sorted(list(map(int, input().split())))
memo = [0]*(10**6+1)

for a in A:
    memo[a] += 1
    if memo[a] < 2:
        for i in range(2*a, 10**6+1, a):
            memo[i] += 1

ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
memo = [0]*(10**6+1)

for a in A:
    memo[a] += 1
    if memo[a] < 2:
        for i in range(2*a, 10**6+1, a):
            memo[i] += 1

ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1

print(ans)

Solution (Python):
N = int(input())
*A, = map(int, input().split())
m = max(A)
cnt = [0] * (m + 1)
for elem in A:
    cnt[elem] += 1


unique = []
for i in range(m + 1):
    if cnt[i] == 1:
        unique.append(i)



cnt = [0] * (m + 1)
A = list(set(A))
for elem in A:
    for mul in range(elem * 2, m + 1, elem):
        cnt[mul] = 1
ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1
print(ans)

Solution (Python):
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)

Solution (Python):



def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()

    
    
    
    
    

    a_max = A[-1]
    dp = [0] * (a_max + 1)
    
    

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

    r = 0
    for a in A:
        if dp[a] == 1:
            r += 1

    print(r)

    
    
    
    
    

    
    
    
    

    


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
A = list(map(int, input().split()))

N = 10 ** 6 + 1


cnt = [0] * (N + 1)
for a in A:
    cnt[a] += 1

once = []
for a in A:
    if cnt[a] == 1:
        once.append(a)


bl = [True] * (N + 1)
A = list(set(A))
for elem in A:
    for m in range(elem * 2, N + 1, elem):
        bl[m] = False

res = 0
for elem in once:
    if bl[elem]:
        res += 1
print(res)

Solution (Python):
def main():
 
    import collections
 
    N = int(input())
    A_s = list(map(int, input().split()))
 
    max_A = max(A_s)
 
    CNT_A = collections.Counter(A_s).most_common()
    CNT_A.sort()
 
    NG_list = [True for i in range(max_A)]
    cnt = 0
    
    for i in range(len(CNT_A)):
        counter = CNT_A[i][1]
        num = CNT_A[i][0]
 
        index_num = num - 1
 
        if (counter > 1):
            NG_list[index_num] = False
 
        if (NG_list[index_num] == True):
            cnt += 1
            NG_list[index_num] = False
 
        coef = 1
        while (True):
            coef += 1
            tmp_num = coef * num
            
            if (tmp_num <= max_A):
                NG_list[tmp_num - 1] = False
            else:
                break
 
    print(cnt)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
def main():
 
    import collections
 
    N = int(input())
    A_s = list(map(int, input().split()))
 
    max_A = max(A_s)
 
    CNT_A = collections.Counter(A_s).most_common()
    CNT_A.sort()
 
    NG_list = [True for i in range(max_A)]
    cnt = 0
    
    for i in range(len(CNT_A)):
        counter = CNT_A[i][1]
        num = CNT_A[i][0]
 
        index_num = num - 1
 
        if (counter > 1):
            NG_list[index_num] = False
 
        if (NG_list[index_num] == True):
            cnt += 1
            NG_list[index_num] = False
 
        coef = 1
        while (True):
            coef += 1
            tmp_num = coef * num
            
            if (tmp_num <= max_A):
                NG_list[tmp_num - 1] = False
            else:
                break
 
    print(cnt)
 
 
if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


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

    
    
    

    table = [False]*(A[-1]+1)
    ans = 0
    for i in range(N):
        
        if table[A[i]]:
            continue
        
        for j in range(2, A[-1]//A[i]+1):
            table[A[i]*j] = True

    ans = 0
    for i in range(N):
        if table[A[i]] is False:
            ans += 1
            if i == 0:
                if len(A) == 1:
                    break
                if A[0] == A[1]:
                    ans -= 1
            elif i == N-1:
                if A[N-1] == A[N-2]:
                    ans -= 1
            else:
                if A[i] == A[i-1] or A[i] == A[i+1]:
                    ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	
	
	al=lin()
	vm=10**6+1
	rr = [0]*(vm)
	for v in al:
		rr[v]+=1
	ual=list(set(al))
	ual.sort()
	for v in ual:
		if rr[v]==0:
			continue
		for i in range(2*v, vm, v):
			rr[i]=0
	ret = rr.count(1)
	print(ret)
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import numpy as np
n = int(input())
a = list(map(int, input().split()))
count = np.zeros(10**6 + 1)
for x in a:
  if count[x] > 1:
    continue
  count[::x] += 1
ans = 0
for x in a:
  if count[x] == 1:
    ans += 1
print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	
	
	al=lin()
	vm=10**6+1
	rr = [0]*(vm)
	for v in al:
		rr[v]+=1
	
	for v in list(set(al)):
		for i in range(2*v, vm, v):
			rr[i]=0
	ret = rr.count(1)
	print(ret)
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)