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 = sorted(list(map(int, input().split())))

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > A[-1]:
            break
        check_list[tmp] += 1
        tmp += A[i]

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

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1]*3)
for i, num in enumerate(a):
    if a[(i-1)%n]==num or a[(i+1)%n]==num:
        if i-1>=0 or i+1<n:
            flag[num] = False
    for j in range(2, a[-1]//num+2):
        flag[j*num] = False
counter = 0
for i in a:
    if flag[i]:
        counter += 1
print(counter)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

a.sort()
dic=dict(Counter(a))

ans=0
for i in range(n):
    if dic[a[i]]==1:
        ans+=1
    if dic[a[i]]==0:
        continue
    dic[a[i]]=0
    j=1
    while 1:
        j+=1
        if j*a[i]>10**6+10:
            break
        if j*a[i] in dic:
            dic[j*a[i]]=0

print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline().rstrip('\n')
    

def calc(N, A):
    A.sort()
    M = A[N - 1] + 1
    b = [False for _ in range(M)]
    tmp = -1
    d = set()
    for a in A:
        if a == tmp:
            d.add(a)
            continue
        for i in range(a * 2, M, a):
            b[i] = True
        tmp = a
    n = 0
    for a in A:
        if not a in d:
            n += (0 if b[a] else 1)
    return n

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))

Solution (Python):
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
maxa = max(a)
a_s = set(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        for j in range(i, maxa+1, i):
            s.add(j)
        ans += 1

print(ans - len(same_s))

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
    ans = 0
    for ai in A:
        if dp[ai] == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
import math

n = int(input())
a = list(map(int, input().split()))
a.sort()
limit = max(a)
dp = [True] * (limit + 1)
archives = set()
for i in a:
    if i in archives:
        dp[i] = False
        continue
    archives.add(i)
    n = 2
    while i * n <= limit:
        dp[i * n] = False
        n += 1


ans = 0
for i in a:
    if dp[i] is True:
        ans += 1


print(ans)

Solution (Python):
from sys import stdin
n = int(input())
a = list(map(int, stdin.readline().split()))
a.sort()
amax = max(a)+1
e = [True]*amax
Alice = set()
Bob = set()
ans = 0

for i in range(n):
    if e[a[i]] == True:
        Alice.add(a[i])
        for j in range(a[i], amax, a[i]):
            e[j] = False
    else:
        if a[i] in Alice:
            Bob.add(a[i])

print(len(Alice - Bob))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
m = max(a)
t = [1]*(m+1)
for i in range(n):
    if(t[a[i]] == 1):
        x = a[i]*2
        while(x <= m):
            t[x] = 0
            x += a[i]
for i in range(n):
    if(t[a[i]] == 0):
        n -= 1
    elif(t[a[i]] == 1):
        t[a[i]] = -1
    elif(t[a[i]] == -1):
        t[a[i]] = -2
        n -= 2
    else:
        n -= 1
print(n)

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

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Solution (Python):


LI = lambda: list(map(int, input().split()))


N = int(input())
A = LI()

MAX = 10 ** 6


def main():
    A.sort()
    s = set()
    ans = N
    for i in range(N):
        a = A[i]
        if a in s:
            ans -= 1
            continue
        if i < N - 1 and A[i + 1] == a:
            ans -= 1
        n = MAX // a
        for i in range(1, n + 1):
            s.add(a * i)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

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

maxa=max(a)
dp=[0]*(maxa+1)
for num in a:
    for i in range(2,10**10):
        if num*i > maxa:
            break
        dp[num*i]=1

import collections
c = collections.Counter(a)

ans=0
for num,cnt in c.items():
    if cnt==1 and dp[num]==0:
        ans+=1
print(ans)

Solution (Python):


from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key




INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    


    
    
    
    
    M = 10**6+1
    
    memo = [0] * M
    ds = list(mulinputs())
    
    
    for i in ds: memo[i] += 1
    ds.sort()
    ans = []
    for i in ds:
        
        if not memo[i]:
            continue
        
        if memo[i] == 1:
            ans += [i]
        
        for j in range(i, M, i): memo[j] = 0
    
    print(len(ans))

Solution (Python):
from collections import Counter

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

m=a[-1]+1
dp=[1]*m
c=Counter(a)
ans=0
for i in a:
    if dp[i] and c[i]==1:
        ans+=1

    for j in range(2*i, m, i):
        dp[j]=0

print(ans)

Solution (Python):
n = int(input())
A = list(sorted(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])

biggest = max(S)
dp = [1 for i in range(biggest+1)]
for i in S:
  if i in D:
    dp[i] = 0
  for j in range(2*i,biggest+1,i):
    dp[j] = 0

ans = 0
for i in A:
  ans += dp[i]
print(ans)

Solution (Python):
n, *a = map(int, open(0).read().split())
a.sort()
am = a[-1] + 1
dp = [True] * am
ans = 0
dup = set()
for x in a:
    d = dp[x]
    if d:
        ans += 1
        for i in range(x, am, x):
            dp[i] = False
        dp[x] = None
    elif d == None:
        dup.add(x)

print(ans - len(dup))

Solution (Python):
N = int(input())
numbers = [int(i) for i in input().split()]

d = set()
s = set()

for n in numbers:
    if n in s: 
        d.add(n)
    else :
        s.add(n) 

M = max(s) 

X = [1 for _ 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
    
output = 0

for n in numbers:
    if X[n] == 1:
        output += 1
print(output)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [0]*(10**6+1)
    for a in A:
        B[a] += 1

    for i in range(1, 10**6):
        if not B[i]:
            continue
        j = 2*i
        while j <= 10**6:
            B[j] += 1
            j += i
    ans = 0
    for a in A:
        if B[a] <= 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

t = [True] * (10 ** 6 + 1)
d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1
    if d[a] > 1:
        t[a] = False

A = sorted(set(A))
for a in A:
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = Counter(A)

MAXN = max(A)
B = [False]*(MAXN+1)
for c in C.most_common():
    B[c[0]] = True
ans = 0
for i in range(MAXN + 1):
    if B[i]:
        if C[i]==1:
            ans += 1
        B[i::i] = [False]*(MAXN//i)
print(ans)

Solution (Python):

N = int(input())

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



A = list(sorted(A))
mark = [0]*(10**6+1)

for i in A:
    mark[i] += 1
    if mark[i] == 1:
        for j in range(2*i, len(mark), i):
            mark[j] += 2

print(mark.count(1))

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]

    if N == 1:
        print(1)
        return

    ax = max(A)+1
    dp = [0]*ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2
        
    print(dp.count(1))


if __name__ == "__main__":
    resolve()

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

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

maxa=max(a)
dp=[0]*(maxa+100)
for num in a:
    for i in range(2,10**10):
        if num*i > (maxa+50):
            break
        dp[num*i]=1

import collections
c = collections.Counter(a)

aa=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        aa.append(num)

ans=0
for num in aa:
    if dp[num]==0:
        ans+=1
print(ans)

Solution (Python):
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    S = list(set(A))
    ND = [True]*(10**6 + 1)
    for e in S:
        m = e*2
        while m <= 10**6:
            ND[m] = False
            m += e
    ans = 0
    for a in A:
        if C[a] == 1 and ND[a]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

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


ans_list = [True for _ in range(A[-1] + 1)]
ans = 0


c = Counter(A)

for a in A:
    if ans_list[a] == True:
        if c[a] == 1:
            ans += 1
        i = 2
        while a * i <= A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Solution (Python):

import numpy as np
def resolve():
    N = int(input())
    A = np.array(list(map(int, input().split())))

    cnt = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if cnt[x] > 1:
            continue
        cnt[::x] += 1
    ret = 0
    for x in A:
        ret += cnt[x] == 1

    print(ret)

if __name__ == "__main__":
    resolve()

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

m_a = max(A)+1
B = [0]*(m_a)

for i in A:
  B[i]+=1
  if B[i] == 1:
    for j in range(i*2, m_a, i):
      B[j]+=100
print(B.count(1))

Solution (Python):
def main():
    n, *A = map(int, open(0).read().split())
    A.sort()
    n = A[-1]
    isPrime = [True] * (n + 1)
    prep = 0
    for i in A:
        if prep == i:
            isPrime[prep] = False
            continue
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
        prep = i

    prep = res = 0
    for i in A:
        if prep == i:
            continue
        if isPrime[i]:
            res += 1
        prep = i
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()


n = int(input())
A = list(int(x) for x in input().split())
A.sort()
counter = Counter(A)
ans = 0
cache = set()
for a in A:
    if a in cache:
        continue
    tmp = a
    while tmp <= 10**6:
        cache.add(tmp)
        tmp += a
    if counter[a] == 1:
        ans += 1
print(ans)

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

a.sort()
mx = a[-1]

dp = [True for _ in range(mx)]

cnt = 0
for i, ai in enumerate(a):
    if dp[ai-1]:
        if i >= len(a)-1 or ai != a[i+1]:
            cnt += 1
        for j in range(ai - 1, mx, ai):
            dp[j] = False

print(cnt)

Solution (Python):
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
dic = defaultdict(int)
for a in A:
    dic[a] += 1
ctr = defaultdict(int)
ans = 0
for a in A:
    if dic[a] == 1 and ctr[a] == 0:
        ans += 1
    if ctr[a] == 0:
        m = 1
        while a*m <= 10**6:
            ctr[a*m] += 1
            m += 1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
M = max(a)
cands = [0]*M

ans = 0
for num in a:
    if cands[num-1] >= 2:
        continue
    for i in range(num, M+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
l.sort()
p=[1]*(l[-1]+1)
ans=0
for i in range(n):
  a=l[i]
  if p[a]==1:
    b=a
    while a<=l[-1]:
      p[a]=0
      a+=b
    if i<n-1:
      if l[i]==l[i+1]:
        pass
      else:
        ans+=1
    else:
      ans+=1
print(ans)

Solution (Python):
from collections import Counter

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


ans_list = [True for _ in range(A[-1] + 1)]
ans = 0


c = Counter(A)

for a in A:
    if ans_list[a] == True:
        if c[a] == 1:
            ans += 1
        i = 2
        while a * i <= A[-1]:
            ans_list[a * i] = False
            i += 1

print(ans)

Solution (Python):
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)
a = set(a)
for i in a:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

Solution (Python):
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)
a = set(a)
for i in a:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

Solution (Python):


from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key




INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    


    
    
    
    
    M = 10**6+1
    
    memo = [0] * M
    ds = list(mulinputs())
    
    for i in ds: memo[i] += 1
    ds.sort()
    ans = []
    for i in ds:
        if not memo[i]:
            continue
        if memo[i] == 1:
            ans += [i]
        
        for j in range(i, M, i): memo[j] = 0
    
    print(len(ans))

Solution (Python):
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in set(a):
  v=i
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
      is_p[j]=0

c=Counter(a)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    cho=set()
    for i in range(len(A)-1):
        if A[i]==A[i+1]:
            cho.add(A[i])
    A=list(set(A))
    SUGOI=[False]*(10**6+1)
    for a in A:
        for j in range(2*a,10**6+1,a):
            SUGOI[j]=True
    cnt=0
    A=list(set(A)-cho)
    for a in A:
        if SUGOI[a]==False:
            cnt+=1
    print(cnt)
    
    
if __name__=="__main__":
    main()

Solution (Python):
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)
M = max(a)
isprime = [0]*(M+1)

for i in range(n):
    if isprime[a[i]]==0:
        isprime[a[i]] = 1
        tmp = 2
        while a[i]*tmp < M+1:
            isprime[a[i]*tmp] = 2
            tmp += 1
    elif isprime[a[i]] == 1:
        isprime[a[i]] = 2

ans = 0
for ele in a:
    if isprime[ele] != 2:
        ans += 1
print(ans)

Solution (Python):
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    max_a = max(A)
    m = set()
    checked = set()
    duplicated = set()

    for a in A:
        if a in checked:
            duplicated.add(a)
            continue

        i = 2
        while a*i <= max_a:
            m.add(a*i)
            i += 1

        checked.add(a)

    ans = 0
    for a in A:
        if a in duplicated: continue

        if a not in m:
            ans += 1
    
    print(ans)
 
resolve()

Solution (Python):
from collections import defaultdict, Counter

def main():
  n, *A = map(int, open(0).read().split())
  A.sort()
  n = A[-1]
  isPrime = [True] * (n + 1)
  prep = 0
  for i in A:
    if prep == i:
      isPrime[prep] = False
      continue
    if isPrime[i]:
      for j in range(i * 2, n + 1, i):
        isPrime[j] = False
    prep = i

  prep = res = 0
  for i in A:
    if prep == i:
      continue
    if isPrime[i]:
      res += 1
    prep = i
  print(res)
if __name__ == '__main__':
  main()

Solution (Python):
from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)+1

numbers = [0] * m

for i in a:
    numbers[i] += 1

    if numbers[i] == 1:
        for j in range(2*i, m, i):
            numbers[j] += 2

print(numbers.count(1))

Solution (Python):
def main():
    N = int(input())
    A = list(map(int,input().split()))
    list.sort(A)
    pre_A = -1
    dp = [True for i in range(A[-1]+1)]
    for i in range(N):
        if pre_A != A[i]:
            for j in range(2,A[-1]+1):
                x = j*A[i]
                if x <= A[-1]:
                    dp[x] = False
                else:
                    break
            pre_A = A[i]
        else:
            dp[A[i]] = False
            
    count = 0
    for i in range(N):
        if dp[A[i]]:
            count += 1
    print(count)
        
if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
n = int(input())
a = list(map(int, stdin.readline().split()))
a.sort()
amax = max(a)+1
e = [0]*amax
ans = 0

for i in range(n):
    e[a[i]] += 1
    if e[a[i]] == 1:
        for j in range(2*a[i], amax, a[i]):
            e[j] += 2

print(e.count(1))

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

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

M = 10**6+1
sieve = [0]*(M)
for k,v in d.items():
    for i in range(k,M,k):
        sieve[i] += v


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

print(ans)

Solution (Python):
from collections import defaultdict
import math
n = int(input())
a = list(map(int,input().split()))
max_a = 10**6 +1 
a = sorted(a)
dic = defaultdict(lambda: False)

count = 0 
for i in range(n):
    ai = a[i]
    if dic[ai] == True:
        count+=1
    else:
        for j in range(1,math.ceil(max_a/ai)):
            dic[j*ai] = True
        if (i+1) < n and a[i]==a[i+1]:
            count+=1
print(n-count)

Solution (Python):
from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    if count[a] > 1:
      continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  
  return ans
  
print(main(np.array(A, np.int32)))

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

Solution (Python):
import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for j in range(n):
        a = A[j]
        if note[a]:
            if j != n-1 and A[j]==A[j+1]:
                ans-=1
            ans+=1
            
            
            
            temp = a 
            while temp <= a_max:
                note[temp]=False
                temp+=a

        
    
    print(ans)
main()