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:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    if N == 1:
        print(1)
        return
    A.sort()
    if A[0] == 1 and not A[1] == 1:
        print(1)
        return
    arr = [0] * (A[-1] + 1) # 1-indexed
    for a in A:
        arr[a] += 1

    count = 0
    for i in range(0, len(arr)):
        if arr[i] == 0:
            continue
        elif arr[i] == 1:
            count += 1
        j = 2
        while i * j <= A[-1]:
            arr[i * j] = 0
            j += 1
    print(count)


    return


# 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:
from math import sqrt
from time import perf_counter
t0=perf_counter()
N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.1)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
            if perf_counter()-t0>1.9:
                a=N
                break                
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

Submission status: Accepted

Solution code:
from math import ceil

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

m = 10 ** 6
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [(k,v) for k, v in n_map.items()]

v_a.sort(key=lambda x: x[0])
res = 0
nn_map = {}
for i, v in v_a:
    if i in nn_map:
        continue
    for j in range(1, ceil(m / i) + 1):
        nn_map[i * j] = True
    if v == 1:
        res += 1
print(res)

Submission status: Accepted

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

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    As.sort()

    setA = set(As)
    setDel = set()

    cands = []

    for a in As:
        if a in setDel:
            continue

        i = 1
        while a*i <= As[-1]:
            if a*i in setA:
                setDel.add(a*i)
            i += 1

        cands.append(a)

    # 重複する数字を調べる
    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    ans = 0
    for x in cands:
        if dic[x] > 1:
            continue
        ans += 1

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
al = [int(i) for i in input().split()]  
al.sort()
ma = al[-1]
from collections import Counter
c = Counter(al)

if n == 1:
  print(1)
else:
  sn = set()
  total = 0
  l = len(al)
  for num in al:
    if num in sn:
      continue
    if c[num] == 1:
      total += 1
    tmp = num
    while tmp <= ma:
      sn.add(tmp)
      tmp += num
  print(total)

Submission status: Accepted

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = {}
    if N == 1:
        print(1)
        return
    for i in range(0, N):
        if i == 0:
            if A[i + 1] == A[i]:
                B[A[i]] = 2
                continue
        elif i == N - 1:
            if A[i - 1] == A[i]:
                B[A[i]] = 2
                continue
        elif A[i - 1] == A[i] or A[i + 1] == A[i]:
            B[A[i]] = 2
            continue
        B[A[i]] = 1
    # print(*B.items())
    for b in B:
        if B[b] == 0:
            continue
        if B[b] == 2:
            B[b] = 0
        for i in range(2, max_ // b + 1):
            if b * i in B:
                B[b * i] = 0
                # print(b * i)
    res = 0
    for v in B.values():
        if v:
            res += 1
    # print(*B.items())
    print(res)
    return

main()

Submission status: Accepted

Solution code:
n=int(input())

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

A.sort()

lis=[0 for i in range(10**6)]

for i in A:
    if lis[i-1]==0:
        lis[i-1]=1
        j=2
        while i*j<=10**6:
            lis[i*j-1]=-1
            j+=1
    elif lis[i-1]==1:
        lis[i-1]=-2

cnt=0
for i in A:
    if lis[i-1]==1:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
# D 

from collections import Counter
N=int(input())
A=list(map(int,input().split()))
A.sort()
maxi=A[-1]
real=set()
forbid=set()
#print(A[0],maxi)
d=dict(Counter(A))
#print(d)

cnt=0
for i in range(N):
    if A[i] not in forbid:
        if d[A[i]]==1:
            cnt +=1
        p=maxi//A[i]
        for j in range(1,p+1):
            forbid.add(j*A[i])
        
        
#print(forbid)
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter


LEN = 10 ** 6
is_avl = [0] * (LEN + 1)
N = int(input())
A = Counter(map(int, input().split()))
for a in A:
    is_avl[a] = 1
for a in A:
    for i in range(2 * a, LEN + 1, a):
        is_avl[i] = 0
ans = 0
for a in A:
    if is_avl[a] == 1 and A[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def e(x,y):
    z=1
    if x<y:
        z=x
        x=y
        y=z

    while x!=0 and y!=0 and z!=0 and x!=y:
        z=x%y
        x=y
        y=z
    return x

n=int(input(''))
a=input('')
a=a.split(' ')
for b in range(n):
    a[b]=int(a[b])

p=[]
for b in range(10**6+1):
    p.append(0)

for b in range(n):
    p[a[b]]+=1

for b in range(10**6+1):
    if p[b]>=1:
        c=b+b
        while c<=10**6:
            p[c]=0
            c=c+b

s=0
for b in range(10**6+1):
    if p[b]==1:
        s=s+1

print(s)

Submission status: Accepted

Solution code:
n = int(input())

a = [int(x) for x in input().split()]

mx = max(a)

mark = [0 for _ in range(mx+1)]

for i in range(n):
	for x in range(a[i], mx+1, a[i]):
		mark[x] += 1

ans = 0

for i in range(n):
	if mark[a[i]] == 1:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

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

a.sort()
mx = max(a)

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

Submission status: Accepted

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

K = 10**6+1
num = [0] * K
l = [False] * K
for i in range(N):
    num[A[i]]+=1
    l[A[i]] = True

for i in range(1, K):
    if num[i]>0:
        if num[i]>1:
            l[i] = False
        j = 2
        while i*j < K:
            l[i*j] = False
            j += 1

ans = 0
for i in range(N):
    if l[A[i]]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A)
num = [0] * (M)
T = [0] * (M)
for a in A:
  num[a-1] += 1
  T[a-1] = 1
for i in range(M):
  if num[i] != 0 and T[i] == 1:
    n = 2 * (i + 1)
    while n <= M:
      T[n-1] = 0
      n += (i + 1)
ans = 0
for i in range(M):
  if T[i] == 1 and num[i] == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter
from numba import jit

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
b = list(set(a))
b.sort()
c = Counter(a)

se = set()

@jit
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in b:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
            break
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MAX = max(A) #Aの中の最大値
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  temp = A[j]
  if Adic[temp] >= 2: #同じ数が複数ある場合には削除
    if temp in Aset:
      Aset.remove(temp)
  fmax = MAX//temp
  #print(fmax,temp)
  for i in range(2,fmax+10): #fmaxまで見る
    now = temp*i
    if now in Aset:
      Aset.remove(now)
#print(Aset)
print(len(Aset))

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

N = int(input())
A = [int(x) for x in input().split()]
A.sort()

C = Counter(A)
D = defaultdict(bool)
for key in C.keys():
    D[key] = True

B = [True] * N
ans = 0
for i in range(N):
    if not D[A[i]]: continue
    if C[A[i]] > 1:
        D[A[i]] = False

    for a in range(2 * A[i], A[-1] + 1, A[i]):
        D[a] = False

ans = 0
for key in D:
    if D[key]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
d = {}
n = A[-1]
def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    i = 0
    for j in A:
        if i == j:
            isPrime[i] = False
            continue
        i = j
        if isPrime[i]:
            for j in range(i * 2, n + 1, i):
                isPrime[j] = False
    return isPrime
P = makePrimeChecker(n)
i = 0
ans = 0
for j in A:
    if i == j:
        continue
    else:
        i = j
        if P[i]:
            ans += 1
print(ans)

Submission status: Accepted

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

A_array.sort()

ans = 0

if A_array[0] == 1:
    if N >= 2 and A_array[1] != 1 or N == 1:
        print(1)
    else:
        print(0)
    exit()


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


for i, a in enumerate(A_array):
    if i != 0 and a == A_array[i - 1]:
        continue
    j = 2
    while a * j <= 10 ** 6:
        ng_array[a * j - 1] = 1
        j += 1


for i in range(N):
    a = A_array[i]
    if i != 0:
        if A_array[i] == A_array[i - 1]:
            continue
    if i != N - 1:
        if A_array[i] == A_array[i + 1]:
            continue
    if ng_array[a-1] == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

C=[1 for i in range(10**6+1)]
for i in range(N):
    if C[A[i]]==0:  #すでに割り切るものがあるとわかった場合
        continue
    if C[A[i]]==-1:  #同じ数字を2回目に通った時
        C[A[i]]=0
        continue
    C[A[i]]*=-1  #通ったの印
    j=2
    while A[i]*j<=10**6:  #それの倍数はすべてダメ
        C[A[i]*j]=0
        j+=1

print(C.count(-1))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
import numpy as np
# from copy import deepcopy
#from collections import deque

#import numba
#import math

def run():
    N = int(input())
    A = list(map(int, sysread().split()))
    NN = 10 ** 6 + 1
    A = sorted(A)
    checks = np.array([True] * NN)
    ret = 0
    for i, a in enumerate(A[:-1]):
        if checks[a] and a != A[i+1]:
            ret += 1
        if checks[a]:
            checks[a:NN+1:a] = False
    if checks[A[-1]]:
        ret += 1


    print(ret)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0]==1:
    if n==1 or a[1]>1:
        print(1)
    else:
        print(0)
    exit(0)
ok = [True]*(10**6+1)
ans = 0
pre = -1
for i in a:
    if not ok[i]:
        continue
    if i==pre:
        ok[i] = False
        continue
    pre = i
    for j in range(i*2, 10**6+1, i):
        ok[j] = False
for i in a:
    if ok[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
alist=list(map(int,input().split()))
alist.sort()
nolist=[False]*(10**6+1)

counter=0
for i,a in enumerate(alist):
    if not nolist[a]:
        for j in range(10**6 // a):
            nolist[a*(j+1)] = True

        if i == n-1:
            counter += 1
        elif alist[i+1] != a:
            counter += 1
print(counter)

Submission status: Accepted

Solution code:
def solve(A,N):
    A.sort()
    if N == 1:
        return 1
    elif N == 2:
        if A[1] == A[0]:
            return 0
        elif A[1] % A[0] == 0:
            return 1
        else:
            return 2
    else:
        Col = set()
        if A[0] == A[1]:
            Col.add(A[0])
        for i in range(1,N-1):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                Col.add(A[i])
        if A[N-1] == A[N-2]:
            Col.add(A[N-1])

        Mul = set()
        cand = set()
        for i in range(N):
            if A[i] not in Mul:
                if A[i] not in Col:
                    cand.add(A[i])
                for d in range(1,(A[N-1]//A[i])+1):
                    Mul.add(A[i] * d)

        return len(cand)

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(1)
    exit()

Ss = sorted(As)
cnt = 0
d = defaultdict(int)
As = [False] * (10**6+10)

for s in Ss:
    d[s] += 1

for s in Ss:
    if As[s]:continue
    else:
        if d[s] == 1:
            cnt += 1
        ind = 1
        while s * ind <= 10**6:
            As[s*ind] = True
            ind += 1

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
  
def chk(arr, n): 
  
    s = dict() 
    max_ele = -10**9
    for i in range(n):
        if arr[i] not in s: 
            s[arr[i]] = 1
        else:
            s[arr[i]] += 1
        max_ele = max(max_ele, arr[i]) 
      
    res = dict() 
    for i in range(n):
        for j in range(arr[i] * 2,  
                        max_ele + 1, arr[i]): 
                
            if (j in s.keys()): 
                res[j] = 1
    p = 0
    for i in arr:
        if i not in res.keys() and s[i] == 1:
            p += 1
    return(p)
  
print(chk(A, N) )

Submission status: Accepted

Solution code:
from math import sqrt
from random import randint
def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main1():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    a.sort()
    for i in range(n):
        v = a[i]
        if dic[v] > 1:
            continue
        lim = v//2 + 1
        f = True
        for j in range(i):
            if a[j] > lim:
                break
            if a[i] % a[j] == 0:
                f = False
                break
        if f:
            ans += 1
    print(ans)

def main2():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    for v in a:
        if dic[v] > 1:
            continue
        tmp = Divisor_Set(v)
        tmp.remove(v)
        f = True
        for x in tmp:
            if x in dic:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    if randint(1, 2) == 1:
        main1()
    else:
        main2()

Submission status: Accepted

Solution code:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    n = max(A)
    C = set()
    D = set()
    for a in A:
        if a in D:
            C.discard(a)
            continue
        D.add(a)
        C.add(a)
    if 1 in D:
        if 1 in C:
            print(1)
        else:
            print(0)
        return
    C2 = deepcopy(C)
    for a in D:
        for i in range(2,1+n//a):
            if (i*a) in C2:
                C2.discard(i*a)
    ans = len(C2)
    print(ans)
    return

def examE():
    N, Q = LI()
    AB = [LI()for _ in range(N)]



    ans = 0
    print(ans)
    return

def examF():
    H, W, K = LI()
    x1,y1,x2,y2 = LI()
    x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
    C = [SI()for _ in range(H)]

    def bfs_grid(h, w, s, maze):
        distance = [[inf] * w for _ in range(h)]

        def bfsg():
            queue_up = deque()
            queue_d = deque()
            queue_r = deque()
            queue_l = deque()
            queue_up.append(s)
            queue_d.append(s)
            queue_r.append(s)
            queue_l.append(s)
            distance[s[0]][s[1]] = 0
            while (len(queue_up) or len(queue_r) or len(queue_d) or len(queue_l)):
                if queue_up:
                    y, x = queue_up.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y + k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_up.append((ny, nx))
                if queue_d:
                    y, x = queue_d.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x, y - k
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_r.append((ny, nx))
                            queue_l.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_d.append((ny, nx))
                if queue_r:
                    y, x = queue_r.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x + k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_r.append((ny, nx))
                if queue_l:
                    y, x = queue_l.popleft()
                    for k in range(1, K + 1):
                        nx, ny = x - k, y
                        if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '@'):
                            if distance[ny][nx] <= distance[y][x] + 1:
                                continue
                            queue_up.append((ny, nx))
                            queue_d.append((ny, nx))
                            distance[ny][nx] = distance[y][x] + 1
                        else:
                            break
                        if k == K:
                            queue_l.append((ny, nx))

            return distance

        return bfsg()
    L = bfs_grid(H,W,(x1,y1),C)
    #print(L)
    ans = L[x2][y2]
    if ans==inf:
        ans = -1
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


n = int(input())
a = lmp()
a.sort()
cnt = 0
amax = max(a)
num = [0]*int(amax+5)
for i in range(n-1):
    if num[a[i]] == 0 and a[i] != a[i+1]:
        cnt += 1
    for j in range(a[i], len(num), a[i]):
        num[j] = 1
if num[a[-1]] == 0:
    cnt += 1


print(cnt)

Submission status: Accepted

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

def eratosthenes(n):
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    is_prime[4::2] = [False] * (n // 2 - 2)
    m = int(n**.5) + 1
    for i in range(3, m, 2):
        if is_prime[i]:
            is_prime[i*i::2*i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    # return [2] + [i for i in range(3, n, 2) if is_prime[i]]
    return is_prime

# prime = eratosthenes(2*10**6+10)
l = [0] * (10**6+1)
for a in A:
    l[a] += 1
ans = 0
for i in range(10**6+1):
    if l[i] == 1:
        # print(i)
        ans += 1
    if l[i] >= 1:
        for j in range(i, 10**6+1, i):
            l[j] = 0
print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
maxA = A[-1]

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

C = collections.Counter(A)
cand = set(A)

ans = 0
for i in range(N):
    if C[A[i]] >= 2:
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+1)])
        continue

    if A[i] in cand:
        ans += 1
        cand -= set([A[i]*j for j in range(1, maxA//A[i]+1)])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def BinarySearch(num, List):
    if len(List) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(List)
    while left < right:
        mid  = (left+right)//2
        if num < List[mid]:#
            right = mid
        else:
            left = mid + 1
    return right


def main():
    n = ni()
    a = sorted(na())
    asub = [i for i in a]

    for i in range(n):
        ai = a[i]
        right = BinarySearch(ai, a)
        if right-1 != i:
            asub[right-1] = -1
            asub[i] = -1
            continue
        cnt = 2
        while right != n:
            right = BinarySearch(ai*cnt, a)
            if asub[right-1] == ai*cnt:
                asub[right-1] = -1
            cnt += 1
    
    ans = 0
    for i in range(n):
        if asub[i] != -1:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)
min_=min(A)

ans=0
for i in reversed(range(N)):
    if A[i] in ng:
        continue
    if A[i]<min_*2:
        ans+=1
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = set()
T = set()
def counter(array):
    from collections import Counter
    return Counter(array)
c = counter(A)
for x in A:
    S.add(x)
    T.add(x)
cnt = 0
maxi = max(S)
for x in sorted(S):
    i = 2
    while x * i <= maxi:
        if x * i in T:
            T.remove(x*i)
        i += 1
ans = 0
for x in T:
    if c[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

if 1 in sa:
    if sa[1]>1:
        print(0)
    else:
        print(1)
    exit()

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1
    if ai%2==0:
        for i in range(2,min(int(ai**(1/2)+7),ai)):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
    else:
        for i in range(3,min(int(ai**(1/2)+7),ai),2):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
print(ans)

Submission status: Accepted

Solution code:
def solve():
	n = int(input())
	arr = list(map(int,input().split()))
	dic = {}
	for i in arr:
		if i not in dic:
			dic[i]=1
		else:
			dic[i]+=1
	arr.sort()
	ele = arr[n-1]
	count = [0]*(ele+1)
	for i in arr:
		mul = i
		k=2
		if dic[i]>1:
			count[i]=1
		while mul*k<=ele:
			if mul*k in dic:
				count[mul*k]+=1
			k+=1
	ans=0
	for i in range(0,n):
		if count[arr[i]]==0:
			ans+=1
		# print(count[arr[i]],ans)
		# print(arr[i],count[arr[i]],ans)
	print(ans)
	


if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
import heapq
N=int(input())
A=list(map(int,input().split()))
A.sort()
nums={}
for i in range(N):
    if nums.get(A[i])==None:
        nums[A[i]]=1
    else:
        nums[A[i]]=nums[A[i]]+1
#print(nums)
for i in range(len(A)):
    if nums[A[i]]!=0:
        for j in range(A[i]*2,10**6+1,A[i]):
            if nums.get(j)!=None:
                nums[j]=0
    if nums[A[i]]!=1:
        nums[A[i]]=0
ans=0
for i in range(len(A)):
    if nums[A[i]]==1:
        ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    p = set()
    no_count = set([k for k, v in Counter(A).items() if v >= 2])
    ans = 0
    for a in A:
        if a not in p:
            b = a
            while b <= A[-1]:
                p.add(b)
                b += a
            if a not in no_count:
                ans += 1
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(a)
nu = {k for k, v in c.items() if v > 1}

s = set()
u = set()
for aa in a:
    m = 2
    if aa in s or aa in u:
        continue
    u.add(aa)
    while aa*m <= mx:
        s.add(aa*m)
        m += 1

o = 0
for aa in a:
    if aa in s or aa in nu:
        continue
    o += 1

print(o)

Submission status: Accepted

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

a.sort()

is_divisible = [-1] * (10 ** 6 + 1)
is_divisible[0] = 1

ans = 0
for num in a:
    if is_divisible[num] == -1:
        ans += 1
        is_divisible[num] = 0
        for i in range(num * 2, 10 ** 6 + 1, num):
            is_divisible[i] = 1
    elif is_divisible[num] == 0:
        ans -= 1
        is_divisible[num] = 1
    else:
        continue

print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
d = list(map(int, input().strip().split()))

counts = collections.Counter(d)
dic = {a: True for a, c in counts.items()}

keys = sorted(dic.keys())
last = keys[-1]

for k in keys:
    if dic[k]:
        n = 2
        while k * n <= last:
            if k * n in dic:
                dic[k * n] = False
            n += 1
    # 重複していた場合の処理
    if counts[k] > 1:
        dic[k] = False

count = len([True for v in dic.values() if v])
print(count)

Submission status: Accepted

Solution code:
import collections
n = map(int, raw_input().split(' '))
ais = map(int, raw_input().split(' '))
cc = collections.Counter(ais)
ais.sort()
m = max(ais)
p = [True for _ in range(m + 1)]

count = 0
for ai in ais:
	if p[ai] is True:
		x = 2 * ai
	 	while(x < len(p)): 
	 		p[x] = False
	 		x += ai
for ai in ais:
	if p[ai] is True:
		if cc[ai] == 1:
			count +=1
print count