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:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    check = Counter(a).items()
    memo = [True] * (2 * 10 ** 6 + 1)
    a = []
    for k, v in check:
        if v == 1:
            a.append(k)
        else:
            memo[k] = False
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * k:
                    break
                memo[i * k] = False
    ans = 0
    a.sort()
    for aa in a:
        if memo[aa]:
            ans += 1
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * aa:
                    break
                memo[i * aa] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
b = set(a)

NN = 10 ** 6 + 100
primes = set([])
isprime = [False for _ in range(NN + 1)]
cnt = [True for _ in range(NN + 1)]
for i in a:
    if cnt[i]:
        isprime[i] = True
        cnt[i] = False
    else:
        isprime[i] = False
for i in range(1, NN + 1):
    if not cnt[i]:
        for j in range(i * 2, NN + 1, i):
            isprime[j] = False
    if isprime[i]:
        primes.add(i)
ans = 0
for i in b:
    if isprime[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = _i()
    a = Counter(_ia())
    k = sorted(a.keys())
    m = max(k) + 1
    c = [False for i in range(m)]
    cnt = 0
    for ki in k:
        if c[ki]:
            continue
        if a[ki] == 1:
            cnt += 1
        for j in range(ki+ki, m, ki):
            c[j] = True

    return cnt


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N==1:
  print(1)
else:
  A.sort()
  import numpy as np

  l = np.array([0] * (10**6 + 10))
  m = np.array([0] * (10**6 + 10))
  for i in range(N):
    l[A[i]] += 1
    m[A[i]] += 1

  ans = 0
  length = len(l)
  for i in range(length):
    if l[i]==1:
      ans += 1
    
    if m[i]>=1:
      l[i::i] = 0

  print(ans)

Submission status: Accepted

Solution code:
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    count = 0
    for i in range(n):
        for div in divisors[a[i]]:
            if (div in hm and (div!=a[i] or hm[a[i]]>1)) or ((a[i] // div in hm) and (div!=1 or hm[a[i]]>1)):
                count -= 1
                break
        count += 1
    print(count)
    return


def get_divisors():
    divisors = [[] for _ in range(mxa+1)]
    for i in range(1, 10**3+1):
        for j in range(i, mxa+1, i):
            divisors[j].append(i)
    return divisors


n = RN()
a = RA()
mxa = max(a)
hm = {}
for ai in a:
    if not ai in hm:
        hm[ai] = 0
    hm[ai] += 1
divisors = get_divisors()
solve()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
*arr, = map(int, input().split())
arr.sort()
mx = max(arr)
is_enabled = [1] * (mx + 1)

counter = Counter(arr)
for val, cnt in counter.items():
    if cnt > 1:
        is_enabled[val] = 0

for i, v in enumerate(arr):
    if i == 0 or arr[i - 1] != v:
        x = v * 2
        while x <= mx:
            is_enabled[x] = 0
            x += v

cnt = 0
for v in arr:
    if is_enabled[v]:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
b = {}
c = 0
for i in range(n):
    if a[i] not in b:
        for j in range(1, 10**6//a[i]+1):
            b[a[i]*j] = 1
        if a[i] != a[i+1]:
            c += 1
print(c)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
used = [False] * (10 ** 6 + 1)
A.sort()
ans = 0
for j in range(n):
    a = A[j]
    if used[a]:
        continue
    ans += 1
    if j < n - 1:
        aa = A[j + 1]
        if aa == a:
            ans -= 1
    for i in range(1, 10 ** 6 // a + 1):
        used[a * i] = True
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6

B = Counter(A)
C = list(B.keys())
C.sort()

table = [1] * (M + 1)
cnt = 0
for c in C:
    if B[c] == 1:
        if table[c] == 1:
            cnt += 1
    for i in range(M):
        if c * i > M:
            break
        else:
            table[c * i] = 0

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(map(int, input().split()))
if A[0] == 1:
    if N > 1 and A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = 0
    MAX = 10 ** 6 + 3
    C = [False] * MAX
    for i in range(N):
        if not C[A[i]]:
            if i != N - 1 and A[i] != A[i + 1]:
                ans += 1
            elif i == N - 1:
                ans += 1
            cur = 1
            while cur * A[i] <= MAX:
                C[cur * A[i]] = True
                cur += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    MAX_A = max(A)
    A_COUNT = Counter(A)

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

    ans = 0
    prime = [False] * 2 + [True] * (MAX_A - 1)
    for a in A:
        if prime[a]:
            if A_COUNT[a] == 1:
                ans += 1
            for j in range(a, MAX_A + 1, a):
                prime[j] = False
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

MAX = 10**6+1

used = [False]*MAX


res = 0

for i in range(n):
    if used[a[i]]:
        continue
    if i+1 == n or a[i+1] != a[i]:
        res += 1
    for j in range(a[i],MAX,a[i]):
        used[j] = True

print(res)

Submission status: Accepted

Solution code:
N = int(input())
Ali = list(map(int,input().split()))
Alis = set()
Blis = set()

Ali.sort()

for i in range(N):
  if Ali[i] in Alis:
    Blis.add(Ali[i])
    continue
  Alis.add(Ali[i])

Alis -= Blis

for i in range(N):
  Alis.difference_update(range(Ali[i]*2, Ali[-1]+1, Ali[i]))
  
print(len(Alis))

Submission status: Accepted

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

A.sort()
numbers = range(M)
not_divisible = [True] * (M)

result = 0
for i in range(N):
    target = A[i]
    if not_divisible[target]:
        if i+1 <= N-1 and A[i+1] == A[i]:
            pass
        else:
            result += 1
        for j in range(target, M, target):
            not_divisible[j] = False
print(result)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
ca=dict(Counter(a))
ablans=set([k for k,v in ca.items() if v==1])
notans=set([k for k,v in ca.items() if v>1])
if len(a)==0:
  print(0)
  exit()
a.sort()
maxa=a[-1]
for ai in a:
  i=2
  while maxa>=i*ai:
    ablans.discard(i*ai)
    i+=1
print(len(ablans))

Submission status: Accepted

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

cands = [False for i in range(0, 1000000 + 1)]
dir_cands = [False for i in range(0, 1000000 + 1)]
for a in A:
    if dir_cands[a]:
        cands[a] = True
    dir_cands[a] = True

    if cands[a]:
        continue

    x = 2 * a
    while x <= 1000000:
        cands[x] = True
        x += a

res = 0
for a in A:
    if not cands[a]:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
すべてのjで割れない場合、カウントする。
逆に言えば、一つでもiをjで割れるようなjが存在するならば、それはカウントしない。
一番小さい数が2つあればそれはカウントしないが、基本的に一番小さい数はほかのどの数字でも割れない
Aiの制約が10**6であることから、小さい数から数えていって、10**6までの倍数の場所にマークを付ける。
初めて出てくるような数字に関して、カウントを1足してやる。
一番小さい数のコーナーケースに注意
"""
n = int(readline())
lst1 = list(map(int,readline().split()))

lst1.sort()

memo = [0]*(10**6+1)
if n == 1:
    print(1)
    exit()

ans = 0
for i in range(n):
    if memo[lst1[i]] == 0:
        if i < n-1:
            if lst1[i] != lst1[i+1]:
                ans += 1
        elif i == n-1:
            ans += 1
        j = 1
        while lst1[i]*j <= 10**6:
            memo[lst1[i]*j] = 1
            j += 1

print(ans)

Submission status: Accepted

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

import collections
buf = collections.Counter(dat)
dat = []
dat = list(buf.keys())

dat.sort()

res = 0

used = [False] * (1000100)

for i in range(len(dat)):
    ok = True

    if used[dat[i]]:
        ok = False
    if buf[dat[i]] != 1:
        ok = False

    c = 0
    v = -1
    while True:
        c += 1
        v = dat[i] * c
        if v > 1000010:
            break
        used[v] = True

    used[dat[i]] = True

    if ok:
        res += 1
#print(used[:10])
print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = sorted(li())
#A = sorted(li(), reverse= True)
max_a = A[-1]

flag = [0] * (A[-1]+1)
cnt = 0

for i, num in enumerate(A):
    #print(flag)
    if i == N-1 and not flag[num]:
        cnt += 1
    elif not flag[num] and A[i+1]!=num:
        cnt += 1
    x = num
    while True:
        flag[x] = 1
        x += num
        if x > max_a:
            break

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)
B = [k for k,v in ctr.items() if v == 1]
B.sort()
D = {b:i for i,b in enumerate(B)}

ok = [1] * len(B)
MX = 10**6+1
for k in ctr.keys():
    for n in range(2*k,MX,k):
        if n in D:
            ok[D[n]] = 0
print(sum(ok))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A_list = sorted(list(map(int, input().split())))
    max_a = A_list[-1]

    res = 0
    multi_set = set([])
    for i,a in enumerate(A_list):
        if a not in multi_set:    
            for j in range(1,max_a//a + 1):
                multi_set.add(a*j)
            
            if i == N-1:
                res += 1
            elif A_list[i+1] != a:
                res += 1
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
b=[0]*(10**6+1)
for i in a:
    b[i]+=1
    if b[i]==1:
        for j in range(2*i,10**6+1,i):
            b[j]+=100
print(b.count(1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int,input().split()))
ma = max(a)
lis = [i for i in range(1,ma+1)]
a.sort()
f = [-1 for i in range(ma+1)]
ans = 0

for i in a:
    if f[i]==-1:
        ans +=1
        f[i]=2
        for j in range(i+i,ma+1,i):
            f[j] = 1
    elif f[i]==2:
        ans-=1
        f[i] = 1
    else:
        continue

print(ans)

Submission status: Accepted

Solution code:
MAX = 10**6
N = int(input())
A = list(map(int, input().split()))
B = [0] * (MAX+1)
for i in range(N):
  B[A[i]] += 1
L = [0] * (MAX+1)
for k in range(MAX+1):
  if(B[k] >= 1 and L[k] == 0):
    tmp = 2*k
    while(tmp <= MAX):
      L[tmp] = 1
      tmp += k

ans = 0
for i in range(N):
  if(B[A[i]] == 1 and L[A[i]] == 0):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *

N = INT()
A = LIST()
A.sort()

A_max = max(A)

a = [0]*(A_max+1)

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

for i in range(A_max+1):
	if a[i] == 1:
		ans += 1
	if 0 < a[i]:
		for j in range(A_max//i + 1):
			a[i*j] = 0

print(ans)

Submission status: Accepted

Solution code:

from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size,init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]



def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x,A):
    n=len(x)
    res=[-1]*n
    for i in range(n):

        res[i]=x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b=bin(b)
        tmp=b[2:].zfill(digit)
        yield list(map(int,tmp))
        #b=list(map(int,list(b[2:].zfill(digit))))
        #yield b
        

def search(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())
A=acinput()


M=max(A)
m=[0]*(M+1)
for i in range(N):
    
    x=A[i]
    m[x]+=1
    
    k=2
    while True:
        if x*k<=M:
            m[x*k]+=1
        
            k+=1
        else:
            break


res=0
for a in A:
    if m[a]==1:
        res+=1

        
print(res)
        
        
#print(m)

Submission status: Accepted

Solution code:

def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis

N = int(input())

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

ans = 0
lis = [0] * (10**6+1)
tmp,dl = Sieve(10**6+2)

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        lis[A[i]] = 1
        continue

    dic = {}
    now = A[i]
    while dl[A[i]] != -1:

        if dl[A[i]] not in dic:
            dic[dl[A[i]]] = 1
        else:
            dic[dl[A[i]]] += 1
        A[i] //= dl[A[i]]

    if A[i] != 1:
        if A[i] not in dic:
            dic[A[i]] = 1
        else:
            dic[A[i]] += 1

    l1 = [1]
    #print (now,dic)
    for i in dic:
        l2 = [i**j for j in range(dic[i]+1)]

        tmp = len(l1)
        for x in range(tmp):
            for y in l2:
                if y != 1:
                    l1.append(l1[x]*y)

    flag = True
    #print (now , l1)
    for i in l1:
        if lis[i] > 0:
            flag = False
            break

    if flag:
        ans += 1
    lis[now] = 1

print (ans)

Submission status: Accepted

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

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

M = A[N-1]
K = [False]*(M+1)
ans = 0
for i in range(N-1):
    a = A[i]
    if K[a]:
        continue
    if A[i+1] != a:
        ans += 1
    for i in range(a, M+1, a):
        K[i] = True
if not K[ A[N-1] ]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
a.sort()
b = [True]*(a[n-1]+1)
ans = 0
for i in range(n):
    x = a[i]
    if not b[x]:
        continue
    if not (i<n-1 and a[i+1]==a[i]):
        ans += 1
    for j in range(x,a[n-1]+1,x):
        b[j] = False
print(ans)

Submission status: Accepted

Solution code:
import sys, math
#import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.buffer.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = 998244353
#from decimal import Decimal

n=int(data())
A=mdata()
d=dd(int)
for i in range(n):
    d[A[i]]+=1
cnt=0
m=max(A)
P=[0]*(m+1)
for i in range(1,m+1):
    if d[i]>0:
        if P[i]==0:
            for j in range(2*i,m+1,i):
                P[j]=1
            if d[i]==1:
                cnt+=1
out(cnt)

Submission status: Accepted

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

if N==1:
  print(1)
  exit()
  
if N==2:
  if A[0]==A[1]:
    print(0)
  elif A[1]%A[0]==0:
    print(1)
  else:
    print(2)
  exit()
  
for i in range(N):
  if 0<i<N-1 and (A[i]==A[i-1] or A[i]==A[i+1]):
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  elif i==0 and A[i]==A[i+1]:
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  elif i==N-1 and A[i-1]==A[i]:
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  
  if B[A[i]]==1:
    counter+=1
    j=2
    while A[i]*j<=10**6:
      B[A[i]*j]=0
      j+=1
print(counter)

Submission status: Accepted

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

import copy
B=copy.deepcopy(A)
B.sort()

D={}
for i in range(N):
    if A[i] not in D:
        D[A[i]]=1
    else:
        D[A[i]]=2
ANS=0
for i in range(N):
    if D[B[i]]==2 and E[B[i]]==1:
        for j in range(1,10**7):
            if B[i]*j>=len(E):
                break
            else:
                E[B[i]*j]=0
    elif D[B[i]]==2 and E[B[i]]==0:
        continue
    else:
        if E[B[i]]!=0:
            ANS+=1
            for j in range(1,10**7):
                if B[i]*j>=len(E):
                    break
                else:
                    E[B[i]*j]=0
print(ANS)

Submission status: Accepted

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

cnt = [0] * (a[-1] + 1)
for i in range(n):
    cnt[a[i]] += 1

ans = 0
for i in range(1, a[-1] + 1):
    if cnt[i] > 0:
        if cnt[i] == 1:
            ans += 1
        for j in range(2, a[-1] + 1):
            na = i * j
            if na <= a[-1]:
                cnt[na] = 0
            else:
                break

print(ans)

Submission status: Accepted

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

A.sort()
from collections import Counter
L = dict(Counter(A))

Xs = list(L.keys())
NX = len(Xs)

B = [0]*(10**6+1)

if NX!=1:
    cnt = 0
    for X in Xs:
        if B[X]>0:
            continue
        else:
            if L[X]==1:
                cnt += L[X]
            check = X
            t = 2
            while check*t<10**6+1:
                B[check*t]=1
                t+=1
    print(cnt)
else:
    if N==1:
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


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


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 10 ** 9 + 7
def wari(n):
    res = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            res.append(i)
            res.append(n // i)

    return res
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def yaku(n):
    fac = primeFactor(n)
    # print(type(fac))
    res = [1]
    for k, v in fac.items():
        new = []
        for i in range(v+1):
            for r in res:
                new.append(r * (k**i))
        res = new
    return res
def solve():
    n = getN()
    nums = getList()
    cnt = Counter(nums)
    ans = 0
    for num in nums:
        flag = True
        # print(primeFactor(num))
        for r in yaku(num):
            if r in cnt.keys() and (r != num or cnt[r] > 1):
                flag = False
                # print(r)
                break
        if flag:
            ans += 1

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
a.sort()

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

ans = 0
for i in a:
    if cnt[i] == 1 and lst[i]:
        ans += 1
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1
    elif lst[i]:
        j = 1
        while i*j <= 10**6:
            lst[i*j] = False
            j += 1

print(ans)

Submission status: Accepted

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

A.sort()

check = [0]*A[-1]

ans = 0
for i in range(N):
    elem = A[i]
    if check[elem-1]==0:
        if i < N-1:
            if elem != A[i+1]:
                ans += 1 
        if i==N-1:
            ans += 1
    
    now = elem
    while now <= A[-1]:
        check[now-1] = 1
        now += elem
        
print(ans)

Submission status: Accepted

Solution code:

def main():
    from collections import Counter as ct
    n = int(input())
    s = list(map(int, input().split()))
    a = ct(s)
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])
    s = set(s)

    ans = 0
    for i in a3:
        if i in s:
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    for i in a2:
        if i in s:
            ans += 1
            k = i
            while k <= 10**6:
                if k in s:
                    s.remove(k)
                k += i
    print(ans)


main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')


def main():
	n=II()
	A=LI()
	A.sort()
	A.append(10**7)
	li=[0]*(10**6+10)

	ans=0
	f=0
	for k in range(n):
		i=A[k]
		if i==A[k+1]:
			f=1
			continue
		if li[i]==0:
			if f==0:
				ans+=1
			j=1
			while i*j<10**6+5:
				li[i*j]=1
				j+=1
		f=0

	print(ans)
















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

L = 1000010
ps = [False] * L

cs = [0] * L
for i in range(N):
    cs[A[i]] += 1

cnt = 0
for i in range(N):
    if cs[A[i]] > 1:
        if not ps[A[i]]:
            j = A[i]
            while j < L:
                ps[j] = True
                j += A[i]
        continue
    if not ps[A[i]]:
        ps[A[i]] = True
        cnt += 1
        j = A[i] * 2
        while j < L:
            ps[j] = True
            j += A[i]

print(cnt)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

a.sort()

aa = s(a)

ans = 0
dp = [0 for i in range(10**6+1)]
for i in range(len(aa)):
	f = 0
	if aa[i][1] != 1:
		f = 1
	elif dp[aa[i][0]] != 0:
		f = 1
	for _ in range(aa[i][0],10**6+1,aa[i][0]):
		dp[_] = 1
	if not f:
		ans += 1



print(ans)