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:
from collections import Counter
 
 
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    searched = [0 for _ in range(10 ** 6 + 1)]
    ans = 0
    for i in range(1, 10 ** 6 + 1):
        if counter[i] == 0:
            continue
        if searched[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1, ((10 ** 6) // i) + 1):
            searched[i * j] = 1
    print(ans)
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = 10 ** 6 + 1
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 x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
maxA = max(A)
B = [0]*(maxA)

for i in A:
    B[i-1] += 1

ans = 0
for i in sorted(A):
    if B[i-1] == 0:
        continue
    if B[i-1] == 1:
        ans += 1
    for j in range(i,maxA+1,i):
        B[j-1] = 0

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
alst = list(map(int, input().split()))
alst.sort()
tmp = [0 for _ in range(10 ** 6 + 10)]
ans = 0
flg = True
if n == 1:
    print(1)
    exit()
if alst[0] == 1:
    if alst[1] == 1:
        print(0)
    else:
        print(1)
    exit()
for num in alst:
    if tmp[num] == 2:
        if flg:
            ans -= 1
            flg = False
        continue
    flg = True
    if tmp[num] == 1:
        continue
    ans += 1
    tmp[num] = 2
    xx = num * 2
    while xx < 10 **  6 + 1:
        tmp[xx] = 1
        xx += num
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def resolve():
    N = int(input())
    A = list(map(int,input().split()))

    B= set(A)

    A.sort()
    dpt = [True]*(A[-1]+1)
    for i in A:
        if dpt[i]==False:
            continue
        for j in range(i*2,A[-1]+1,i):
            dpt[j] = False
    co = Counter(A)
    c=0
    for i,v in dict(co).items():
        if dpt[i] and v==1:
            c+=1
    print(c)
resolve()

Submission status: Accepted

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

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

for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for i in range(M)[a::a]:
        cnt[i] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0 for _ in range(a[-1] + 1)]

for x in a:
    for j in range(x, a[-1] + 1, x):
        dp[j] += 1
ans = 0
for x in set(a):
    #print(x)
    if dp[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    n = int(readline())
    a = list(map(int, readline().split()))
    a.sort()
    limit = a[-1]
    dp = [0] * (limit + 1)
    for aa in a:
        dp[aa] += 1
        if dp[aa] == 1:
            for i in range(aa * 2, limit + 1, aa):
                dp[i] += 1
    print(sum((1 for aa in a if dp[aa] == 1)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
 
As.sort()
 
st = set(As)
m = As[-1]
rlt = 0
Fs = [1]*(m+1)
 
for i in range(N):
  if i > 0 and As[i] == As[i-1]:
    Fs[As[i]] = 0
    continue
  j = 2
  while As[i]*j <= m:
    Fs[As[i]*j] = 0
    j += 1

for a in As:
  rlt += Fs[a]
    
print(rlt)

Submission status: Accepted

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time


def main():

    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)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

n = int(input())
a = list(map(int,input().split()))+[10**7]
a.sort()
l = [True]*(10**6+1)

ans=0
a.sort()
for i in range(n):
    if l[a[i]]:
        for j in range(a[i],10**6+1,a[i]):
            l[j]=False
        if a[i]!=a[i+1]:
            ans+=1
print(ans)

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:
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 = 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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
sorted_As = sorted(map(int, input().split()))
A_max = sorted_As[N-1]

dp = [True for i in range(A_max+1)]

ans = 0
for i in range(len(sorted_As)):
    a = sorted_As[i]
    
    if not dp[a]:
        continue

    if i == len(sorted_As)-1 or a != sorted_As[i+1]:
        ans += 1

    i = 1
    while a*i <= A_max:
        dp[a*i] = False
        i += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
mx = max(a)
flag = [True]*(mx+1)
c = Counter(a)
a.sort()
ans = 0
for i in range(n):
    if flag[a[i]]:
        if c[a[i]] == 1: ans += 1
        for j in range(a[i],mx+1,a[i]): flag[j] = False
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np

A_MAX = 10 ** 6 + 1

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

dp = np.zeros(shape=A_MAX, dtype=np.int64)

if A[1] == 1:
    print(1)
elif A[1] > 1:
    print(0)
else:
    for a in A.keys():
        multiples = np.arange(a, A_MAX, a)
        np.add.at(dp, multiples, 1)

    ans = 0
    for a, count in A.items():
        if count > 1:
            continue
        if dp[a] == 1:
            ans += 1

    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter

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

dp = [0]*(a[-1]+1)
dp = np.array(dp,int)

for i in a:
    dp[i] = 1

for i in a:
    if dp[i] == 1:
        dp[2*i::i] = 0

c = Counter(a)

for i,j in c.items():
    if j > 1:
        dp[i] = 0

print(dp.sum())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0]*(1000000+1)
cnt = 0
for i in range(len(a)):
  if dp[a[i]]==1:
    continue
  j = 2
  while(a[i]*j<=a[-1]):
    dp[a[i]*j] = 1
    j += 1
  if i!=len(a)-1 and a[i+1]==a[i]:
    dp[a[i]] = 1
    continue
  cnt += 1
  dp[a[i]] = 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()
#print(A)
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))

Submission status: Accepted

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

X = [0] * (ma + 1)
ans = 0
A.sort()

for a in A:
    X[a] += 1
for a in A:
    if X[a] ==1:
        ans += 1
    num = 1
    while num * a <= ma:
        X[num * a] += 2
        num += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

A.sort()
m = A[-1]

import collections
h = collections.Counter(A)

ans = 0
for a in A:
	if h[a] == 0:
		continue
	if h[a] == 1:
		ans += 1
	for j in range(a, m+1, a):
		h[j] = 0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Al = sorted([int(i) for i in input().split()])
maxAl = Al[-1]
markl = [-1] * (maxAl+1)

for i in Al:
    if markl[i] == 1:
        continue
    if markl[i] == 0:
        markl[i] = 1
        continue
    markl[i] = 0
    p = i*2
    while p <= maxAl:
        markl[p] = 1
        p += i
print(markl.count(0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
kari=[0]*((10**6)+1)
A.sort()
hako=[]
for i in range(N):
    kari[A[i]]+=1

for i in range(N):
    if kari[A[i]]==1:
        hako.append(A[i])
kari=[0]*((10**6)+1)
aru=A.copy()
count=0
aru=list(set(aru))
#print(hako)
for i in aru:
    for j in range(i*2,10**6+1,i):
        kari[j]+=1
for i in hako:
    if kari[i]==0:
        count+=1
print(count)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(a_list)
divisible = [True] * (10**6+1)
for el, count in c.items():
    if count!=1:
        divisible[el] = False
    for i in range(el*2, 10**6+1, el):
        divisible[i] = False
a_list = list(set(a_list))
ans = len(
    [1 for a in a_list if divisible[a]]
)    
print(ans)

Submission status: Accepted

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




MAX=max(A)
nums=[0]*(MAX)

ans=0

for i in range(N):
    a=A[i]
    kousin=True
    if i!=0:
        if A[i-1]==a:
            kousin=False
    if i!=N-1:
        if a==A[i+1]:
            kousin=False

    if nums[a-1]==0 and kousin:
        ans+=1
        
                
        if a>MAX//2:
            continue
            

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
print(ans)

Submission status: Accepted

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

dp = [True]*(A[-1]+1)

ans = 0

for i in range(len(A)):
    if dp[A[i]]:
        if (i == len(A)-1) or (A[i] != A[i+1]):
            ans += 1
    try:
        k = 1
        while(True):
            dp[k*A[i]] = False
            k += 1
    except:
        pass

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

a.sort()

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

ans = 0

m = a[-1]

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and dp[x]:
        ans += 1
    for b in range(x, m + 1, x):
        dp[b] = False

if dp[a[-1]]:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    memo = [True] * (10 ** 6 + 1)
    ans = 0
    for k, v in sorted(Counter(a).items()):
        if v == 1 and memo[k]:
            ans += 1
        memo[k] = False
        for i in range(1, 10 ** 6 + 1):
            if 10 ** 6 + 1 <= i * k:
                break
            memo[i * k] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)] #M個の1のリスト
for a in S:
    if a in D:# かぶってたらフラグ除去
        X[a]=0
    for i in range(2*a,M+1,a): # aのN倍をフラグ除去
        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 = int(input())
a = sorted(map(int, input().split()))
m = a[-1]
dp = [0]*(m+1)

for i in a:
    dp[i] += 1
    if dp[i] > 1:
        continue
    else:
        for j in range(i*2, m+1, i):
            dp[j] += 1

print(sum([1 for i in a if dp[i] == 1]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

ans = 0
lim = max(A)+1
ok = [True]*lim
checked = [False]*lim

for a in sorted(A):
    if (not checked[a]) and ok[a]:
        checked[a] = True
        for j in range(a*2, lim, a):
            ok[j] = False

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    ans = 0
    mx = max(a) + 1
    dp = [0] * mx
    for i in a:
        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()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
lim = max(A)+1
cnt = [0]*lim
is_prime = [1]*lim

for x in A:
	cnt[x] += 1

for i in range(2, lim):
	if not is_prime[i]: continue
	for j in range(2*i, lim, i):
		is_prime[j] = 0
	for j in range(1, -(-lim//i)):
		cnt[i*j] += cnt[j]

ans = 0

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

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;
        continue

    times = 2
    while a[i] * times <= a[-1]:
        r = bisect.bisect_left(a, a[i] * times + 1)
        l = bisect.bisect_left(a, a[i] * times)
        if r != l:
            for idx in range(l, r):
                ok[idx] = 1
        times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Accepted

Solution code:
import sys

def Sieve2(N, AList, Bools, Max_A):
    N_NotDivisible = 0
    value = 0
    for i in range(N):
        if(AList[i]>value):
            value = AList[i]
            if(Bools[value]==True):
                N_NotDivisible += 1

            for j in range(2, Max_A//value+1, 1 ):
                Bools[j*value] = False
    #print(Mins)
    return N_NotDivisible


if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()
    Max = 0
    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
        Max = max(AList[i], Max)
    Bools = [False] * (Max+1)
    AList.sort()
    Dups = []
    for Num in range(N):
        value = AList[Num]
        Bools[value] = True
        if(Num < N-1 and AList[Num] == AList[Num+1]):
            Dups.append(value)
    for Num in range(len(Dups)):
        value = Dups[Num]
        Bools[value] = False


    N_NotDivisible= Sieve2(N, AList, Bools, Max)
    print(N_NotDivisible)

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i + 1] = 1
        continue
    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 2
        while a[i] * times < a[-1]:
            l = bisect.bisect_left(a, a[i] * times)
            r = bisect.bisect_right(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
# print(ok)
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
A.sort()
inf=10**6+1
t=[True for i in range(inf)]

ans=0
for j in range(N):
    if j+1<=N-1 and t[A[j]]:
        if A[j+1]!=A[j]:
            ans+=1
        else:
            t[A[j]]=False
        for numb in range(A[j],inf,A[j]):
            t[numb]=False
    elif j==N-1 and t[A[j]]:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

A.sort()

ans = 0
max_A = max(A)
ban = [0]*(max_A+1)
again = list()

last = 0
for i in range(N-1):
    if A[i] == A[i+1] and A[i] != last:
        again.append(A[i])
        last = A[i]
if N > 1 and A[N-1] == A[N-2] and A[N-1] != last:
    again.append(A[N-1])

for num in again:
    ban_num = num
    while ban_num <= max_A:
        ban[ban_num] = 1
        ban_num += num
 
for num in A:
    if ban[num] != 1:
        ans += 1
        ban_num = num
        while ban_num <= max_A:
            ban[ban_num] = 1
            ban_num += num

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*n
a=list(map(int,input().split()))
a=sorted(a)
maxnum=a[-1]
check=[True]*(maxnum+1)
before=0

for x in a:
    if (before==x):
        check[x]=False
        continue
    num=2
    while num*x<=maxnum:
        check[x*num]=False
        num+=1
    before=x

ans=0
for i in a:
    ans+=check[i]
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n = rl()
a=rl()
a.sort()
b=[0]*2*10**6
for i in a:
    if b[i]==0:
        b[i]=-1
        for j in range(2,10**6):
            if i*j>10**6:
                break
            b[i*j]+=1
        continue
    
    if b[i]==-1:
        b[i]=1
cnt = 0
for i in a:
    if b[i]==-1:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import math
import copy
import collections


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()
    AArry = LI()
    AArry.sort()
    count = 0
    li = [0 for _ in range(10**6+2)]

    for i, v in enumerate(AArry):
        a = v
        if li[a] == 1:
            count += 1
        if li[a] == 0:
            if i != N-1 and AArry[i+1] == a:
                count += 1

            for j in range(a, 10**6+2, a):
                li[j] = 1

    print(N-count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def d_not_divisible():
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]

    a_max = max(A)
    appear = [0] * (a_max + 1)
    for a in A:
        appear[a] += 1

    for j in range(1, a_max + 1):
        if appear[j] == 0:
            continue
        for k in range(j * 2, a_max + 1, j):
            appear[k] = 0
    return len([1 for a in appear if a == 1])

print(d_not_divisible())

Submission status: Accepted

Solution code:
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 :
        if m_a%i:
            a = m_a//i+1
        else:
            a = m_a//i
        for j in range(2, a):
            dp[j*i] +=100

print(dp.count(1))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    from collections import Counter
    c = Counter()
    ma = max(A)
    for a in A:
        for i in range(ma//a + 1):
            c[a*i] += 1

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

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # from random import randint
    # N = 2* (10**5)
    # A = [randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a.sort()
dp = [True] * a[-1]
ans = 0

for i,num in enumerate(a):
    if dp[num-1]:
        j= 2 * num
        while j <= a[-1]:
            dp[j-1] = False
            j += num
        if not i+1==len(a):
            if a[i]==a[i+1]:
                dp[num-1] = False

for k in a:
    if dp[k-1]:
        ans += 1

#print(dp)
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import sys
#from collections import deque
#import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n = xnxn()
if n == 1:
    print(1)
    sys.exit()

a = xnxn()

a.sort()

a_max = max(a)

dp = [1] * (a_max+1)


if a[0] != a[1]:
    count = 1
else:
    count = 0
for k in range(1, a_max // a[0]+1):
    dp[a[0] * k] = 0

for i in range(1, n):
    if dp[a[i]] == 1:
        for k in range(1, a_max // a[i]+1):
            dp[a[i] * k] = 0
        if i+1 < n and a[i] == a[i+1]:
            continue
        count += 1

print(count)

Submission status: Accepted

Solution code:

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


n = I()
a = LI()
cnt = [0] * ((10 ** 6) + 1)
for elem in a:
    cnt[elem] += 1

unique = []

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

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

a = list(set(a))

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

ans = 0

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

print(ans)

Submission status: Accepted

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

num = [1 for i in range(1000001)]
ans_list = [0 for i in range(1000001)]
for i in range(N):
    now = A[i]
    if ans_list[now] == 2:
        continue
    elif ans_list[now] == 1:
        ans_list[now] = 2
    else:
        ans_list[now] = 1
    for j in range(2*now, 1000001, now):
        num[j] = 0

count = 0
for i in range(N):
    now = A[i]
    if num[now] == 1 and ans_list[now] == 1:
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
m = a[-1]
b = [True]*(m+1)
for i in range(n):
    if i > 0 and a[i] == a[i-1]:
        continue
    for j in range(2, m//a[i]+1):
        b[j*a[i]] = False
ans = 0
for i in range(n):
    if 0 < i and a[i] == a[i-1]:
        continue
    if i < n-1 and a[i] == a[i+1]:
        continue
    if b[a[i]]:
        ans += 1
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 = list(map(int, input().split()))
ma = max(A)

X = [0] * (ma + 1)
Ans = [True] * (ma + 1)
ans = 0
A.sort()

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