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:
import os, sys, atexit
from io import BytesIO, StringIO
 
input = BytesIO(os.read(0, os.fstat(0).st_size)).readline
_OUTPUT_BUFFER = StringIO()
sys.stdout = _OUTPUT_BUFFER
 
@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
n = int(input())
l = list(map(int, input().split()))
l.sort()
vis = [0] * 1000004
for i in l: vis[i] -= -1
for i in range(n):
    tmp = l[i]
    while tmp <= l[n - 1]:
        if vis[tmp]:
            if tmp == l[i]:
                if vis[tmp] > 1: vis[tmp] = 0
            else:
                vis[tmp] = 0
        tmp += l[i]
ans = 0
for i in vis: ans += i
print(ans)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A_list = [int(e) for e in input().split()]

#import random
#N = 2 * 10**5
#A_list = [random.randrange(1,10**6) for _ in range(N+1)]

A_counter = collections.Counter(A_list)

max_A = max(A_list)

A_list.sort(reverse=False)
OK_set = set(A_list)

ans = list()

#入力のうち、小さい方から倍数を生成。その倍数に引っかかったらアウト

for i in range(0,N):
    A = A_list[i]

    if A*2 <= max_A:
        multiple_set = {A*j for j in range(2,1+max_A//A)}
        #print(multiple_set)
        OK_set -= multiple_set

    if A_counter[A] != 1:
        OK_set -= {A}
    
    #print(OK_set)

print(len(OK_set))

Submission status: Accepted

Solution code:
visited=[False]*(10**6+1)

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

if N>=2 and A[1]==1:
  print(0)
  exit()
if A[0]==1 or N == 1:
  print(1)
  exit()
  
ans=0
for i in range(N):
  if visited[A[i]]:
    continue
  if i < N-1 and A[i]==A[i+1]:
    index = 1
    while A[i]*index<=10**6:
      visited[A[i]*index]=True
      index+=1
    continue
  ans+=1
  index=1
  while A[i]*index<=10**6:
    visited[A[i]*index]=True
    index+=1
    
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a.sort()
num = 10**6+10
input_list = defaultdict(int)
sqrt = math.sqrt(num)

ans = 0
for serial in a:



    if input_list[serial] == 1:
        # print(serial)
        continue
    if input_list[serial] == 2:
        # print(serial)
        ans -= 1
        input_list[serial] = 1
        continue
    input_list[serial] = 2
    for s in range(serial*2, num, serial): 
        input_list[s] =1
    ans +=1
# for i in a:
    # print(i,input_list[i])
print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# ----------

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

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

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

if A[0] == A[1] == 1:
    print(0)
    exit()
if A[0] == 1:
    print(1)
    exit()


S = set()

for a in A:
    i = 2
    while a * i <= 10 ** 6:
        S.add(a * i)
        i += 1

ans = []
for a in A:
    if not a in S:
       ans.append(a)


D = defaultdict(int)
for a in ans:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)


print(len(L))

Submission status: Accepted

Solution code:
N = int(input())
l = list(map(int, input().split()))
M = max(l)

h = [1]*(M+1)
g = [0]*(M+1)

for v in l:
    if g[v] == 1:
        h[v] = 0
    g[v] = 1
    s = v*2
    while s <= M:
        h[s] = 0
        s += v
cnt = 0
for v in l:
    if h[v] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 一番小さい数はかならず条件を満たす(同じ数があるときはだめ)
# i!=j の任意のjで割り切れない → N-i!=jで一つでも割り切れるものがある数

'''
エラトステネスの篩の数列版じゃない？
1  2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

小さい方から倍数を取ってけば良いかな
'''


N = read_a_int()
A = read_ints()


cnt = Counter(A)
A = []
B = []
for k, v in cnt.items():
    if v == 1:
        A.append(k)
        # ただ消すだけじゃだめなんだ
    else:
        B.append(k)


A.sort()
AMAX = 10**6 + 10
is_first = [True] * (AMAX + 1)
for a in B:
    if is_first[a]:
        for j in range(a, AMAX + 1, a):
            is_first[j] = False

cnt = 0  # なにでも割り切れないときのcnt
for a in A:
    if is_first[a]:
        cnt += 1
        for j in range(a, AMAX + 1, a):
            # print(j)
            is_first[j] = False
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
lim = A[-1]
se = [True for i in range(lim + 1)]
ans = 0
for i, a in enumerate(A):
    if se[a]:
        if not((i != n - 1 and A[i + 1] == a) or (i != 0 and A[i - 1] == a)):
            ans += 1
        tmp = a
        while not tmp > lim:
            se[tmp] = False
            tmp += a
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
N=int(input())
alist=list(map(int,input().split()))

adic=defaultdict(int)
for a in alist:
  adic[a]+=1

noset=set()
aset=set()
max_a=0
for a,v in adic.items():
  aset.add(a)
  max_a=max(max_a,a)
  if v>=2:
    noset.add(a)
  
if not aset:
  print(0)
  sys.exit(0)
  
tlist=[False]*(max_a+1)
for a in aset:
  tlist[a]=True
#print(tlist)

for i in range(1,len(tlist)):
  if not tlist[i]:
    continue
  else:
    for j in range(2*i,len(tlist),i):
      tlist[j]=False
      
#print(tlist)
answer=0
for i in range(len(tlist)):
  if tlist[i] and not i in noset:
    answer+=1
    
print(answer)

Submission status: Accepted

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

seen = set()
A_set = set()
A_largest = 0
for a in A:
    if a > A_largest:
        A_largest = a
    if a not in seen:
        A_set.add(a)
        seen.add(a)
    else:
        if a in A_set:
            A_set.remove(a)

for b in range(1, A_largest+1):
    if b in seen:
        n = 2
        c =b*n
        while c <= A_largest:
            if c in A_set:
                A_set.remove(c)
            c += b

print(len(A_set))

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
alist = [int(v) for v in input().split()]
dup_set = {k for k, v in Counter(alist).items() if v >= 2}
alist = sorted(set(alist))
adict = {a: False for a in alist}
a_max = alist[-1]
max_ind = -1

count = 0
if 1 in adict:
    count = 0 if 1 in dup_set else 1
else:
    for a, f in adict.items():
        if f:
            continue
        if a not in dup_set:
            count += 1
        for k in range(a, a_max + 1, a):
            if k in adict:
                adict[k] = True
                if k == a_max:
                    max_ind -= 1
                    if abs(max_ind) <= len(alist):
                        a_max = alist[max_ind]

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
e=[1]*(10**6+1)
from collections import Counter
d=Counter(a)
if d[0]==1:exit(print(1))
if d[0]>1:exit(print(0))
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:
from collections import defaultdict

N=int(input())

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

dic=defaultdict(int)
max_dic=0

for i in range(N):
    if A[i] in dic:
        dic[A[i]]+=1
    else:

        dic[A[i]]=1
        max_dic=max(A[i],max_dic)

dic1=dic.copy()

for k in dic1:
    cn=k
    while cn<=max_dic:
        cn+=k
        if cn in dic:
            del dic[cn]

result=0

for m in dic:
    if dic[m]==1:
        result+=1

print(result)

Submission status: Accepted

Solution code:
from collections import Counter

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

MAX = 10 ** 6
is_divisible = [True] * (MAX + 1)
is_divisible[0] = False
for i in S:
    if not is_divisible[i]:
        continue
    for j in range(i * 2, MAX + 1, i):
        is_divisible[j] = False

for k, v in Counter(A).items():
    if v > 1:
        is_divisible[k] = False

ans = len([a for a in A if is_divisible[a]])
print(ans)

Submission status: Accepted

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

    a.sort()
    tf = [0] * (a[-1] + 1)
    for ea in a:
        tf[ea] = 1
    for i1 in range(n - 1):
        if a[i1] == a[i1 + 1]:
            tf[a[i1]] = 0

        for i2 in range(2, a[-1]//a[i1] + 1):
            tf[a[i1] * i2] = 0
    r = sum(tf)
    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
size = 1000001
# 1000001
# ar = [0] * 1000001
ar = [0] * size

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

for i in range(n):
	ar[br[i]] += 1


i = 1
cnt = 0
while i < size:
	if ar[i] is -1 or ar[i] is 0:
		i += 1
		continue
	
	if ar[i] == 1:
		# print(i)
		cnt += 1

	j = i
	while j < size:
		ar[j] = -1
		j += i

	i +=1

# print(ar)

print(cnt)

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
if n == 1:
    print(1)
    quit()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
M = max(a)
cnt = [0]*(M+1)
ans = 0
for i in range(n):
    if cnt[a[i]]:
        continue
    j = a[i]
    if i == 0:
        if a[i] == a[i+1]:
            1
        else:
            ans += 1
    elif i == n-1:
        if a[i-1] == a[i]:
            1
        else:
            ans += 1
    elif a[i] == a[i+1] or a[i-1] == a[i]:
        1
    else:
        ans += 1
    while j <= M:
        cnt[j] = 1
        j += a[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

MAXNUM = 1000001

def main():
    N = int(input())
    A = list(map(int, readline().split()))
    A.sort()
    Acounter = collections.Counter(A)
    acount1 = Acounter[1]
    if acount1 >= 1:
        if acount1 == 1:
            print(1)
            return
        else:
            print(0)
            return
    numset = set()
    for a in A:
        acount = Acounter[a]
        if a in numset:
            continue
        if acount > 1:
            numset.update(set(range(a, MAXNUM, a)))
        else:
            numset.update(set(range(2*a, MAXNUM, a)))

    cnt = 0
    for a in A:
        cnt += a not in numset

    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))
A = sorted(A)

maxA = A[-1]
halfA = maxA // 2

ans = [False] * maxA
for i in range(N):
    if i != N - 1 and A[i + 1] == A[i]:
        continue
    if i != 0 and A[i - 1] == A[i]:
        continue
    ans[A[i] - 1] = True

for i in A:
    if i > halfA:
        break
    j = i + i
    while j <= maxA:
        ans[j - 1] = False
        j += i

print(sum(ans))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
list=[0 for i in range(10**6+1)]
for i in A:
  list[i]+=1

for i in range(len(list)):
  if list[i]!=0:
    for j in range(2*i,10**6+1,i):
      list[j]=0
ans=0
for i in range(len(list)):
  if list[i]==1:
    ans+=1
print(ans)

Submission status: Accepted

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

max_A = max(A)
table = [False]*(max_A+1)
for i in A:
    if table[i] == False:
        table[i] = True
    else:
        table[i] = -1

mem = []        
for i in A:
    if table[i] == -1:
        table[i] = True
        mem.append(i)

for i in range(1, max_A+1):
    if table[i] == True:
        n = 2
        while i*n < max_A+1:
            table[i*n] = False
            n += 1

for i in mem: 
    if table[i] == True:
        table[i] = False
        
print(table.count(True))

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
a.sort()
li = np.zeros(a[-1])

u, counts = np.unique(a,return_counts=True)

for item in a[::-1]:
  li[item-1::item] = 0
  li[item-1] = 1

#print(li[:100])

for i in range(len(u)):
  if counts[i] >=2:
    li[u[i]-1] = 0

print(int(li.sum()))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
li = [1]*(10**6+5)
a.sort()
ans = 1
 
for i in range(a[0], len(li), a[0]):
  li[i] = [0]
 
flag = False
flag2 = True
for i in range(1, len(a)):
  if a[i-1] == a[i]:
    flag = True
    continue
  else:
    if flag and flag2:
      ans -= 1
    flag = False
  if li[a[i]] == 1:
    flag2 = True
    ans += 1
    for j in range(a[i], len(li), a[i]):
      li[j] = 0
  else:
    flag2 = False
if flag and flag2:
  ans -= 1
print(ans)

Submission status: Accepted

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

ct = Counter(As)
L = 10**6+1
flags = [True] * L
ans = 0
for k in sorted(ct.keys()):
    c = ct[k]
    if not flags[k]:
        continue
    flags[2*k::k] = [False] * ((L-k-1) // k)
    if ct[k] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# D

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = a[-1]
counter_a = Counter(a)

if n == 1:
    print(1)
    sys.exit()
    
if len(set(a)) == 1:
    print(0)
    sys.exit()

lis_prime = [False] * (max_a+1)
for a_ in a:
    lis_prime[a_] = True

primes = []
for i in range(len(lis_prime)):
    if lis_prime[i]:
        if counter_a[i]==1:
            primes.append(i)

        j = 2 * i
        while True:
            if j > max_a:
                break
            lis_prime[j] = False
            j += i

print(len(primes))

Submission status: Accepted

Solution code:
'''     ##     ##  #######  # #  ######
        ##     ##  ##   ##  ###    ##
        ##     ##  ##    #  # #    ##
        #########  #######  # #    ##    '''

import sys
import math
# sys.setrecursionlimit(10**6)

def get_ints(): return map(int, input().strip().split())
def get_list(): return list(get_ints())

def printspx(*args): return print(*args, end="")
def printsp(*args): return print(*args, end=" ")
def printchk(*args): return print(*args, end=" \ ")

MODPRIME = int(1e9+7); BABYMODPR = 998244353;

ONLINE_JUDGE = 1
if not ONLINE_JUDGE:
    sys.stdin = open("input.txt","r")  # <<<  Comment this line  >>> #
    sys.stdout = open("output.txt","w")  # <<<  Comment this line  >>> #
    sys.stderr = open("output.txt","w")  # <<<  Comment this line  >>> #

# for _testcases_ in range(int(input())):
n = int(input())
li = get_list()
flagli= [True]*n
d = {}
li.sort()
se = set(li)
for i in range(n):
    try:
        d[li[i]].append(i)
    except:
        d[li[i]] = [i]

for i in range(n):
    j = li[i]
    if flagli[i]:
        while j <= li[-1]:
            if j in d:
                for val in d[j]:
                    if val != i:
                        flagli[val] = False
            j += li[i]
for k, v in d.items():
    if len(v) > 1:
        for i in v:
            flagli[i] = False

# print(flagli)
ans = 0
for i in flagli:
    if i:ans+=1
print(ans)

'''
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
THE LOGIC AND APPROACH IS BY ME @luctivud ( UDIT GUPTA )
SOME PARTS OF THE CODE HAS BEEN TAKEN FROM WEBSITES LIKE::
(I Own the code if no link is provided here or I may have missed mentioning it)
DO NOT PLAGIARISE.
TESTCASES:
>>> COMMENT THE STDIN!! CHANGE ONLINE JUDGE !!
'''

Submission status: Accepted

Solution code:
import numpy as np
import sys
from collections import Counter
input = sys.stdin.buffer.readline
N = int(input())
A = sorted(list(map(int, input().split())))

B = np.ones(10**6 + 1, np.bool)
S = set()
for a in A:
    if B[a]:
        B[a * 2::a] = 0
        S.add(a)
# print('S', S)
# print('B', B[:20])

c = Counter(A)
# print('c', c)
for key, value in zip(c.keys(), c.values()):
    if value >= 2 and key in S:
        S.remove(key)
# print('S', S)
ans = len(S)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = [int(s) for s in input().split()]
A.sort()
MAX_VAL = A[-1]+1

duplicate = {}
for a in A:
    if a in duplicate:
        if duplicate[a]:
            continue
        else:
            duplicate[a] = True
            continue
    duplicate[a] = False

ng_map = {}
counter = 0
for a in A:
    if a in ng_map:
        continue
    if not(a in duplicate and duplicate[a]):
        counter += 1
    for i in range(a, MAX_VAL, a):
        ng_map[i] = True

print(counter)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    mx=10**6
    aa=LI()
    ac=Counter(aa)
    #print(aa)

    ok=[True]*(mx+1)
    ans=0
    for a,c in sorted(ac.items()):
        if ok[a]:
            if c==1:ans+=1
            for b in range(a*2,mx+1,a):
                ok[b]=False
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
maxA = max(A)
tbl = set()
dup = set()
vis = set()
for a in A:
   if a in vis:
      dup.add(a)
   else:
      vis.add(a)
   s = a
   while s < maxA:
      s += a
      tbl.add(s)

cnt = 0
for a in A:
   if a in dup:
      continue
   if a not in tbl:
      cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
m = dict()
d = dict()
n = int(input())
a = [int(i) for i in input().split()]

maxer = max(a)
for i in range(1, maxer + 1):
    m[i] = 1
    d[i] = 1

for i in a:
    if m[i] != 0 and d[i] != 0:
        d[i] = 0
        k = 2
        while True: 
            t = i * k
            if t <= maxer:
                m[t] = 0
                k += 1
            else:
                break
    elif d[i] == 0:
        m[i] = 0
        
res = 0
for i in a:
    if m[i] == 1:
        res += 1

print(res)

Submission status: Accepted

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    #divisors.sort(reverse=True)
    return divisors

def main():
    A.sort()
    S = set(A)
    m = max(A)
    X = [0]*(m+1)
    for i in range(1, m+1):
        j = i
        if j not in S:
            continue
        while j <= m:
            X[j] += 1
            j += i
    #print(X)

    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1

    ans = 0
    for a in A:
        if X[a] == 1 and D[a] == 1:
            ans += 1
    print(ans)

    #for i in range(m+1):
    #    if X[i] == 1:
            #print(i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
a=list(map(int,input().split()))
a.sort()
s=10**6
s+=100
sosu_flag=[True for i in range(s)]
#素数であるかどうかの前計算
#素数をn倍していき倍数をどんどん塗りつぶしていくイメージ
ans=0
cal=[]
for i in a:
    if not sosu_flag[i]:
        continue
    ans+=1
    cal.append(i)
    for j in range(i,s,i):
        sosu_flag[j]=False

c=Counter(a)
for key in cal:
    if c[key]>1:
        ans-=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
L = [0] * (10 ** 6 + 1)
S = set()

for a in A:
    if L[a]:
        continue
    if a in S:
        L[a] = 1
    S.add(a)
    for i in range(2, 10 ** 6 + 1):
        if a * i > 10 ** 6:
            break
        L[a * i] = 1

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split())) 
A.sort()
mx = A[-1]
E = [False]*(mx + 3)
ans = 0
A += [float("inf")]*2
for i in range(N):
    a = A[i]
    if not(E[a]) and A[i+ 1] != A[i]:
        ans += 1
    for j in range(1,(mx // a )+ 1):
        E[a*j] = True

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            yakusu.append(i)
            if n // i != i:
                yakusu.append(n//i)
    return yakusu
     
baisu = [False] * (10**6 + 1)
def main():
    N = I()
    A = LI()

    ok = 0
    for a in set(A):
        if baisu[a]:
            continue
        if not baisu[a]:
            num = a + a
            while num < 10**6+1:
                baisu[num] = True
                num += a
    s = collections.Counter(A)
    for a in A:
        if not baisu[a]:
            if s[a] > 1:
                continue
            ok += 1
    print(ok)
main()

Submission status: Accepted

Solution code:
import collections
N = int(input())
cA = collections.Counter([int(_) for _ in input().split()])
cand = set(range(1, 1000001))
ans = 0
for a in sorted(cA.keys()):
    if a in cand:
        if cA[a] == 1:
            ans += 1
        for c in range(a, 1000001, a):
            if c in cand:
                cand.remove(c)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
~~ Author : Bhaskar
~~ Dated : 07~06~2020
"""

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 array import array
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")

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)

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = (10 ** 6) + 5
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1] and prime[A[i]]:
            prime[A[i]] = False
            for j in range(A[i] * 2, MAX, A[i]):
                prime[j] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
a.sort()
m=max(a)
x=[1 for i in range(m+1)]
for p in a:
    if m//p:
        for k in range(2,m//p+1):
            x[p*k]=-1

ans=0
dic=defaultdict(int)
for i in a:
    dic[i]+=1

for p in a:
    if x[p]==1 and dic[p]==1: ans+=1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
from collections import Counter as co
l=co(list(map(int,input().split())))
ans=len(l)
ng=set()
for k in l:
    if l[k]>=2:ng.add(k)
    for i in range(2*k,10**6+1,k):

        if i in l:
            ng.add(i)
            
            

print(ans-len(ng))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort()
    L = max(A)
    ad = defaultdict(int)
    for a in A: ad[a] += 1

    ans = 0
    B = [True] * (L + 1)
    for a in A:
        if B[a]:
            if ad[a] == 1: ans += 1
        k = 2 * a
        while k <= L:
            B[k] = False
            k += a

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))
    a.sort()

    a_max=max(a)+1
    table=[False]*a_max
    cnt=0
    s=set()
    t=set()
    for i in range(n):
        a_i=a[i]
        if table[a_i]==False:
            s.add(a_i)
            if table[a_i]==False:
                cnt+=1
            for x in range(a_i,a_max,a_i):
                table[x]=True
        else:
            if a_i in t:
                pass
            elif a_i in s:
                cnt-=1
                t.add(a_i)

    print(cnt)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
r = [0 for _ in range(max(a)+1)]
l = [0 for _ in range(max(a)+1)]
ans = n
for i in a:
    r[i] += 1
    l[i] = 1
for i in range(len(r)):
    if r[i]:
        if 1 < r[i]:
            l[i] = 0
        for j in range(2*i,len(r),i):
            if r[j]:
                l[j] = 0
print(sum(l))

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
A=Counter(sorted(list(map(int,input().split()))))
number=[True for i in range(10**6+1)]

cnt=0
for v,m in A.items():
    if m!=1:
        for i in range(v,10**6+1,v):
            number[i]=False
    else:
        if number[v]==True:
            cnt +=1
            for i in range(v,10**6+1,v):
                number[i]=False
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
mx = a[-1]
c = [0 for _ in range(mx+1)]
ans = 0
if a[0] == 1:
  if n == 1:
    print(1)
    exit()
  if a[1] == 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
i = 0
while i < n:
  if c[a[i]] == 0:
    p = a[i]
    for _ in range(2,mx//a[i]+1):
      p += a[i]
      c[p] = 1
    flag = True
    while i+1 < n and a[i+1] == a[i]:
      i += 1
      flag = False
    if flag:
      ans += 1
  i += 1
print(ans)