Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
# 以下カンニング
n = int( input() )
a = list( map( int, input().split() ) )

max_a = max( a )

c = {} # c[ a_i ] = aに含まれるa_iの個数
d = {} # d[ a_i ] = aにa_iの約数( < a_i )があるか(bool)
for a_i in a:
    try:
        c[ a_i ] += 1
    except KeyError:
        c[ a_i ] = 1
        d[ a_i ] = False # 初期値

for a_i in a:
    if c[ a_i ] > 0:
        tmp = 2 * a_i
        while tmp <= max_a:
            d[ tmp ] = True
            tmp += a_i

ans = 0
for a_i in a:
    if c[ a_i ] == 1 and d[ a_i ] == False:
        ans += 1

print( ans )

Submission status: Accepted

Solution code:
import sys
import heapq
from collections import Counter
from math import sqrt

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
a_s.sort()
_max = max(a_s)
ct = Counter(a_s)
cnt = 0
ls = [False] * (10**6+1)
for a in a_s:
    if ls[a]:
        cnt += 1
        continue
    elif ct[a] > 1:
        cnt += 1
    for i in range(a, _max+1, a):
        if ls[i]:
            continue
        if i % a == 0:
            ls[i] = True

print(n - cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = sorted(list(map(int, input().split())))

# 探索範囲は数列aの最大値まで
max_a = a[-1]
b = [0] * (max_a + 1)
ans = set()
for i in a:
    if b[i] == 1:
        if i in ans:
            ans.remove(i)
        continue
    # 探索範囲内のiの倍数をチェック
    for j in range(i, max_a+1, i):
            b[j] = 1
    ans.add(i)

print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
Amax = A[-1]
dp = [1]*(Amax+1)
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:
    for q in range(Amax//p+1):
      dp[p*q] = 0
    if A[i] != A[i+1]: 
      ans += 1
if dp[Amax] == 1:
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

max_ = 10 ** 6 + 1
b = [True] * (max_ + 1)
data.sort()
c = Counter(data)

ans = 0
for d in data:
    if b[d]:
        for j in range(d, max_, d):
            b[j] = False
        # 複数存在
        if c[d] == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

max_ = 10 ** 6 + 1
b = [True] * (max_ + 1)
data.sort()
c = Counter(data)

ans = 0
for d in data:
    if b[d]:
        for j in range(d, max_, d):
            b[j] = False
        # 複数存在
        if c[d] > 1:
            continue
        else:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#10
#33 18 45 28 8 19 89 86 2 4

n = int(input().rstrip("\n"))
a = [int(_) for _ in input().rstrip("\n").split(" ")]
a.sort()
from collections import defaultdict

counter = defaultdict(int)

limit = 10 ** 6
for num in a:
  counter[num] += 1
  if counter[num] >= 2:
    continue
  current = num
  while current <= limit:
    current += num
    counter[current] += 1

answer = 0
for num in a:
  if counter[num] == 1:
    answer += 1

#print(counter)
print(answer)

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
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:
    d[i]=0
ans=0
for i in a:
  if d[i]==1:
    ans+=1
print(ans)

Submission status: Accepted

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

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

A = sorted(set(A))
t = [True] * (10 ** 6 + 1)
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]))

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    #N = 1のときなどcorner caseを確認！
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:
import numpy as np
from collections import Counter


n = int(input())
A = list(map(int, input().split()))
A.sort()
is_divisible = np.zeros(10**6+1, dtype=np.int64)


def update(num):
    nums = np.arange(num, 10**6+1, num)
    is_divisible[nums] = True

counter = Counter(A)
ans = 0
for a, count in counter.items():
    if count == 1 and not is_divisible[a]:
        ans += 1
        
    update(a)

print(ans)

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 1:
    print(1)
    sys.exit()
if n == 2:
    if a[0] == a[1]:
        print(0)
    elif a[1]%a[0] == 0:
        print(1)
    else:
        print(2)
    sys.exit()

b = []
pre = a[0]
if a[0] != a[1]:
    if pre == 1:
        print(1)
        sys.exit()
else:
    if pre == 1:
        print(0)
        sys.exit()

judge = [False for i in range(10**6+1)]
for num in a:
    judge[num] = True
for i in range(1,(10**6)):
    if judge[i]:
        for j in range(i*2,10**6+1,i):
            judge[j] = False
ans = 0
for i in range(1,10**6+1):
    if judge[i]:
        ans+=1
subans = 0
c = collections.Counter(a)
for k,v in c.items():
    if v > 1 and judge[k]:
        subans+=1
print(ans-subans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

n = int(readline())
a = np.array(read().split(), np.int32)

b = np.zeros(10**6 + 10, np.int32)
cnt = 0

for x in a:
    if b[x] > 1:
        continue
    b[::x] += 1

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

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
l = [True] * (10**6 + 1)
cnt = 0
for i in range(n):
  d = a[i]
  if l[d]:
    if i < n-1 and a[i] != a[i+1]:
      cnt += 1
    elif i == n-1:
      cnt += 1
    for j in range(d, 10**6 + 1, d):
      l[j] = False
print(cnt)

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import Counter


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    max = A[-1]
    count = Counter(A)
    S = list(count.keys())
    C = []
    for s in S:
        if count[s] > 1:
            continue
        else:
            C.append(s)

    is_prime = np.ones(max + 1, np.bool)
    for a in A:
        if is_prime[a]:
            is_prime[a * 2 :: a] = 0
        else:
            continue
    answer = 0
    for c in C:
        if is_prime[c]:
            answer += 1
        else:
            continue
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

a=[0]*((10**6)+1)
for i in L:
    a[i]+=1

uni=[]
for i in range((10**6)+1):
    if a[i]==1:
        uni.append(i)
a=[0]*((10**6)+1)
L=list(set(L))
for i in L:
    for m in range(i*2,(10**6)+1,i):
        a[m]=1
ans=0
for i in uni:
    if a[i]==0:
        ans+=1 
print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
S = set()
D = set()
for a in A:
    if a in S:
        D.add(a)
    else:
        S.add(a)
M = max(S)
A = [0]*(M+1)
for s in S:
    if s in D:
        A[s] += 1
    for i in range(2*s,M+1,s):
        A[i]+=1
count = 0
for s in S:
    if A[s]==0:
        count += 1
print(count)

Submission status: Accepted

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

temp = [0] * (10 ** 6 + 1)
for i in A:
    j = i
    while j <= A[-1]:
        temp[j] += 1
        j += i

result = 0
for i in A:
    if temp[i] == 1:
        result += 1

print(result)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = Counter(A)
    c = sorted(c.items(), key=lambda x: x[0])
    ans = 0
    isOK = [True] * (10 ** 6 + 1)
    for k, v in c:
        if not isOK[k]:
            continue

        if v > 1:
            for i in range(k, 10 ** 6 + 1, k):
                isOK[i] = False
            continue

        ans += 1
        for i in range(2 * k, 10 ** 6 + 1, k):
            isOK[i] = False

    print(ans)


if __name__ == "__main__":
    main()

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:
    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()))
B=[0]*(max(A)+1)
count=0
for i in A:
    for j in range(0,len(B),i):
        B[j]+=1
for k in A:
    if B[k]==1:
        count+=1
print(count)

Submission status: Accepted

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
ma=A[-1]
is_prime = [True] * (ma + 1)
for i in A:
    if not is_prime[i]:
        continue
    for j in range(i * 2, ma + 1, i):
        is_prime[j] = False
k=[i for i in range(ma + 1) if is_prime[i]]
N=[]
if len(A)==1:
    print(1)
else:
    if A[0] !=A[1]:
        N.append(A[0])
    for i in range(1,len(A)-1):
        if A[i-1]!=A[i] and A[i]!=A[i+1]:
            N.append(A[i])
    if A[len(A)-2] != A[len(A)-1]:
        N.append(A[len(A)-1])
    s=set(k) & set(N)
    print(len(s))

Submission status: Accepted

Solution code:
from collections import Counter

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

MAX = 10 ** 6 + 10
multiples = [0] * MAX

for a in list(set(A)):
    for j in range(a * 2, MAX, a):
        multiples[j] = 1

d = Counter(A)
dup = [k for k, v in d.items() if v > 1]
for i in dup:
    multiples[i] = 1

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] > 0:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
max_val=max(a)

done=[0 for i in range(max_val)]
cnt=0
ans=0

for i in a:

  if 1<=done[i-1]:
    done[i-1]+=1
    continue

  done[i-1]+=1
  cnt=1
  while(i*cnt<=max_val):
    cnt+=1
    if cnt*i<=max_val:
      done[cnt*i-1]+=1

for i in a:
  if done[i-1]==1:
      ans+=1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
m=max(l)
check=[0]*(m+1)

for ll in l:
  for i in range(ll,m+1,ll):
    check[i]+=2
  check[ll]-=1
print(check.count(1))

Submission status: Accepted

Solution code:
import sys

n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
max_val=max(a)
dp=[True for i in range(max_val)]
done=[0 for i in range(max_val)]
cnt=0
ans=0

for i in a:

  if 1<=done[i-1]:
    done[i-1]+=1
    continue

  done[i-1]+=1
  cnt=1
  while(i*cnt<=max_val):
    cnt+=1
    if cnt*i<=max_val:
      done[cnt*i-1]+=1

for i in a:
  if done[i-1]==1:
      ans+=1

print(ans)

Submission status: Accepted

Solution code:
N = 5
ARR = [24, 11, 8, 3, 16]

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

def calculate(n, arr):
    maxValue = max(arr) + 1
    maxValue = 1000006
    krr = [0 for i in range(maxValue)]

    for start in arr:
        if krr[start] > 0:
            krr[start] = 2
            continue

        for i in range(start, maxValue, start):
            krr[i] += 1

    result = 0
    for ar in arr:
        if krr[ar] == 1:
            result = result + 1

    print(result)


calculate(N, ARR)

Submission status: Accepted

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

C = {a:0 for a in A}
D = {a:0 for a in A}
for a in A:
    C[a] += 1
for a in A:
    if C[a] > 0:
        t = 2
        while a*t <= maxA:
            D[a*t] = 1
            t += 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())

ma=1001001
nums=[0]*ma

for i in a:
    nums[i]+=1
    if nums[i]==1: # 一回だけ出てきた場合
        for j in range(i+i,ma,i):
            nums[j]+=2
            
ans=nums.count(1)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    dp = [True] * (10 ** 6 + 1)
    a.sort()
    ans = 0
    d = defaultdict(int)
    for i in a:
        if d[i]:
            d[i] = 0
            ans -= 1
        if dp[i]:
            d[i] = 1
            ans += 1
            dp[i] = False

            for j in range(i * 2, 10 ** 6 + 1, i):
                dp[j] = False
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:14:26 2020

@author: NEC-PCuser
"""

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

a = [0] * (10 ** 6)

for i in A:
    first_flg = True
    for j in range(i, 10 ** 6 + 1, i):
        if first_flg == True and a[j - 1] != 0:
            a[j - 1] += 1
            break
        a[j - 1] += 1
        first_flg = False


count = 0
for i in A:
    if a[i - 1] == 1:
        count+=1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      ans[j] += 2
print(ans.count(1))

Submission status: Accepted

Solution code:
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
a_set = set(a_list)
m = max(a_list)
for key, count in sorted_dict:
    if  key in a_set:
        j = key * 2
        while j <= m:
            a_set.discard(j)
            j += key
    if count > 1:
        a_set.discard(key)

print(len(a_set))

Submission status: Accepted

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        for j in range(i, m, i):
            l[j] += 2
        l[i] -= 1

    ans = sum(l[i] == 1 for i in a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, *a = map(int, open(0).read().split())
    if n == 1:
        print(1)
        return

    m = max(a) + 1
    l = [0] * m
    for i in a:
        for j in range(i, m, i):
            l[j] += 2
        l[i] -= 1

    ans = l.count(1)
    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 i in a:
    cnt[i] += 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 i in a:
    for j in range(i*2, 10**6 + 1, i):
        cnt[j] = 1
    
ans = 0

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

Submission status: Accepted

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

amax = max(A)
sieve = [False] * (amax+1)
exist = [0] * (amax+1)

for a in A:
    if exist[a] > 0:
        exist[a] += 1
        continue
    exist[a] += 1
    for i in range(a*2, amax+1, a):
        sieve[i] = True

ans = 0
for a in A:
    if not sieve[a] and exist[a] == 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()

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

    ans = set()
    for a in A:
        if B[a] == 1:
            if a in ans:
                ans.remove(a)
            continue
        for aa in range(a, ma + 1, a):
            B[aa] = 1

        ans.add(a)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
max = int(10e5+1)
l = [0] * (max+1)
for n in A:
    if l[n] != 0:
        l[n] = 2
        continue
    for j in range(n, max+1, n):
        l[j] += 1
for n in A:
    if l[n] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

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

a.sort()
b = [0 for _ in range(a[-1])]
c = 0
for i in a:
    x = i-1
    while len(b) > x:
        b[x] += 1
        x += i 
for i in a:
    if b[i-1] == 1:
        c += 1
print(c)

Submission status: Accepted

Solution code:
M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in sorted(l):
  a[i]+=1
  if a[i]==1:
    for j in range(2*i,M,i):a[j]+=9
print(a.count(1))

Submission status: Accepted

Solution code:
M=10**7
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in sorted(l):
  a[i]+=1
  if a[i]==1:
    for j in range(2*i,M,i):a[j]+=9
print(a.count(1))

Submission status: Accepted

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

d = {}
for ai in a:
  if ai in d:
    d[ai] += 1
  else:
    d[ai] = 1
d = sorted(d.items())
#print(d)

e = [True for _ in range(maxa+1)]
for ai,c in d:
  if c > 1:
    e[ai] = False
  for i in range(2,maxa//ai+1):
    e[ai*i] = False

ans = 0
for ai,_ in d:
  if e[ai]:
    ans += 1
print(ans)

Submission status: Accepted

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

from collections import Counter
c=Counter(a)

max_a=max(a)
bls=[0]*(max_a+1)
for a_i in a:
    for j in range(a_i, max_a+1, a_i):
        bls[j]+=1
ans=0
for a_i in a:
    if bls[a_i]==1 and c[a_i]==1:
        ans+=1
print(ans)

Submission status: Accepted

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

A.sort()

m_a = max(A)
check = [0]*(m_a+2)

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

print(check.count(1))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

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

A.sort()
table = [0 for i in range(10**6 + 1)] # 約数のテーブル

cc = collections.Counter(A)


cnt = 0
for a in A:
    if table[a] == 0:
        for i in range(10 ** 6):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1
        if cc[a] == 1:
            cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
nux = A[-1]+1
ans = 0
table = [True]*nux
for i, s in enumerate(A):
    if table[s] == False:
        continue
    if i == n-1:
        ans += 1
    elif A[i+1] != s:
        ans += 1
    b = 1
    while b*s < nux:
        table[b*s] = False
        b += 1
print(ans)

Submission status: Accepted

Solution code:

N=int(input())
A=list(map(int,input().split()))
dp=[False]*(10**6+1)
A.sort()
ans=0
before_ = -1
for i in A:
  if dp[i]==False:
    for j in range(2*i,10**6+1,i):
      dp[j]=True
  if before_ == i:
      dp[i]=True
  before_=i

for i in A:
  if dp[i]==False:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    D = Counter(A)

    dup = set()
    for k, v in D.items():
        if v > 1:
            dup.add(k)

    judge = [False] * (A[-1] + 1)
    res = 0
    for a in A:
        if judge[a]:
            continue
        else:
            if a not in dup:
                res += 1
            for i in range(a, A[-1] + 1, a):
                judge[i] = True

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_set = set(a_list)
m = max(a_list)
a_list.sort()
 
pre_a = 0
for a in a_list:
    if a == pre_a:
        a_set.discard(a)
    if a in a_set:
        j = a * 2
        while j <= m:
            a_set.discard(j)
            j += a
    pre_a = a

print(len(a_set))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
nux = max(A)
B = set(A)
A.sort()
ans = 0
table = [True]*(nux+1)
for ii, s in enumerate(A):
    if table[s] == False:
        continue
    if ii == n-1:
        ans += 1
    elif A[ii+1] != s:
        ans += 1
    i = 1
    while i*s <= nux:
        table[i*s] = False
        i += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
a.sort()
A = max(a)
b = [0]*A
for i in range(N):
  if b[a[i]-1] == 0:
    for j in range(a[i], A+1, a[i]):
      b[j-1] += 1
  elif b[a[i]-1] == 1:
      b[a[i]-1] += 1
n = 0      
for i in range(N):
  if b[a[i]-1] == 1:
    n += 1
print(n)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
# M = max(A)+1
M = 10**6+1
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] != 0:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
m=a[-1]
b=[1]*(m+1)
b[0]=0
p=0
q=1
r=0
for c in range(m+n):
    if p>=n or q>m:
        break
    if a[p]>q:
        if r!=q:
            b[q]=0
        q+=1
        continue
    elif a[p]<q:
        p+=1
        continue
    else:
        p+=1
        if r==q:
            b[q]=0
            continue
        for d in range(2,m//q+1):
            b[d*q]=0
        r=q
print(sum(b))

Submission status: Accepted

Solution code:
def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A)+1
cnt = [0]*M
ans = 0
for a in A:
    if cnt[a] != 0:
        cnt[a] = 2
    else:
        for i in range(a, M, a):
            cnt[i] += 1
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
As = sorted(map(int, input().split()))

flgs = np.full(10**6+1, False)
flgs[As] = True

for i, A in enumerate(As):
    if flgs[A] == True:
        flgs[::A] = False
        if i+1 == len(As) or As[i+1] != A:
            flgs[A] = True

print(np.count_nonzero(flgs))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
ans=0
for i in A:
  if dp[i]==0:
    for j in range(i,10**6+1,i):
      dp[j]+=1
  else:
    dp[i]+=1
for i in A:
  if dp[i]==1:
    ans+=1
print(ans)

Submission status: Accepted

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

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

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

print(res)

Submission status: Accepted

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

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

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

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

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

N = I()
A = LI()

A.sort()

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

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

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

print(ans)

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
#print(l)
for i in a:
    if l[i]==1:
        ans+=1

print(ans)

Submission status: Accepted

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

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

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

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

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

ans=0

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

print(ans)

Submission status: Accepted

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

a.sort()
a_max = a[-1] + 1   # aの最大値
lst = [0] * a_max   # a_max個のリストを生成

for x in a:
    lst[x] += 1                         # リストの該当の数字に1追加 
    if lst[x] == 1:                     # まだ他の数値の倍数でなければ、リストへ2倍、3倍…の数字を1追加していく
        for i in range(x*2, a_max, x):
            lst[i] += 1

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

Submission status: Accepted

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

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

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


print(ans)