Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
import sys

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

if len(A) == 1:
    print(1)
    sys.exit(0)

box = [False] * (A[-1] + 1)
for a in A:
    box[a] = True

for idx, a in enumerate(A):
    if A[idx] == A[idx - 1]:
        box[a] = False
    for j in range(2, A[-1]//a + 1):
        box[a * j] = False

count = 0
for d in box:
    if d:
        count += 1
print(count)

Submission status: Accepted

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

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            B[a * i] = 0
    print(sum(B.values()))
    return

main()

Submission status: Accepted

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

dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for idx, a in enumerate(A):
    if A[idx] == A[idx - 1]:
        if idx == 0:
            None
        else:
            dp[a] = False
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)

Submission status: Accepted

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

i2s = lambda: sys.stdin.readline().rstrip()

def main():
    N = int(i2s())
    A = sorted(map(int, i2s().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            if B[a * i]:
                B[a * i] = 0
    print(sum(B.values()))
    return

main()

Submission status: Accepted

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

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            if B[a * i]:
                B[a * i] = 0
    print(sum(B.values()))
    return

main()

Submission status: Accepted

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

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

def solve_old(N, A):
    A = sorted(A)
    dp = [True for i in range(N)]  # Trueのものは、割り切れない（カウント対象）

    idx = 0
    while True:
        a = A[idx]
        for j, target in enumerate(A[i+1:]):
            if target % a == 0:
                dp[idx + j + 1] = False


    for i, a in enumerate(A):
        if dp[i] == False:
            continue

        elif A.count(a) > 1:  # 同じ値が複数入っていたら、その値はカウント対象外
            dp[i] = False
            continue

        for j, target in enumerate(A[i + 1:]):  # 探索対象の倍数を、リストから除外していく
            if target % a == 0:
                dp[i + j + 1] = False
    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


def solve_old(N, A):
    A = sorted(A)
    dp = [True for i in range(N)] # Trueのものは、割り切れない（カウント対象）

    for i, a in enumerate(A):
        if dp[i] == False:
            continue

        elif A.count(a) > 1: # 同じ値が複数入っていたら、その値はカウント対象外
            dp[i] = False
            continue

        for j, target in enumerate(A[i + 1:]): # 探索対象の倍数を、リストから除外していく
            if target % a == 0:
                dp[i+j+1] = False
    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


# 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:
#!python3.8
# -*- coding: utf-8 -*-
# abc170/abc170_d
from collections import Counter

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            B[a * i] = 0
    print(Counter(B.values())[1])
    return

main()

Submission status: Accepted

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

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 = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, max_ // a + 1):
            if a * i in B:
                B[a * i] = 0
    res = 0
    for v in B.values():
        if v:
            res += 1
    print(res)
    return

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import math
import collections
import math

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行N項目 x, y = map(int, input().split())
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    n = int(input())

    a_list = list(map(int, input().split()))
    # a_list = list(set(a_list))
    a_list.sort()
    collections.Counter(a_list)

    dp = [0 for i in range(1000001)]
    ans = 0

    # for i in range(len(a_list)):
    a_counter = collections.Counter(a_list)
    for a, cnt in a_counter.items():

        # 現在の桁が素数か判定
        if dp[a] > 0:
            dp[a] += 1
            continue

        # 次の桁が素数か判定するための準備
        # 現在の桁の情報を追加する
        aa = range(a, 1000001, a)
        for aaaa in aa:
            dp[aaaa] += cnt

    ans = 0
    for a in a_counter.keys():
        if dp[a] == 1:
            ans += 1

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """6
        2 7 21 1000000 1000000 1000000"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """93
951 299 994 913 105 760 468 12 613 158 61 536 877 688 548 81 398 916 378 556 871 268 814 220 18 455 913 677 239 697 590 520 261 885 734 749 473 384 641 76 612 28 86 144 205 772 201 999 88 940 699 873 938 44 285 272 342 219 648 254 314 421 988 617 755 921 820 257 565 376 454 965 513 253 350 834 47 275 866 450 102 159 790 814 364 406 851 236 298 288 999 238 283
"""
        output = """67"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """90
617 279 402 110 487 288 34 58 989 681 964 387 955 376 821 155 291 282 266 252 189 190 94 765 158 264 631 69 604 366 605 241 560 990 86 683 784 260 373 101 780 54 71 620 173 692 101 344 978 784 520 416 778 973 222 260 847 733 933 837 441 696 363 684 19 405 997 56 42 654 431 7 803 974 910 326 110 846 987 789 569 381 362 1 387 583 279 779 737 349
"""
        output = """1"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))

n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    mark=[0]*(10**6+5)
    for x in l:
        if mark[x]>=1:   #X已经出现了一次
            mark[x]=2
            continue
        mark[x]=1
        i=2
        while x*i<10**6+1:
            mark[x*i]=2
            i+=1
    ans=0
    for x in l:
        if mark[x]==1:ans+=1
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
for a in A:
    if a in ans:
        depricated.add(a)
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(map(int, input().split()))
U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    if a in ans:
        depricated.add(a)
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Submission status: Accepted

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

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
        continue
    if 2 < cnt[a]:
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Submission status: Accepted

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

cnt=[0]*(a[-1]+1)
#cntは0が25個続くリスト
for x in a:
  #xは3,8,11,16,24
 for i in range(x,a[-1]+1,x):
  #x = 3ならrange(3, 25, 3) = 3, 6, 9, 12, 15, 18, 21, 24
  
  cnt[i]+=1
  #xの倍数(xを含む)だったら1が足される
ans=0
for x in a:
 if cnt[x]==1:
  ans+=1
print(ans)

Submission status: Accepted

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

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
        continue
    if 2 < cnt[a]:
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Submission status: Accepted

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

U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

Submission status: Accepted

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

#定数倍のやつに＋１する
M=max(ls)
A=[0]*(M+1)
for i in range(N):
  a=M//ls[i]
  for j in range(1,a+1):
    if A[ls[i]]>=2:
      break
    else:
      A[j*ls[i]]+=1
  continue  
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max

for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        for j in range(2,a_Max+1):
            if a*j > a_Max:
                break
            B[a*j-1] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
            
ans = 0
for b in B:
    if b == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = ([0]*1000001)
a.sort()
for i in a:
    s[i] += 1
ans = 0
for j in range(1000001):
    if s[j] == 1:
        ans += 1
    if s[j] > 0:
        for k in range(j, 1000001, j):
            s[k] = 0
print(ans)

Submission status: Accepted

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

a=sorted(a)
m=max(a)
dp=[0]*(m+1)
d={}
cnt=0
for i in range(n):
    b=a[i]
    if b in d:
        d[b]+=1
        continue
    else:
        d[b]=1
    j=b
    while b<=m+b:
        if b>m:
            break
        dp[b]+=1
        b+=j
        


for i in a:
    if dp[i]==1 and d[i]==1:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
count_of_a = Counter(A)
# すでに出現した倍数の場合はアウト
ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        # 複数出現するとしても，初めての要素の場合は処理を行う
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
count_of_a = Counter(A)
# すでに出現した倍数の場合はアウト
ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        # 複数出現するとしても，初めての要素の場合は処理を行う
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Accepted

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

#定数倍のやつに＋１する
M=max(ls)
A=[0]*(M+1)
for i in range(N):
  a=M//ls[i]
  for j in range(1,a+1):
    A[j*ls[i]]+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
B = [True]*(A[-1]+1)
i = 0
for i in range(N):
  if i < N-1 and A[i] == A[i+1]:
    B[A[i]] = False
  if A[-1] < 2*A[i]:
    continue
  M = A[-1]//A[i]+1
  for j in range(2,M):
    B[j*A[i]] = False

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    A.sort(reverse=True)

    if A[-1] == 1:
        if N > 1 and A[-2] == 1:
            print(0)
        else:
            print(1)
        return

    MAX = 10 ** 6 + 10
    memo = [False for _ in range(MAX)]
    for i in range(N):
        memo[A[i]] = True
        for j in range(A[i] * 2, MAX, A[i]):
            memo[j] = False
        if i - 1 >= 0 and A[i] == A[i - 1]:
            memo[A[i]] = False

    print(sum(memo))


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	count = 0
	a_max = A[-1]
	dp = [1]*a_max
	for a in A:
		point = dp[a-1]
		if point == 1:
			dp[a-1] = 2
			count += 1
			for ai in range(a*2,a_max+1,a):
				dp[ai-1] = 0
		elif point == 2:
			count -= 1
			dp[a-1] = 0
	print(count)






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
def D():
    N = int(input())
    A = list(map(int, input().split()))
    nums = Counter(A)
    if 1 in nums:
        if nums[1] > 1:
            print(0)
            return
        else:
            print(1)
            return
    n = max(A)
    dp = [True for i in range(n+1)]
    p = 2
    while (p <= n): 
        if (p in nums and dp[p] == True): 
            for i in range(p*2, n+1, p): 
                # print(i)
                dp[i] = False
        p += 1
    ans = 0
    for num in nums:
        if nums[num] == 1 and dp[num]:
            # print(num)
            ans += 1
    print(ans)

D()

Submission status: Accepted

Solution code:
N=int(input())
#5
A=sorted(map(int,input().split()))
#24 11 8 3 16

dp = [1]*max(A)
l = len(dp)

for a in A:
	if dp[a-1] == 1:
		dp[a-1] = 2
		for i in range(2*a, l+1, a):
			dp[i-1] = 0
	elif dp[a-1] == 2:
		dp[a-1] = 0

print(sum([1 for a in A if dp[a-1] != 0]))

Submission status: Accepted

Solution code:
#abc170d
n=int(input())
a=list(map(int,input().split()))
a.sort()
cnt=[0]*(a[-1]+1)
for x in a:
 for i in range(x,a[-1]+1,x):
  cnt[i]+=1
res=0
for x in a:
 if cnt[x]==1:
  res+=1
print(res)

Submission status: Accepted

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

b = [True for i in range(a[-1]+1)]

ans = 0

for i, j in enumerate(a):
    if b[j]:
        t = 1
        while j*t < len(b):
            b[j*t] = False
            t += 1
        
        if i == n-1:
            ans += 1
        elif j != a[i+1]:
            ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
import collections
c = collections.Counter(a)
a = list(set(a))
n = len(a)
a = sorted(a)
B = [True]*(a[-1]+1)
ans = 0
for i in range(n):
    if B[a[i]]:
        if c[a[i]] == 1:
            ans += 1
    j = 2
    while a[i]*j <= a[-1]:
        B[a[i]*j] = False
        j += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
if n == 1:
    print(1)
    exit()  
check_list = [0] * (10**6 + 2)
ans = 0
for i in range(n):
    tmp = a[i]
    while tmp <= a[-1]:
        check_list[tmp] += 1
        tmp += a[i]
for aa in a:
    if check_list[aa] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
sys.setrecursionlimit(10**6)

M = 10**6+5


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * M
    for i in range(n):
        if cnt[a[i]] != 0:
            cnt[a[i]] += 1
            continue

        for j in range(a[i], M, a[i]):
            cnt[j] += 1
    ans = 0
    for i in range(n):
        if cnt[a[i]] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

stdin = sys.stdin

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

n = ni()
a = na()
a.sort()
cnt = Counter(a)
elem = [True]*(a[-1]+1)

for i in a:
  for j in range(i*2,a[-1]+1,i):
    elem[j] = False
ans = 0
for v in a:
  if elem[v] == True and cnt[v] == 1:
    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:
n = int(input())
a = list(map(int,input().split()))
import collections
c = collections.Counter(a)
a = list(set(a))
n = len(a)
a = sorted(a)
B = [True]*(a[-1]+1)
ans = 0
for i in range(n):
    if B[a[i]]:
        if c[a[i]] == 1:
            ans += 1
        j = 2
        while a[i]*j <= a[-1]:
            B[a[i]*j] = False
            j += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
input = stdin.readline

N = int(input())
A_list = list(map(int, input().split()))
# ans_list =np.ones(N)
# A_list = np.array(A_list)

# for i in range(N-1):
#     for j in range(i+1,N):
#         if A_list[i] %  A_list[j] == 0:
#             ans_list[i] = 0
#             if (A_list[j] %  A_list[i] == 0):
#                 ans_list[j] = 0
#         elif(A_list[j] %  A_list[i] == 0):
#             ans_list[j] = 0
# print(int(np.sum(ans_list)))
A_set = list(set(A_list))
maxA =  A_set[-1]
dp = [1] * (( 10 ** 6) + 1)

cntli = [0] * (( 10 ** 6) + 1)
unique =[]
for i in A_list:
    cntli[i] += 1
for i in range((( 10 ** 6) + 1)):
    if cntli[i] == 1:
        unique.append(i)

for elem in A_set:
    for i in range(2 * elem,  10 ** 6 + 1, elem):
        dp[i] = 0

ans = 0
for i in unique:
    if not (dp[i] == 0):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def main():
    input()
    a = [int(i) for i in input().split()]
    a.sort()
    dp = np.zeros(a[-1] + 1, dtype=np.int)
    for ai in a:
        if dp[ai] == 0:
            dp[ai] = 1
            dp[ai * 2:a[-1] + 1:ai] = 2
        else:
            dp[ai] = 2
    # print(dp)
    print(len(dp[dp == 1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = [0]*(1000001)
for i in a:
    c[i] += 1
b = list(set(a))
ans = []
b.sort()

num = [True]*(1000001)

for i in range(len(b)):
    now = b[i]
    if num[now]:
        ans.append(now)
        for j in range(now, 1000001, now):
            num[j] = False


count = 0
for i in ans:
    if c[i] == 1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    A = sorted(list(in_nn()))

    maxA = max(A)
    ans = [True] * (maxA + 1)
    d = set()

    for i in range(N):
        if A[i] in d:
            ans[A[i]] = False
        for j in range(A[i] * 2, maxA + 1, A[i]):
            if not j:
                break
            else:
                ans[j] = False
        d |= {A[i]}

    count = 0
    for i in range(N):
        count += ans[A[i]]

    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    a.sort()
    b = 0
    dp = [True] * (a[-1] + 1)
    for ai in a:
        if not dp[ai]:
            continue
        for j in range(ai * 2, a[-1] + 1, ai):
            dp[j] = False
        if ai == b:
            dp[ai] = False
        b = ai
    print(sum(dp[ai] for ai in a))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
        for j in range(2*a[i], max_a+1, a[i]):
            flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)

Submission status: Accepted

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

max_a = max(a)
flag = [True for i in range(max_a+1)]

dup = set()
for i in range(n):
    if a[i] in dup:
        flag[a[i]] = False
    else:
        dup.add(a[i])
    for j in range(2*a[i], max_a+1, a[i]):
        flag[j] = False

ans = 0
for i in a:
    ans += flag[i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
d = {}
for a in A:
    d.setdefault(a,0)#setdefault(key,value):辞書の既存のkeyについては変更せず
    d[a] += 1       #新規のkeyにのみ新たなvalueで要素を追加できる   
#今は({A1:1,A2:1,...An:1}となっている)
A = sorted(set(A))#重複要素なくしてかつ昇順にする
t = [True] * (10 ** 6 + 1)#Aiの制約範囲最大までのTrueのリストを作る

for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a+a, 10 ** 6 + 1, a):#自分自身を含めないためのa+a
        t[i] = False
print(sum(1 for a in A if t[a]==True))

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    counter = Counter(A)
    A.sort()
    B = [True] * (10 ** 6 + 1)
    ans = 0
    for ai in A:
        if B[ai]:
            for i in range(ai, 10 ** 6 + 1, ai):
                B[i] = False
            if counter[ai] == 1:
                ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
MAX = 10 ** 6 + 10
cnt = [0] * MAX  # cntが1以上ならその数以下に約数が1個以上存在する(自分も含める)

for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for j in range(a, MAX, a):
        cnt[j] += 1
ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1
print(ans)