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:
#170D
def main():
    import sys
    from collections import Counter
    import random
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    #A = [random.randint(1, 10**6+1) for _ in range(2*(10**5))]
    judge = [0 for _ in range(10**6+1)]
    A.sort()
    B = Counter(A)
    for a in A:
        judge[a] =1
    for a in A:
        if judge[a] ==1:
            if B[a] >=2:
                judge[a] = 0
            for i in range(2*a, 10**6+1, a):
                judge[i] = 0
                
    print(judge.count(1))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  D=[0]*(10**6+1)
  A=sorted(map(int,input().split()))
  m=max(A)+1

  for a in A:
    if D[a]==0:
      D[a]=1
      for i in range(2*a,m,a):
        D[i]=-1
    else:
      D[a]=-1

  print(D.count(1))

main()

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  D=[0]*(10**6+1)

  for a in sorted(map(int,input().split())):
    if D[a]==0:
      D[a]=1
      for i in range(2*a,10**6+1,a):
        D[i]=-1
    else:
      D[a]=-1

  print(D.count(1))

main()

Submission status: Accepted

Solution code:
n = int(input())
list_P = list(map(int, input().split()))
d = {}
q = max(list_P)

for p in list_P:
    d.setdefault(p, 0)
    d[p] += 1

list_P = set(list_P)
list_Ans = [True]*(q+1)

for p in list_P:
    if d[p] > 1:
        list_Ans[p] = False

    for i in range(2*p, q + 1, p):
        list_Ans[i] = False

ans = 0

for p in list_P:
    if list_Ans[p]:
        ans += 1

print(ans)

Submission status: Accepted

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

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

for i in range(len(A)):
    if i<n-1 and A[i]==A[i+1]:
        box[A[i]]=False
    k=2
    while A[i]*k<len(box):
        box[A[i]*k]=False
        k+=1

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [1]*(10**6+1)
for i in range(n):
    if i + 1 < n and a[i] == a[i + 1]:
        b[a[i]] = 0
        continue
    for x in range(2*a[i], 10**6+1, a[i]):
        b[x] = 0
print(sum(b[x] for x in a))

Submission status: Accepted

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

mx=max(A)
f=[True]*(mx+1)
chk=[0]*(mx+1)

for a in A:
    chk[a]+=1

for a in A:
    cnt=2
    while a*cnt<=mx:
        f[a*cnt]=False
        cnt+=1
ans=0
for a in A:
    if f[a]==True and chk[a]<=1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


N = int(input())
A = list(map(int, input().split()))
A.sort()
countA = Counter(A)
maxA = A[-1]
# if countA[1] == 1:
#     print(1)
#     exit()

ef = [True]*(maxA+1)
count = 0
prev = -1
for num in A:
    if num == prev:
        continue
    if ef[num] and countA[num] == 1:
        count += 1

    b = 2*num
    while b <= maxA:
        ef[b] = False
        b += num

    prev = num

print(count)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
A = list(set(a))
A.sort()
amax = A[-1]
sieve = [1]*(amax+1)
ans = []

for i in A:
  for j in range(2,amax//i + 1):
    sieve[i*j] = 0

for i in A:
  if sieve[i] == 1:
    ans.append(i)

c = Counter(a)
ansl =len(ans)

for k,v in c.items():
  if sieve[k] == 1 and v >= 2:
    ansl -= 1
    
print(ansl)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split(" ")))
A.sort()
sieve = [True for i in range(A[-1] + 1)]
done = set()
ans = 0

for i, a in enumerate(A):
    if sieve[a] == True:
        num = 1
        while a*num <= A[-1]:
            sieve[num*a] = False
            num += 1
        if i ==len(A)-1:
            ans +=1
        elif (i < len(A) -1) and (A[i] != A[i+1]):
            ans +=1
        

print(ans)

Submission status: Accepted

Solution code:
n = input()
*A, = map(int, input().split())
max_A = max(A)
count = {a:0 for a in A}
for a in A:
    count[a] += 1
is_OK = {a:True for a in A}
for a in A:
    i = 2
    if not is_OK[a]:
        continue
    while a * i < max_A + 1:
        is_OK[a * i] = False
        i += 1
ans = 0
for a in A:
    if count[a] == 1 and is_OK[a]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0
cnt_li = [0]*(10**6+1)

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

for l in li:
    for x in range(2,10**7):
        if x*l > (10**6):
            break
        else:
            cnt_li[x*l] += 1


while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    if cnt_li[ba] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
_,*a = map(int,open(0).read().split())
a.sort()
ans = 0
#M = 30
M = 10**6 + 1
l = [0] * (M)
ans = 0
for i in range(len(a)):
    if l[a[i]] == 0:
        l[a[i]] = 2
        ans += 1
        for x in range(a[i]*2, M, a[i]):
            l[x] = 1
    elif l[a[i]] == 2:
        ans -= 1
        l[a[i]] -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline


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

    M = A[-1]
    flg = [0] * (M + 1)
    res = 0

    for a in A:
        if flg[a] == 0:
            res += 1
        if flg[a] == 2:
            res -= 1
            flg[a] = 1
        if flg[a] > 0:
            continue
        flg[a] = 2
        for i in range(2, 10**6):
            if a * i > M:
                break
            flg[a*i] = 1
    
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A_max = max(A)
#A = sorted(A)
dp = [True for i in range(A_max)]
counter = [0 for i in range(A_max)]
# count
for a in A:
    counter[a - 1] += 1

for a in A:
    multiple = a + a
    while (multiple <= A_max):
        dp[multiple - 1] = False
        multiple = multiple + a
ans = 0

for i in A:
    if dp[i - 1] and counter[i - 1] <= 1:
        ans += 1

print(ans)

Submission status: Accepted

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

table = [0] * (a[n - 1] + 1)
#table
for i in range(n):
    p = a[i]
    for j in range(2 * p, a[n - 1] + 1, p):
        #print(j)
        table[j] = 1
        
from collections import Counter
cnt = Counter(a)
ans = 0
for i in range(n):
    
    if cnt[a[i]] != 1:
        continue
    
    if table[a[i]] != 1:
        ans += 1
print(ans)

Submission status: Accepted

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

cnt = [0] * (a[-1] + 1)
for i in a:
    cnt[i] += 1
for i in set(a):
    if cnt[i] >= 1:
        for j in range(i * 2, a[-1] + 1, i):
            cnt[j] = 0
print(cnt.count(1))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

Amx = max(A)
A.sort()
As = set(A)
# DP
ca = Counter(A)
ans = 0
dp = [True] * (Amx + 1)
for a in A:
    if ca[a] <= 1 and dp[a]:
        ans += 1
    k = 1
    while k * a <= Amx:
        dp[k * a] = False
        k += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
*a, = sorted(map(int, input().split()))
a_max = a[n-1]
dp = [True] * a_max
ans = 0
recent = 0

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

for i in a:
    if recent == i:
        ans -= 1
        recent = 0
    if dp[i-1] == False:
        continue
    else:
        for j in range(i, a_max+1, i):
            dp[j-1] = False
        ans += 1
        recent = i

print(ans)

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

#個数が1個のリスト
unique = []

for i in range((10**6) + 1):
    #iが複数ないならばリストに追加
    if cnt[i] == 1:
        unique.append(i)

#cntを初期化
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
#それぞれの数の個数が1個しかないリストを回す(重複対策してるため)
for elem in unique:
    if cnt[elem] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
ma=max(a)
b=[0]*(ma+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,ma+1,i):
        b[j]+=1
ans=0
for i in a:
    if b[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
import sys
from bisect import *
from math import floor,sqrt,ceil,factorial as F,gcd,pi,log
from itertools import chain,combinations,permutations,accumulate
from collections import Counter,defaultdict,OrderedDict,deque
from functools import cmp_to_key,reduce
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
mod = 1000000007
ch = "abcdefghijklmnopqrstuvwxyz"
lcm = lambda a,b : (a*b)//gcd(a,b)
setbit = lambda x : bin(x)[2:].count("1")

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def solve():
    nn = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    tra = Counter(a)
    s = dict()
    n = len(a)
    max_ele = INT_MIN
    for i in range(n):
        s[a[i]] = 1
        max_ele = max(max_ele,a[i])

    res = dict()
    for i in range(n):
        if a[i] !=0 :
            for j in range(a[i]*2,max_ele+1,a[i]):
                if j in s.keys():
                    res[j]  = 1
    # print(res)
    c =0
    for k,v in tra.items():
        if k not in res:
            if v == 1:
                c += 1


    print(c)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


if __name__ == '__main__':
    # try:
    #     sys.stdin = open("input.txt","r")
    # except :
    #     pass
    solve()

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
m=max(a)
b=[1]*m
c=[0]*m
for i in a:
  c[i-1]+=1
  if b[i-1]:
    for j in range(i*2-1,m,i):
      b[j]=0
x=0
for i in range(m):
  if b[i] and c[i]==1:
    x+=1
print(x)

Submission status: Accepted

Solution code:
# coding: utf-8

# 13:42- kaisetsu and try again
# -14:03 giveup (WA*6) -> testcase


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

    M = 10**6
    is_ans_flag = [0] * (M+1)
    n_appeared_in_A = [0] * (M+1)
    for a in A:
        n_appeared_in_A[a] += 1
        is_ans_flag[a] = 1

    for a in A:
        if n_appeared_in_A[a] == -1:
            continue

        if n_appeared_in_A[a] >= 2:
            is_ans_flag[a] = 0

        for i in range(2, M+1):
            if a*i > M:
                break
            is_ans_flag[a*i] = 0

        n_appeared_in_A[a] = -1

    return sum(is_ans_flag)


print(main())

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
ma=1001001
nums=[0]*ma

for q in a:
  nums[q]+=1
  if nums[q]==1:
    for j in range(2*q,ma,q):
      nums[j]+=2

cnt=0
for elem in nums:
  if elem==1:
    cnt+=1
    
print(cnt)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

N=int(input().rstrip())
a=[int(i) for i in input().split()]
l=max(a)+1
cnt=[0]*l
for i in a:
    for j in range(i,l,i):cnt[j]+=1

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

Submission status: Accepted

Solution code:
import collections
N = int(input()) 
A = sorted(list(map(int, input().split())))
unique_count = collections.Counter(A)
A_count1 = []
A_unique = list(set(A))
baisu = [0]*(10**6+1)

for k,v in unique_count.items():
    if v == 1: A_count1.append(k)

for a_unique in A_unique:
    for i in range(a_unique*2,10**6+1,a_unique):
        baisu[i] = 1

ans = 0

for a_count1 in A_count1:
    if baisu[a_count1]==0: ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
  ## IMPORT MODULE
  #import sys

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n = 5
    A = [24, 11, 8, 3, 16]

  else:
    ##INPUT 
    n = int(input())
    A = list(map(int, input().split()))

  ## SUBMITION CODES HERE
  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)
  
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():
    N, *A = map(int, read().split())

    t = Counter(A)
    A.sort()
    table = [True] * (A[-1] + 1)
    n = len(table)

    seen = set()
    for a in A:
        if a in seen:
            continue
        for i in range(2*a, n, a):
            table[i] = False
        seen.add(a)

    ans = 0
    for k, v in t.items():
        if v > 1:
            continue
        else:
            if table[k]:
                ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

num_array = np.zeros(max(a_list)+1)
for a in a_list:
    num_array[a::a] += 1
    
count = 0
for a in a_list:
  if num_array[a] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
a.sort()
dp=[True]*(m+1)
h=dict()
for i in a:
    if i not in h:
        h[i]=1
    else:
        h[i]+=1
    j=2
    while j*i<=m:
        dp[i*j]=False
        j+=1
ans=0
for i in a:
    if dp[i]==True and h[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
max_=10**6+1
ans=0

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

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

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:
import sys
from collections import Counter
input = lambda: sys.stdin.readline().rstrip()

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
a = sorted(list(set(a)))
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import collections
import math
"""
#n = int(input())
#A = [int(i) for i in input().split()]
n = 10**5
A = [int(i)+1 for i in range(10**5,0,-1)]
A.sort()
ans = 0
ans_list = []
kaburi = {}
for i in A:
    Flag = True
    for j in ans_list:
        if i==j:
            kaburi[i]=True
            Flag = False
            break
        if i%j==0:
            Flag = False
            break
    if Flag:
        ans_list.append(i)
        ans += 1
print(ans-len(kaburi))
"""


n = int(input())
A = [int(i) for i in input().split()]
A.sort()
Max = max(A)
cnt_dict = collections.Counter(A)
#Dict[i]はi未満の約数がAに存在しなければTrue
Dict = {a:True for a in A}
for a in A:
    times = 2
    while a*times<=Max:
        Dict[a*times]=False
        times +=1
ans = 0
for a in A:
    if cnt_dict[a]==1 and Dict[a]:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import collections
import math
"""
#n = int(input())
#A = [int(i) for i in input().split()]
n = 10**5
A = [int(i)+1 for i in range(10**5,0,-1)]
A.sort()
ans = 0
ans_list = []
kaburi = {}
for i in A:
    Flag = True
    for j in ans_list:
        if i==j:
            kaburi[i]=True
            Flag = False
            break
        if i%j==0:
            Flag = False
            break
    if Flag:
        ans_list.append(i)
        ans += 1
print(ans-len(kaburi))
"""


n = int(input())
A = [int(i) for i in input().split()]
Max = max(A)
cnt_dict = collections.Counter(A)
#Dict[i]はi未満の約数がAに存在しなければTrue
Dict = {a:True for a in A}
for a in A:
    times = 2
    while a*times<=Max:
        Dict[a*times]=False
        times +=1
ans = 0
for a in A:
    if cnt_dict[a]==1 and Dict[a]:
        ans +=1
print(ans)

Submission status: Accepted

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

# 参考：https://qiita.com/HUVEC/items/97739696ab51cacd10f2
# エラトステネスの篩の原理を基に求める

A.sort()
Amax = max(A)

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
max_=10**6+1
ans=0

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

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

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:
# https://qiita.com/HUVEC/items/97739696ab51cacd10f2
from sys import stdin

def main():
    from collections import defaultdict
    input = stdin.readline

    n = int(input())
    a = sorted(list(map(int, input().split())))
    p = defaultdict(int)
    for x in a:
        p[x] += 1
    q = a[-1] + 1
    f = [True] * (q)
    for k, v in p.items():
        if v > 1:
            f[k] = False
        for i in range(k + k, q, k):
            f[i] = False
    print(sum(1 for x in a if f[x]))
main()

Submission status: Accepted

Solution code:
# https://qiita.com/HUVEC/items/97739696ab51cacd10f2
N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(ans)

Submission status: Accepted

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

def main():
    n = int(input())
    a = sorted([int(i) for i in input().split()])
    cnt_list = collections.Counter(a)
    search_list = [0] * (a[-1]+1)
    ans = 0
    for num, cnt in cnt_list.items():
        search_list[num] = cnt
    for i in a:
        if search_list[i] == 1:
            ans += 1
        for j in range(i, a[-1]+1, i):
            search_list[j] = 0
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[0]*M
for i in A:
    if cnt[i]!=0:
        cnt[i]=2
        continue
    for j in range(i,M,i):
        cnt[j]+=1
ans=0
for i in A:
    if cnt[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, A: "List[int]"):
    max_a = max(A)
    arr = [0] * (max_a + 1)
    for a in A:
        arr[a] += 1

    counter = 0
    for x in range(1,max_a+1):
        if arr[x] == 1:
            counter += 1
        if arr[x]:
            for j in range(x*2,max_a+1,x):
                arr[j] = 0
    print(counter)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
e=[1]*(10**6+1)
from collections import Counter
d=Counter(a)
ans=0
for i in a:
    if d[i]==1 and e[i]==1:
        ans+=1
    if e[i]==1:
        for j in range(i,10**6+1,i):
            e[j]=0
print(ans)

Submission status: Accepted

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    lim = max(a) + 1
    tmp = [0] * (lim)
    # set_a = list(set(a))
    # set_a.sort()
    a.sort()

    for aa in a:
        if tmp[aa] == 0:
            for j in range(aa,lim,aa):

                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    lim = max(a) + 1
    tmp = [0] * (lim)
    # set_a = list(set(a))
    # set_a.sort()
    a.sort()

    for aa in a:
        if tmp[aa] == 0:
            for j in range(lim):
                if aa * j > lim-1:
                    break
                tmp[aa*j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)

Submission status: Accepted

Solution code:
M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))

cnt = [0] * M
for i in A:
    if(cnt[i] >= 2):
        continue
    for j in range(i, M, i):
        cnt[j] += 1
ans = 0
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def solve(n, a):
    ub = max(a) + 1
    a = sorted(a)
    matched = [False] * ub
    for x in a:
        matched[x] = True
    for x in a:
        if matched[x]:
            for y in range(2*x, ub, x):
                matched[y] = False
    for i in range(n-1):
        if a[i] == a[i+1]:
            matched[a[i]] = False
    return sum(matched)

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

Submission status: Accepted

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


N = 4
ARR = [5, 5, 5, 5]


N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):

    prr = [0 for i in range(2000005)]

    for i in range(n):
        start = arr[i]
        #
        if prr[start] > 0:
            prr[start] = 2
            continue

        for j in range(start, 2000005, start):
            prr[j] = prr[j] + 1


    result = 0
    for i in range(n):
        start = arr[i]
        if prr[start] == 1:
            result += 1


    print(result)

calculate(N, ARR)

Submission status: Accepted

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

counts = [0 for i in range(Amax+1)]

for a in A:
    counts[a] += 1

count = 0
for i in range(1, Amax+1):
    if counts[i] == 1:
        count += 1
    if counts[i]:
        for j in range(i*2, Amax+1, i):
            counts[j] = 0
print(count)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)
 
b = sorted(set(a))
 
for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 10:
            break
        prime[num] = False
        num += i
 
ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)
 
b = sorted(set(a))
 
for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i
 
ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


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

    ans = 0
    m = max(A)
    zeta = [0]*(m+1)
    for a in A:
        zeta[a] += 1

    # 素数の列挙
    primes = eratosthenes_sieve(m)
    # ゼータ変換
    for p in primes:
        for i in range(1, m//p+1):
            zeta[p*i] += zeta[i]

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

    # print(zeta)
    # for a in A:
    # print(a, zeta[a])

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
ans = 0
A = list(map(int,input().rstrip().split(" ")))
A.sort()
A2 = [True for i in range(A[-1] + 1)]
for i in range(len(A)):
    k = A[i] * 2
    if A2[A[i]]:
        if i != 0 and A[i-1] == A[i]:
            A2[A[i]] = False
        while(k < len(A2)):
            A2[k] = False
            k += A[i]
for i in A:
    if A2[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''
5
24 11 8 3 16
'''

def solve(l):
	n = len(l)
	l.sort()
	maxx,ans = max(l),0
	cancel,p = [0]*(maxx+1),[0]*(maxx+1)
	for i in l:
		p[i] += 1
	for i in l:
		for j in range(2*i,maxx+1,i):
			cancel[j] = 1
	for i in l:
		if(p[i] == 1 and not cancel[i]):
			ans += 1
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

Submission status: Accepted

Solution code:
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Submission status: Accepted

Solution code:
N = 1000001
a = [0]* 1000001
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Submission status: Accepted

Solution code:
a = [0]* 1000001
m = 0
input()
for x in map(int, input().split()):
  m = max(m, x)
  a[x] += 1
m += 1
for i in range(1, m):
  if a[i]:
    for j in range(i + i, m, i):
      a[j] = 0
print(a[:m].count(1))

Submission status: Accepted

Solution code:
a = [0]* 1000001
m = 0
input()
for x in map(int, input().split()):
  m = max(m, x)
  a[x] += 1
m += 1
for i in range(1, m):
  if a[i]:
    for j in range(i + i, m, i):
      a[j] = 0
print(a.count(1))