Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
N = int(input())
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)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
aMax=a[-1]
isAns=[0]*(aMax+1) ## 1=ans 2=multiple or plural
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))

Submission status: Accepted

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

l=[0]*(10**6+1)
ans=0
#print(l)
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#D-Not Divisible
#pdf見た
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
a.sort()
m = a[-1]  # m = max(a)
s = [0]*(m+1)  # インデックスを合わせる
ans = 0
for i in a:
    if s[i] <= 100:  # 2以上なら計算しても意味ない
        for j in range(i, m+1, i):
            s[j] += 1  # sのiの倍数の部分を増やす
# ここで、s[i] == 1なら、自分自身で一度だけ+1されてることと同値なので他の数字と互いに素。
# 逆に2以上なら自分自身と自分の倍数で+1されてるから互いに素ではない。
for k in a:
    if s[k] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math
import sys
N = int(input())
A = list(map(int, input().split()))
#A.sort()
a_dic = {}
for n in range(N):
    if A[n] in a_dic:
        a_dic[A[n]] += 1
    else:
        a_dic[A[n]] = 1
#print(a_dic)
A = list(set(A))
A.sort()
#print(A)
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(j)
#print(dp)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

@njit
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))

Submission status: Accepted

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

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

#@njit
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

unique = []
for i in range(m + 1):
    if cnt[i] == 1:
        unique.append(i)
# print(unique)
# unique = list(set(A))

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# import collections


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

    A.sort()

    # sames = 0
    # C = collections.Counter(A)
    # for v in C.values():
    #     if v > 1:
    #         sames += 1

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

    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 dp[a - 1]:
    #         tmp_a = a * 2
    #         while tmp_a < a_max + 1:
    #             dp[tmp_a - 1] = False
    #             tmp_a += a

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

    # print(r - sames)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()

    # 愚直に行うとO(N^2)となる
    # エラトステネスの篩を真似ると、NlogNで済む
    # 同じ数字が存在している場合は、注意する

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

Submission status: Accepted

Solution code:
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())
	#b , c = tin()
	#s = 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
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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())
	#b , c = tin()
	#s = 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
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    adic={}
    for i in range(n):
        if a[i] in adic:
            adic[a[i]]+=1
        else:
            adic[a[i]]=1
    ans=0
    a=list(set(a))
    a.sort()
    maxa=max(a)
    dp=[True for i in range(maxa+1)]
    for i in a:
        if dp[i] and adic[i]==1:ans+=1
        j=i+i
        while j<=maxa:
            dp[j]=False
            j+=i
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
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:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)
for i in a:
  d[i] += 1

a.sort()
mx = max(a)

chk = [False for i in range(mx+1)]
cnt = 0
for i in range(n):
  if d[a[i]] >= 2:
    for j in range(a[i],mx+1,a[i]):
      chk[j] = True
    continue
  if chk[a[i]] == False:
    cnt += 1
  for j in range(a[i],mx+1,a[i]):
    chk[j] = True
print (cnt)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
A.sort()
lim = A[-1]+1
B = [0] * lim
U = list(set(A))
C = Counter(A)

for a in U:
    if C[a] > 1:
        B[a] = 1
    for i in range(a*2, lim, a):
        B[i] = 1

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
flag=[0]*N

ans=0
M=A[-1]
B=[0]*(M+1)
for i in A:
    B[i]+=1

for i in A:
    if B[i]==1:
        ans+=1
    for j in range(i,M+1,i):
        B[j]+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
max_a = a[-1]
is_True = [1]*(max_a + 1)
for i in a:
    if is_True[i]:
        for j in range(2*i, max_a + 1, i):
            is_True[j] = False
cnt = 0
from collections import Counter
c = Counter(a)
for i in a:
    if is_True[i] and c[i] == 1:
        cnt += 1
print(cnt)