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
input = sys.stdin.readline
from collections import Counter

def main():
    n = int(input())

    A = sorted(map(int, input().split()))
    counter = Counter(A)

    ans = 0
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a

        if counter[a] == 1:
            ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()

    dp = [True] * (max(A) + 1)
    tmp = 0
    for a in A:
        if a == tmp:
            dp[a] = False
            continue
        tmp = a
        i = 2
        while a*i < len(dp):
            dp[a*i] = False
            i += 1
    
    ans = 0
    for a in A:
        if dp[a] == True:
            ans += 1
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
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)]
mod = 1000000007

n = I()
A = sorted(LI())
ans = 0
cnt = Counter(A)
m = max(A) + 1
B = [0] * (10 ** 6 + 1)
for a in A:
    if B[a] == 0 and cnt[a] == 1:
        ans += 1
    for i in range(a * 2, m, a):
        B[i] = 1


print(ans)

Submission status: Accepted

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

dlen = A[-1]+3
d = [True]*dlen
for a in A:
    if d[a]:
        for i in range(a*2, dlen, a):
            d[i] = False

res = 0
for i in range(N):
    if i > 0:
        if A[i] == A[i-1]:
            continue
    if i < N-1:
        if A[i] == A[i+1]:
            continue
    if d[A[i]]:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

def main():
    n = int(input())

    A = sorted(map(int, input().split()))
    counter = Counter(A)

    if not A:
        print(0)
        return

    ans = 0
    maxi = max(A)
    cache = set()
    for a in A:
        if a in cache:
            continue

        x = a
        while x <= maxi:
            cache.add(x)
            x += a

        if counter[a] == 1:
            ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)
from collections import defaultdict
from bisect import bisect_left


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization(n, primes):
    """
    nの素因数分解を求める
    """
    prime_factors = defaultdict(int)
    if n < 2:
        return prime_factors
    for p in primes:
        if p * p > n:
            break
        while n % p == 0:
            prime_factors[p] += 1
            n //= p
    if n > 1:
        prime_factors[n] = 1
    return prime_factors


def sieve(n):
    """
    n以下の素数を昇順に列挙する
    """
    is_prime = [True for i in range(n+1)]
    primes = []
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return primes


def solve(N, A):
    A.sort()
    AMAX = max(A)
    ans = 0
    is_div = [True for i in range(AMAX+1)]
    for i in range(N):
        a = A[i]
        if is_div[a]:
            if not ((i > 0 and A[i] == A[i-1]) or (i < N-1 and A[i] == A[i+1])):
                ans += 1
            for j in range(a, AMAX+1, a):
                is_div[j] = False
    return ans


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

n = int(input())
A = sorted(map(int, input().split()))
U = 10**6
B = [0]*(U+1)
C = Counter(A)
ans = 0
for a in A:
  if B[a]:
    continue
  if C[a] == 1:
    ans += 1
  for j in range(a, U+1, a):
    B[j] = 1
print(ans)

Submission status: Accepted

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

As.sort()
# print(As)

all_nums = [0] * (As[-1] + 1)

for A in As:
    all_nums[A] += 1
#print(all_nums)
dup = 0

for i, num in enumerate(all_nums):
    if num == 0: #その数が一つもないなら無視
        continue
    if num > 1: #同じ数が複数ある場合はあとで除くためにカウント
        dup += num
    j = 2
    while i * j <= As[-1]:
        all_nums[i*j] = 0
        j += 1
    #print(all_nums)

print(sum(all_nums)-dup)

Submission status: Accepted

Solution code:
# エラトステネスの篩

N = int(input())
A = sorted(map(int, input().split()))
maxA = A[N - 1]
dp = [0] * (maxA + 1)

for i in range(len(A)):
    cursor = A[i]
    while cursor <= maxA:
        dp[cursor] += 1
        cursor += A[i]

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

print(ans)

Submission status: Accepted

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

import numpy as np
from numba import njit


@njit('i8(i4[::1],)', cache=True)
def f(A):
    count = np.zeros((A.max() + 1))
    for a in A:
        if count[a] > 1:
            continue
        count[::a] += 1

    ret = 0
    for a in A:
        ret += count[a] == 1

    return ret

N = int(input())
A = np.array(readline().split(), np.int32)

print(f(A))

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
a.sort()
d = defaultdict(int)
for ai in a:
    d[ai] += 1

m = a[-1]
x = [True for _ in range(m + 1)]

ans = 0
c = defaultdict(bool)
for ai in a:
    if x[ai] and d[ai] == 1:
        ans += 1
    if not c[ai]:
        c[ai] = True
        for j in range(2 * ai, m + 1, ai):
            x[j] = False
print(ans)

Submission status: Accepted

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

A = sorted(A)
C = Counter(A)
S=set(A)

dp=[True]*(A[-1]+1)

ans=0
for i in range(1,A[-1]+1):
    if dp[i]:
        if i in S:
            for j in range(i,A[-1]+1,i):
                dp[j]=False
            if C[i]==1:
                ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def divisors(n):
    # 約数列挙

    divisors = []

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

    return set(divisors)


def main():
    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    counter = Counter(a)
    a.sort()
    mx = max(a)

    ok = [True] * (mx + 1)

    for x in a:
        for y in range(2 * x, mx + 1, x):
            ok[y] = False

    ans = 0
    prev = -1
    for key, val in counter.items():
        if val > 1:
            pass
        else:
            if ok[key]:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=0
A.sort()

f=[0]*1000005

for i in A:
    f[i]+=1

for i in range(1,1000001,1):
    if f[i]==0:
        continue
    j=i+i
    while j<=1000000:
        f[j]+=f[i]
        j=j+i

for i in A:
    if f[i]==1:
        ans+=1


print(ans)

Submission status: Accepted

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

for a in A:
    A_div[a] += 1
    if A_div[a] == 1:
        for j in range(2 * a, 10 ** 6 + 1, a):
            A_div[j] += 100

print(A_div.count(1))

Submission status: Accepted

Solution code:
N=int(input())
alist=list(map(int,input().split()))
max_a=max(alist)

exclude_set=set()
tlist=[False]*(max_a+1)
for a in alist:
  if tlist[a]:
    exclude_set.add(a)
  else:
    tlist[a]=True
#print(tlist)

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
if N == 1:
    print(1)
elif A[0] == 1 and A[1] == 1:
    print(0)
elif A[0] == 1:
    print(1)
else:
    Eratos = [False]*1000001
    ans = 0
    for i in range(N):
        if Eratos[A[i]]:
            ans += 1
        else:
            if i < N-1 and A[i] == A[i+1]:
                ans += 1
            for j in range(A[i], 1000001, A[i]):
                Eratos[j] = True
    print(N-ans)

Submission status: Accepted

Solution code:
import collections


def main():
    n = int(input())
    al = list(map(int, input().split()))
    al.sort()

    dp = [1]*(10**6+1) 
    for a in al:
        if dp[a] >= 0:
            dp[a] -= 1
            for i in range(2,10**6//a + 1):
                dp[a*i] -= 2
    
    ans = 0
    for a in al:
        if dp[a] >= 0: ans+=1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A.sort()

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

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

ans = 0

for a in A:
    if B[a] == False:
        c = 1
        i = a * c
        while i <= 10 ** 6:
            B[i] = True
            c += 1
            i = a * c
        if D[a] == 1:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
A = [True]*(10**6+1)

for i in range(0, N):
    if not A[S[i]]:
        continue
    if 0 < i:
        if S[i-1] == S[i]:
            continue
    if i < N-1:
        if S[i] == S[i+1]:
            for j in range(1, 10**6//S[i]+1):
                A[S[i]*j] = False
            continue
    ans += 1
    for j in range(1, 10**6//S[i]+1):
        A[S[i]*j] = False

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    a1 = {}
    for i in range(len(a)):
        if a[i] in a1:
            a1[a[i]] += 1
        else:
            a1[a[i]] = 1
    a = sorted(list(a1.keys()))
    ans = [1] * a[-1]

    for i in a:
        if ans[i-1] == 1:
            for j in range(i-1, len(ans), i):
                ans[j] = 0
            ans[i-1] =1
    ans1 = 0
    for i in a:
        if a1[i] == 1:
            ans1 += ans[i-1]
    print(ans1)
resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
m = max(A)+10
dp = [0] * m

for x in A:
    dp[x] += 1

ans = 0
for i in range(1, m):
    if dp[i]:
        if dp[i] == 1:
            ans += 1
        for j in range(i, m, i):
            dp[j] = 0
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10 ** 6 + 1)
for a in A:
    if P[a] == 0:
        for i in range(10 ** 7):
            x = a * i
            if x > 10 ** 6:
                break
            P[x] = 1
        if cnt[a] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = Counter(list(map(int,input().split(' '))))
ans = 0
m = max(A.keys())
L = [1]*(10**6+1)
for i in sorted(A.keys()):
    if not L[i]:
        continue
    if A[i] == 1:
        ans += 1
    for j in range(i,m+1,i):
        L[j] = 0
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

from collections import Counter as cnt
aaa = dict(cnt(a))

ma = max(a)
dp = [True for i in range(ma+1)]

for i in a:
    if dp[i]:
        mul = i*2
        while mul<=ma:
            dp[mul] =False
            mul += i

mans = 0
for i,v in aaa.items():
    if dp[i] & (v == 1) :
        mans+=1

print(mans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = max(A)
memo = [0]*(M+1)
i = 0
while i < N:
  a = A[i]
  memo[a] += 1
  x = a+a
  while x <= M:
    memo[x] += 2
    x += a
  i += 1
print(sum([1 if m == 1 else 0 for m in memo]))

Submission status: Accepted

Solution code:
cnt = [0]*(10**6+1)
conv = [0]*(10**6+1)

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

for i in A:
    cnt[i] += 1

ans = 0##割り切れないものの数
for i in range(1,10**6+1):
    if cnt[i] == 1 and conv[i] == 0:##配列に1回のみ出現&&他の倍数でない
        ans += 1 
    if conv[i] == 1 or cnt[i] == 0:
        continue
    for j in range(10**6//i+1):##その数の倍数をメモ
        conv[i*j] = 1

print(ans)

Submission status: Accepted

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

for a in A:
  B[a]+=1
  if B[a]==1:
    for n in range(2*a,10**6+1,a):
      B[n]+=10

print(B.count(1))

Submission status: Accepted

Solution code:
M = 10 ** 6 + 1
N = int(input())
A = list(map(int, input().split()))
 
A.sort()
not_divisible = [True] * (M)
# print(A)

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:
def solve():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    numbers = [0] * (10 ** 6 + 1)
    for i in a:
        numbers[i] += 1
        if numbers[i] == 1:
            for j in range(2 * i, len(numbers), i):
                numbers[j] += 2
    print(numbers.count(1))








if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

counter = 0
for i in range(1, 10**6+1):
    if if_can_divide[i] == 1 or exist_in_input[i] == 0:
        continue

    if exist_in_input[i] == 1:
        counter += 1

    for j in range(0, 10**6+1, i):
        if_can_divide[j] = 1

print(counter)

Submission status: Accepted

Solution code:
from collections import Counter


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

flags = [True] * (a[-1] + 1)

for e in a:
    for mul in range(2, a[-1] // e + 1):
        flags[e * mul] = False

print(sum([flags[a[i]] and c[a[i]] == 1 for i in range(n)]))

Submission status: Accepted

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

ans = 0
dp = [0] * (a[-1] + 1)

for i in range(n):
    tmp = a[i]
    while tmp <= a[-1]:
        dp[tmp] += 1
        tmp += a[i]

for i in a:
    if dp[i] == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

a.sort()
a_max = a[-1]
ban = [0]*(a_max+1)

count = 0
for i in range(n):
    if ban[a[i]]:
        continue
    else:
        if i == n-1 or a[i+1] != a[i]:
            count += 1
        x = a[i]
        while x <= a_max:
            ban[x] = 1
            x += a[i]
#print(ban)
print(count)

Submission status: Accepted

Solution code:
# print('input >>')
N = int(input())
As = list(map(int,(input().split())))

As.sort()
# print(As)

all_nums = [0] * (As[-1] + 1)

for A in As:
    all_nums[A] += 1

dup = 0

for i, num in enumerate(all_nums):
    if num == 0:
        continue
    if num > 1:
        dup += num
    j = 2
    while i * j <= As[-1]:
        all_nums[i*j] = 0
        j += 1
    # print(all_nums)

print(sum(all_nums)-dup)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [True for _ in range(a[-1] + 1)]
pre = -1
for i in a:
    if i == pre:
        dp[i] = False
        continue
    for j in range(i * 2, a[-1] + 1, i):
        dp[j] = False
    pre = i
ans = 0
for i in a:
    if dp[i] == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
mx = max(a)
flag = [True]*(mx+1)
c = Counter(a)
a.sort()
ans = 0
for i in range(n):
    if flag[a[i]]:
        if c[a[i]] == 1: ans += 1
        for j in range(2*a[i],mx+1,a[i]): flag[j] = False
print(ans)

Submission status: Accepted

Solution code:
##想定解

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

from collections import Counter

ca=Counter(a)

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


for ai in ca:
    nn[ai]=ca[ai]

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
A.sort()
count = defaultdict(lambda:0)
for a in A:
    count[a] += 1
dp = [True]*(A[-1]+1)

ans = 0
for a in A:
    if dp[a] and count[a]==1:
        ans += 1
    for i in range(1,len(dp)):
        if a*i>A[-1]:
            break
        dp[a*i] = False

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

m = max(A) + 1
ok = [True] * m
ctr = Counter(A)
ans = 0
for a in sorted(A):
    if ok[a] and ctr[a] == 1:
        ans += 1
        
    for j in range(2 * a, m, a):
        ok[j] = False
            
print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    countA = Counter(A)
    A.sort()
    l = [True for _ in range(A[-1] + 1)]
    for i in range(N):
        j = 2
        while A[i] * j <= A[-1]:
            l[A[i] * j] = False
            j += 1
    cnt = 0
    for a in A:
        cnt += (l[a] and countA[a] == 1)
    print(cnt)




# 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:
import collections

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

    _max = 10 ** 6 + 1

    c = collections.Counter(A)

    ok_flag = [True] * _max   
    uniq_A = list(c.keys())
    uniq_A.sort()
    ans = 0

    for a in uniq_A:
        if ok_flag[a]:
            if c[a] == 1:
                ans += 1

            for i in range((_max - 1) // a + 1):
                ok_flag[a*i] = False
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

l = [0]*1000001

A.sort()

for a in A:
    if l[a] == 0:
        l[a] = 1
        tmp = 2
        while tmp*a <= 1000000:
            l[tmp*a] = 2
            tmp+=1
    elif l[a] == 1:
        l[a] = 2

ans = 0
for a in A:
    if l[a] != 2:
        ans += 1

print(ans)

Submission status: Accepted

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

UB = 10**6

cand = set(range(1, UB + 1))
used = set()
for a in A:
    if a in used:
        cand.discard(a)
        continue
    i = 2
    while a * i <= UB:
        cand.discard(a * i)
        i += 1

    used.add(a)

count = sum(a in cand for a in A)
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mx = max(A)+1
B = [0]*(mx)
dic = defaultdict(int)
for a in A:
  dic[a] += 1

A = sorted(list(set(A)))
ans = 0
for a in A:
  if B[a] == 0:
    if dic[a] == 1:
      ans += 1
  for i in range(a, mx, a):
    B[i] += 1

print(ans)

Submission status: Accepted

Solution code:
M=10**6+1
_,*l=map(int,open(0).read().split())
b=[0]*M
for i in l: b[i]+=1
a=[]
for i in sorted(l):
  if b[i]:
    if b[i]==1: a+=[i]
    for j in range(i,M,i): b[j]=0
print(len(a))

Submission status: Accepted

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    A.sort()

    ans = 0
    M = max(A)
    dp = [True]*(M+1)
    for x in A:
        for xx in range(x+x, M+1, x):
            dp[xx] = False
    for x in A:
        if d[x] == 1 and dp[x]:
            ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
import math
def sieve(n, done):
    for i in range(n, 10**6+1, n):
        done[i] = 1

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

ans = 0
done = [0] * (10 ** 6 + 1)

for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        if i > 0 and a[i] == a[i-1]:
            continue
        sieve(num, done)
        continue
    
    if not done[num]:
        sieve(num, done)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
import collections
n = int(input())
a = [int(i) for i in input().split()]
dic = collections.defaultdict(int)
for i in range(n):
    dic[a[i]] += 1
a = [i for i in dic.keys() if dic[i] == 1]
b = [i for i in dic.keys() if dic[i] >= 1]

ls = [0] * (10**6)
for i in range(len(b)):
    tmp = b[i]
    cnt = 2
    while True:
        tmp = b[i] * cnt
        if tmp > 10**6:
            break
        ls[tmp-1] = 1
        cnt += 1

ans = 0
if len(a):
    for i in range(len(a)):
        if ls[a[i]-1] == 0:
            ans += 1
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys

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


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


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    one = A.count(1)
    if one == 1:
        print(1)
        return
    if 2 <= one:
        print(0)
        return
    
    counter = [0] * (10 ** 6 + 1)
    for ai in A:
        for m in range(ai, 10 ** 6 + 1, ai):
            counter[m] += 1
    
    ans = 0
    for ai in A:
        if counter[ai] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import Counter 

def main():
    n = int(input())
    a = list([int(t)for t in input().split()])
    c = Counter(a)
    checker = [False]*(10**6+1)
    times = [False]*(10**6+1)

    for a_i in a:
        checker[a_i] = True
    ans = 0
    for i in range(1,10**6+1):
        if times[i]:
            continue
        if not checker[i]:
            continue
        if checker[i] and c[i]==1:
            ans+=1
        for j in range(i,10**6+1,i):
            times[j] = True
        
    print(ans)
            
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
MAX = 10 ** 6 + 1
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * MAX
f = [True] * MAX
for a in A:
    cnt[a] += 1
    if not f[a] or cnt[a] > 1:
        continue
    for j in range(2 * a, MAX, a):
        f[j] = False
res = 0
for a in A:
    if f[a] and cnt[a] == 1:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
A = LI()
A = sorted(A)

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

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

B = [0]*(10**6+1)
C = [0]*(10**6+1)
for i in range(len(A)):
    if B[A[i]] == 0:
        C[A[i]] = 1
    for j in range(A[i]*2,10**6+1,A[i]):
        B[j] = 1

from collections import Counter

c = Counter(A)

for i in c.keys():
    if c[i] >= 2:
        C[i] = 0

print(sum(C))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = [0 for _ in range(10 ** 6 + 1)]
    for a in A:
        counter[a] += 1
    searched = [0 for _ in range(10 ** 6 + 1)]
    ans = 0
    for i in range(1, 10 ** 6 + 1):
        if counter[i] == 0:
            continue
        if searched[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1, ((10 ** 6) // i) + 1):
            searched[i * j] = 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

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

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

C = Counter(A)
D = []
A = []
for c in C:
  A.append(c)
  if C[c] != 1:
    D.append(c)
D.sort()
A.sort()
    
dp = [0 for i in range(A[-1]+2)]

for x in A:
  k = 2
  while k*x <= A[-1]+1:
    dp[k*x] = 1
    k += 1
ans = 0
for x in A:
  if dp[x] == 0 and x not in D:
    ans += 1
print(ans)