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:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
b = []
for i, j in Counter(a).most_common():
	if j == 1:
		b.append(i)
aset = set(a)

dp = [0 for _ in range(10**6+1)]
for i in list(aset):
	for j in range(i*2, 10**6+1, i):
		dp[j] += 1

ans = 0
for i in b:
	if dp[i] == 0:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input());dp=[1]*(10**7);C=Counter(sorted(list(map(int,input().split()))));ans = 0
for a,b in C.items():
    if b != 1:dp[a] = 0
    elif dp[a]:ans += 1
    for j in range(a,10**6+1,a):dp[j] = 0
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:
n = int(input())
a = list(map(int,input().split()))
a.sort()

n_max = 10**6+1

ans = 0
flag = [True] * (n_max)
for i in range(n-1):
    if(not flag[a[i]]):
        continue

    if(a[i]!=a[i+1]):
        ans += 1
    for j in range(a[i],n_max,a[i]):
        flag[j] = False

ans += flag[a[-1]]*1
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)
#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = [int(x) for x in input().split(" ")]
Amax = max(A)
dp = np.ones(Amax, dtype=bool)
appear = np.zeros(Amax, dtype=int)
for a in A:
  appear[a-1] += 1

for i in range(1, (len(dp) + 1) // 2):
  if not dp[i-1]:
    continue
  if appear[i-1] != 0:
    j = 2
    while j * i <= Amax:
      dp[j * i - 1] = False
      j += 1

count = 0
for a in A:
  if appear[a-1] > 1:
    continue
  else:
    count += dp[a-1]
print(count)

Submission status: Accepted

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

#kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    if work[A[i]]<=1:
        maxN = int(maxA/A[i])
        for n in range(1,maxN+1):
            buf = A[i]*n
            #remove_list.append(buf)
            work[buf]+=1
                #print(A[i]*n)

#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
MAX = max(A)

# 同値で何回もやらないようにsetにしておく
S = set(A)
ok = [1] * (MAX+1)
for a in S:
    # エラトステネスっぽく倍数の情報を更新
    for x in range(a+a, MAX+1, a):
        ok[x] = 0

# 同値が2つ以上ある場合もNGにする
C = Counter(A)
for k, v in C.items():
    if v >= 2:
        ok[k] = 0

# 全部チェックが済んだらあとは見るだけ
ans = 0
for a in A:
    if ok[a]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    L.sort()
    max_=L[-1]
    isDivisible = [False]*(max_) # 1-Lmax
    
    for i,x in enumerate(L):
        if i!=n-1 and x==L[i+1]:
            isDivisible[x-1]=True
            continue
        j=2*x
        while j<=max_:
            isDivisible[j-1]=True
            j+=x
    ans=0
    for x in L:
        if not isDivisible[x-1]:
            ans+=1
    print(ans)
# print(ans)
    
if '__main__' == __name__:
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))
c = Counter(a)
maxa = a[-1]+1
dp = [True] * maxa
s = list(set(a))
for x in s:
    for j in range(x*2,maxa,x):
        dp[j] = False
ret = 0
for x in a:
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
import bisect as bc

N = int(input())
A = list(map(int,input().split()))
 
A.sort()
 
dp = [True for _ in range(A[-1]+1)]
finished = [False for _ in range(A[-1]+1)]
 

for i in range(N):
    if not finished[A[i]]:
        finished[A[i]] = True
        ai = A[i]
        for j in range(2,A[-1]+1):
            if ai*j > A[-1]:
                break
            dp[ai*j] = False

ans = 0
for i in range(N):
    if dp[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8,b1


# @njit(b1[:](i8,i8,b1[:]))
@njit
def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


# @njit(i8(i8,i8,b1[:]))
@njit
def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


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

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = [int(x) for x in input().split(" ")]
Amax = max(A)
dp = np.ones(Amax, dtype=bool)
appear = np.zeros(Amax, dtype=int)
for a in A:
  appear[a-1] += 1

for i in range(1, len(dp)+1):
  if not dp[i-1]:
    continue
  if appear[i-1] != 0:
    j = 2
    while j * i <= Amax:
      dp[j * i - 1] = False
      j += 1

count = 0
for a in A:
  if appear[a-1] > 1:
    continue
  else:
    count += dp[a-1]
print(count)

Submission status: Accepted

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

from collections import Counter
c = Counter(A)

NMAX = 10 ** 6 + 1000
dp = [True] * (NMAX + 1)
for k, v in c.items():
    if not dp[k]:
        continue
    for i in range(k * 2, NMAX + 1, k):
        dp[i] = False
    if v > 1:
        dp[k] = False

count = 0
for k, v in c.items():
    if v > 1: continue
    if dp[k]: count += 1

print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
A.sort()
c=0
"""
for k in range(len(A)-1):
    if A[k] == A[k+1]:
        del A[k]
        A.insert(0,0)
        c+=1
        if k <len(A)-2:
            if A[k+1] != A[k+2]:
                del A[k+1]
                A.insert(0,0)
                c+=1
        else:
            del A[k+1]
            A.insert(0,0)
            c+=1
del A[:c]
if len(A)>0:
    saidai = A[-1]
else:
    saidai=0
#print(A)
"""
saidai = A[-1]
foo = [0 for k in range(saidai+1)]
for k in range(len(A)):
    if foo[A[k]] == 1:
        continue
    else:
        for j in range(A[k], saidai+1, A[k]):
            foo[j] = 1
        if k < len(A)-1:
            if A[k] == A[k+1]:
                continue
        if 0 < k < len(A):
            if A[k] == A[k-1]:
                continue
        count+=1
print(count)

Submission status: Accepted

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

for x in A: T.add(x)

maxi = max(A)

for x in sorted(A):
    i = 2
    while x * i <= maxi:
        if x * i in T:
            T.remove(x*i)
        i += 1
ans = 0

def counter(array):
    from collections import Counter
    return Counter(array)
c = counter(A)
for x in T:
    if c[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split(" ")))
Amax = max(A)
dp = np.ones(Amax, dtype=bool)
appear = np.zeros(Amax, dtype=int)
for a in A:
  appear[a-1] += 1

for i in range(1, len(dp)+1):
  if not dp[i-1]:
    continue
  if appear[i-1] != 0:
    j = 2
    while j * i <= Amax:
      dp[j * i - 1] = False
      j += 1
# print(dp)

app_set = set([])
dup_set = set([])
count = 0
for a in A:
  if appear[a-1] > 1:
    continue
  else:
    count += dp[a-1]
print(count -  len(dup_set))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline()

n=int(input())
A=list(map(int,input().split()))
cnt=[0]*(10**6+2)
ans=0
for a in A:
  if cnt[a]!=0:
    cnt[a]=2
    continue
  x=a
  while x<10**6+2:
    cnt[x]+=1
    x+=a
for a in A:
  #print(cnt[a])
  if cnt[a]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

U = 10**6 + 10

def main(A, primes):
    B = np.zeros(U + 1, np.int64)
    for x in A:
        B[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            B[p * i] += B[i]
    ret = 0
    for x in A:
        ret += B[x] == 1
    return ret

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[::1],i8[::1])')(main)
    cc.compile()
    exit()
from my_module import main

def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2:3] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]

A = np.array(read().split(), np.int64)[1:]
_, primes = prime_table(U)

print(main(A, primes))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
amax = a[-1] + 1
dp = [True] * amax
ans_set = set()
remove_set = set()
for e in a:
  if dp[e]:
    if e in ans_set:
      remove_set.add(e)
    else:
      ans_set.add(e)
      for i in range(e*2, amax, e):
        dp[i] = False
print(len(ans_set - remove_set))

Submission status: Accepted

Solution code:
from collections import Counter

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

flg = [0 for _ in range(10**6+1)]

ans = 0
for i in range(1,10**6+1):
    if counter[i] == 0:
        continue
    if flg[i] == 0 and counter[i] == 1:
        ans += 1
    for j in range(1,((10**6)//i)+1):
        flg[i*j] = 1

print(ans)

Submission status: Accepted

Solution code:
import math

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

A_list.sort()

topvalue = A_list[-1] + 1
counts = [0] * topvalue
hits = [False] * topvalue

for A in A_list:
	counts[A] += 1
	n = A + A
	while n < topvalue:
		hits[n] = True
		n += A

count = 0
for A in A_list:
	if counts[A] == 1 and hits[A] == False:
		count += 1
print(count)

Submission status: Accepted

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

from collections import Counter
c = Counter(A)

NMAX = 10 ** 6 + 1000
dp = [True] * (NMAX + 1)

for x in A:
    if not dp[x]:
        continue
    for i in range(x * 2, NMAX + 1, x):
        dp[i] = False
    if c[x] > 1:
        dp[x] = False
    
count = 0
for x in A:
    if dp[x]:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
T = set()
def counter(array):
    from collections import Counter
    return Counter(array)
c = counter(A)
for x in A:
    T.add(x)
cnt = 0
maxi = max(A)
for x in sorted(A):
    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:
n = int(input())
a = list(map(int,input().split()))

a.sort()

max_a = a[-1]
is_available = [True] * (max_a + 1)

ans = 0

for i, x in enumerate(a[:-1]):
    if is_available[x]:
        if not a[i+1] == x:
            ans += 1
        for b in range(x, max_a + 1, x):
            is_available[b] = False

if is_available[a[-1]]:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 

"""
3
1 1 2
のパターンが例外だった
"""

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

table = [0 for i in range(10 ** 6 + 1)]
cnt = 0

cc = collections.Counter(A)
duplicate = []
for key in cc.keys():
    if cc[key] > 1:
        duplicate.append(key)

for a in A:
    if table[a] != 0:
        pass
    else:
        if a not in duplicate:
            cnt += 1
        for i in range(1, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            table[a * i] = 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_s = sorted(a)
    a_set = set(a_s)
    maxv = max(a)
    res = [0] * maxv
    rep = 0
    for i in a_s:
        if res[i-1] == 0:
            for j in range(i, maxv+1, i):
                res[j-1] += 1
        else:
            res[i-1] +=1
    cnt = 0
    for i in range(n):
        if res[a[i]-1] == 1:
            cnt += res[a[i]-1]
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from numba import njit

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

U = 10**6 + 10

@njit('(i8[::1],i8[::1])', cache=True)
def solve(A, primes):
    B = np.zeros(U + 1, np.int64)
    for x in A:
        B[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            B[p * i] += B[i]
    ret = 0
    for x in A:
        ret += B[x] == 1
    return ret

def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2:3] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]

A = np.array(read().split(), np.int64)[1:]
_, primes = prime_table(U)

print(solve(A, primes))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] != 1:
        print(1)
    else:
        print(0)
    exit()
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8


def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


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

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()

Submission status: Accepted

Solution code:
from collections import Counter
if __name__ == "__main__":
    # Problem D
    N = int(input())
    A = sorted(map(int, input().split(' ')))
    dp = [1]* (A[-1]+1)
    C = Counter(A)

    for i in A:
        j = i*2
        while j < A[-1]+1:
            dp[j] = 0
            j += i

    ans=0
    for i in set(A):
        if C[i] == 1 and dp[i] == 1:
            ans+=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()

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

ans = 0
for x in set(a):
    if flg[x]:
        ans += 1

    tmp = 1
    while tmp * x <= 10 ** 6:
        flg[tmp * x] = False
        tmp += 1

print(ans)

Submission status: Accepted

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

a.sort()

max_a = a[-1]
is_available = [True] * (max_a + 1)

ans = 0

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and is_available[x]:
        ans += 1
    for b in range(x, max_a + 1, x):
        is_available[b] = False

if is_available[a[-1]]:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
M = max(a)
ok = [0]*(M+1)
a.sort()

for i in range(n):
    ok[a[i]] += 1
    if ok[a[i]] == 1:
        for g in range(a[i], M+1, a[i]):
            if g != a[i]:
                ok[g] += 2


print(ok.count(1))

Submission status: Accepted

Solution code:
from collections import Counter
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    dp = [True] * (10 ** 6 + 1)
    counter = Counter(A)

    A.sort()
    ans = 0
    for a in A:
        if dp[a]:
            if counter[a] == 1:
                ans += 1
            i = a
            while i <= 10 ** 6:
                dp[i] = False
                i += a
    
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    max=a[-1]
    check=[0 for i in range(max+10)]
    sum=0
    #print(a)
    if len(a)==1:
        print(1)
        exit()
    if a[0]==1:
        if a[1]==1:
            print(0)
        else:
            print(1)
        exit()
    for i in range(n):
        if check[a[i]]==0:
            sum+=1
            j=1
            x=a[i]*j
            while x<max+1:
                check[x]=1
                j+=1
                x=a[i]*j
            if i<n-1 and a[i+1]==a[i]:
                sum-=1
        else:
            continue
    print(sum)
        
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
count=[0]*1000001
divisible=[False]*1000001
ans=0
for i in a:
    count[i]+=1
for i in a:
    if count[i]>=2:
        if divisible[i]:
            continue
        else:
            j=1
            while i*j<=1000000:
                divisible[i*j]=True
                j+=1
    elif count[i]==1:
        if divisible[i]:
            continue
        else:
            ans+=1
            j=1
            while i*j<=1000000:
                divisible[i*j]=True
                j+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
exist_flags = [0] * (10 ** 6)
for a in A:
    if exist_flags[a - 1] > 0:
        exist_flags[a - 1] += 1
    else:
        # for i in range(a, 25, a):
        for i in range(a, 10 ** 6 + 1, a):
            exist_flags[i - 1] += 1


ans = 0
for a in A:
    if exist_flags[a - 1] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
kazu=[0]*(10**6+1)
for i in a:
  for j in range(i,10**6+1, i):
    if j > 10**6+1:
      break
    if kazu[i] >= 2:
      break
    kazu[j] += 1

count = 0
for i in a:
  if kazu[i] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
n=int(input())
li=list(map(int,input().split()))
li.sort()
a_max=li[-1]
dp=[0]*(a_max+1)
ans=0

for a in li:
  for aj in range(a,a_max+1,a):
    dp[aj]+=1
for a in li:
  if dp[a]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def chk():
    N = int(input())
    A=list(map(int,input().split(' ')))
    counter = Counter(A)

    flg = [0 for _ in range(10**6+1)]

    ans = 0
    for i in range(1,10**6+1):
        if counter[i] == 0:
            continue
        if flg[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1,((10**6)//i)+1):
            flg[i*j] = 1

    print(ans)

chk()

Submission status: Accepted

Solution code:
from collections import Counter
def i(): return int(input())
def l(): return list(map(int,input().split()))

N = i();A = l()
A.sort()
dp = [1]*(10**6+1)
C = Counter(A)
ans = 0
for a,b in C.items():
    if b != 1:dp[a] = 0
    elif dp[a]:ans += 1
    for j in range(a,10**6+1,a):dp[j] = 0
print(ans)

Submission status: Accepted

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

# 0 ~ 10**6に入力値の個数を入れる
# (count()で数えると、o(n**2)になるため)
val_list = [0 for i in range(10**6+1)]
for i in a_l:
	val_list[i] += 1

# 重複削除
a_l = list(set(a_l))

# 0 ~ 10**6のリスト
A_list = [True for i in range(10**6+1)]
# 倍数のところにFalseを入れる
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in a_l:
	if(val_list[i] != 1):
		continue
	if(A_list[i]):
		cnt += 1

print(cnt)

Submission status: Accepted

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax=A[-1]+1
    dp = [True]*Amax
    ans=0
    a_temp=set()
    a_tempcheck=set()
    for a in A:
        if dp[a]:
            ans+=1
            a_temp.add(a)
            for i in range(a, Amax, a):
                dp[i] = False
        else:
            if a not in a_tempcheck:
                if a in a_temp:
                    ans-=1
                    a_tempcheck.add(a)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

MAX = 1000005
cnt = [0] * MAX
for x in a:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    #cnt配列の各倍数のところに+1
    for i in range(x, MAX, x):
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# D - Not Divisible

N = int(input())
A = list(int(a) for a in input().split())
A.sort()

M = max(A)
is_D = [0] * (M+1)
for i, a in enumerate(A):
    if is_D[a]:
        is_D[a] = 2
        continue
    for j in range(a, M+1, a):
        is_D[j] += 1

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
l=[0for i in range(m+1)]
for i in range(n):
 for j in range(a[i], m + 1, a[i]):l[j] += 1
c=0
for i in range(n):
 if l[a[i]] == 1:c += 1
print(c)

Submission status: Accepted

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

s = A[-1]
p = [0 for _ in range(s+1)]
for i in A:
    p[i] += 1
    if p[i] > 1:
        continue
    for j in range(i*2,s+1,i):
        p[j] += 1
ans = 0
for i in A:
    if p[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

n = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]

# 使わなくて良い
# def get_sieve_of_eratosthenes_new(n):
#     import math
#     if not isinstance(n, int):
#         raise TypeError('n is int type.')
#     if n < 2:
#         raise ValueError('n is more than 2')
#     prime = []
#     limit = math.sqrt(n)
#     data = [i + 1 for i in range(1, n)]
#     while True:
#         p = data[0]
#         if limit <= p:
#             return prime + data
#         prime.append(p)
#         data = [e for e in data if e % p != 0]

# 倍数はOUTという判定を行ってく

# その前に複数あるものはのぞく

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

filtered = []

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

# 倍数かどうかチェック用カウンタ
cnt = [0] * ((10**6)+1)

# 重複のない要素それぞれで倍数を見ていく（上限まで）
a = list(set(a))
for elem in a:
    # 自分自身はカウントしない
    # elemずつ増えるので、倍数という意味になる
    for i in range(elem*2, (10**6)+1, elem):
        cnt[i] += 1

ans = 0
# filteredのうち何らかの倍数になっていないものの数が答え
for i in filtered:
    if cnt[i] == 0:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = [False] * (Amax + 1)
for x in A:
    for j in range(x, Amax + 1, x):
        ans[j] += 1

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

Submission status: Accepted

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

MAX = 1000005
cnt = [0] * MAX
for x in a:
    if cnt[x] > 2:
        continue
    #cnt配列の各倍数のところに+1
    for i in range(x, MAX, x):
        cnt[i] += 1
ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def i(): return int(input())
def l(): return list(map(int,input().split()))

N = i();A = l();A.sort()
dp = [1]*(10**6+1);C = Counter(A);ans = 0
for a,b in C.items():
    if b != 1:dp[a] = 0
    elif dp[a]:ans += 1
    for j in range(a,10**6+1,a):dp[j] = 0
print(ans)

Submission status: Accepted

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

cnt = [0] * (10**6+1)
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for i in range(10**6+1)[a::a]:
        cnt[i] += 1
ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_s = sorted(a)
    a_set = set(a_s)
    maxv = max(a)
    res = [0] * maxv
    rep = 0
    for i in a_s:
        if i in a_set:
            if res[i-1] == 0:
                for j in range(i, maxv+1, i):
                    res[j-1] += 1
            else:
                res[i-1] +=1
    cnt = 0
    for i in range(n):
        if res[a[i]-1] == 1:
            cnt += res[a[i]-1]
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect as bc
 
N = int(input())
A = list(map(int,input().split()))
A.sort()
 
dp = [True for _ in range(A[-1]+1)]
 
for i in range(N):
    ai = A[i]
    for j in range(2,A[-1]+1):
        if ai*j > A[-1]:
            break
        dp[ai*j] = False
 
ans = 0
for i in range(N):
    if dp[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def i(): return int(input())
def l(): return list(map(int,input().split()))
N = i();A = l();A.sort();dp = [1]*(10**6+1);C = Counter(A);ans = 0
for a,b in C.items():
    if b != 1:dp[a] = 0
    elif dp[a]:ans += 1
    for j in range(a,10**6+1,a):dp[j] = 0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())						# 5
A =        list( map(int, input().split()) )	# 1 2 3 4 5 ...

A.sort()
maxA = A[-1]
X = [0]*(maxA+1)


for a in A:
  for i in range(1,maxA+1):
    x = a*i
    if x > maxA: break
    X[x] += 1

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

print(ans)
# print(A)
# print(X)

Submission status: Accepted

Solution code:

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


alist.sort()

hurui=[0]*(alist[-1]+1)

for i in range(n):
    for j in range(1,alist[-1]//alist[i]+1):
        hurui[alist[i]*j]+=1
ans=0
for i in range(n):
    if hurui[alist[i]]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import copy, collections

n = int(input())
a = list(map(int, input().split()))
size = max(a)
a.sort()
a = collections.deque(a)
a2 = copy.copy(a)
b = [0] * (size + 1)
while a:
    test = a.popleft()
    count = 1
    if not a:
        pass
    else:
        while a[0] == test:
            a.popleft()
            count += 1
            if not a:
                break
    for i in range(size // test):
        b[test * (i + 1)] += count
ans = 0
for i in range(n):
    if b[a2[i]] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys 

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

max_a = max(A)
counts = [0 for _ in range(max_a + 1)]
ans = 0

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

for a in A:
    if counts[a] == 1:
        ans += 1
    n = 1
    while n * a <= max_a:
        counts[n * a] += 2
        n += 1

print(ans)

Submission status: Accepted

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

MAX = 10 ** 6

fdp = [False for _ in range(MAX+1)]
tdp = [True for _ in range(MAX+1)]

for i in A:
    if tdp[i]:
        fdp[i] = True
        tdp[i] = False
    else:
        fdp[i] = False

for i in range(1, MAX+1):
    if not tdp[i]:
        for j in range(i*2, MAX+1, i):
            fdp[j] = False

ans = 0
for i in B:
    if fdp[i]:
        ans += 1
print(ans)

Submission status: Accepted

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

N = int(readline())
A = sorted(list(map(int,readline().split())))
M = A[-1]
from collections import Counter
counter = Counter(A)
dp = set()
ans = 0
for a in A:
  if a in dp:
    continue
  if counter[a] == 1:
    ans += 1
  for i in range(a * 2, M + 1, a):
    dp.add(i)
print(ans)