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 sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect


"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""


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

## 例外処理
if N == 1:
  print(1)
  exit()
elif N > 1 and A[0] == 1:
  if A[1] == 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
elif A[0] == A[-1]:
  print(0)
  exit()


MAXINT = int(1e6)
#MAXINT = int(10)
lst = [False for _ in range(MAXINT+1)]
for i in range(N):
  lst[A[i]] = True

pre = 0
for i in range(N):
  #print(i, lst, pre)
  if lst[A[i]]:
    if A[i] == pre:
      lst[A[i]] = False
      continue
    else:
      pre = A[i]
      j = 2 * A[i]
      while j <= MAXINT:
        lst[j] = False
        j += A[i]
    #print(i, lst)

solver = [i for i in range(MAXINT+1) if lst[i]]
ans = len(solver)
print(ans)
#print(lst)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
t = max(A)
K = [1]*(t+1)
before = -1
for i in A:
    if K[i] == 1:
        c = 2
        while(True):
            if i*c > t:
                break
            K[i*c] = 0
            c += 1
    if i == before:
        K[i] = 0
    before = i

ans = 0
for i in A:
    ans += K[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=sorted(list(map(int,input().split())))
c=Counter(A)
if 1 in A:
    if c[1]==1:
        print(1)
    else:
        print(0)
    exit()
n=max(A)
ans=[0]*(n+1)
for k,v in c.items():
    if v==1:
        ans[k]=1
for i in c.keys():
    t=i*2
    while t<=n:
        ans[t]=0
        t+=i
print(sum(ans))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def prime_factors(n):
    c = collections.Counter()
    while n > 1:
        for i in range(2, n + 1):
            if n % i == 0:
                c.update([i])
                n //= i
                break
    return c

def solve(N, As):
    As.sort()
    k = As[-1]
    data = [True for _ in range(k + 1)]
    count = collections.Counter(As)
    if count[1] >= 2:
        return 0

    ans = []
    done = set()
    for a in As:
        if count[a] == 1 and data[a]:
            ans.append(a)
        if a not in done:
            for n in range(a, len(data), a):
                data[n] = False
        if a == 1:
            break
    return len(ans)

#
# def solve(N, As):
#     As.sort()
#     count = collections.Counter(As)
#     past_primes = {}
#     past_primes_keys = {}
#     ans = []
#
#     for a in As:
#         prime = prime_factors(a)
#         success = True
#         if count[a] > 1:
#             success = False
#         if a == 1:
#             ans.append(a)
#             continue
#         if count[1] >= 1:
#             success = False
#
#         for k in prime.keys():
#             if k not in past_primes:
#                continue
#             if past_primes[k] <= prime[k]:
#                 another_check = past_primes_keys[k]
#                 for past_a in another_check:
#                     if a % past_a == 0:
#                         success = False
#                         break
#         # print(prime)
#         if success:
#             # print(a)
#             ans.append(a)
#
#         for k in prime.keys():
#             if k not in past_primes:
#                 past_primes[k] = prime[k]
#             past_primes_keys.setdefault(k, []).append(a)
#     print(ans)
#     return len(ans)

def dummy(N, R=100):
    import random
    return [random.randint(1, R) for _ in range(N)]

def slow_solve(N, As):
    ans = 0
    for i, a in enumerate(As):
        if all(i == j or a % b != 0 for j, b in enumerate(As)):
            ans += 1
    return ans

# for _ in range(10000):
#     for R in [10, 100, 1000]:
#         N = 10
#         d = dummy(N, R)
#         if (solve(N, d) != slow_solve(N, d)):
#             print("Out!!")
#             print(f"N = {N}")
#             print(f"As = {d}")
#             print(f"solve(N, As) = {solve(N, d)}")
#             print(f"slow_solve(N, As) = {slow_solve(N, d)}")
#             break

# assert(solve(5, [24, 11, 8, 3, 16]) == 3)
# assert(solve(3, [36, 36, 72]) == 0)
# assert(solve(10, [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]) == 5)
# assert(solve(5, [9, 9, 70, 76, 81]) == 2)
# assert(solve(5, [1, 9, 27, 35, 48]) == 1)
# assert(solve(5, [17, 18, 24, 48, 71]) == 4)
# assert(solve(10, [16, 27, 30, 36, 36, 41, 41, 70, 72, 91]) == 5)
# assert(solve(5, [2, 3, 5, 7, 11, 1000000]) == 5)

# print("OK")
if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    print(solve(N, As))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
d = [0]*(10**6+1)
a.sort()
for i in range(n):
    if d[a[i]]: continue
    cnt += 1
    if i != n-1 and a[i] == a[i+1]:
        cnt -= 1
    res = a[i]
    while res <= 10**6:
        d[res] = 1
        res += a[i]
print(cnt)

Submission status: Accepted

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

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

    A = list(map(int, input().split()))
    A. sort()
    Nmax = A[-1] + 1

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n=int(input())
A=list(map(int,input().split()))
A.sort()
m=10**6+10
C=[0]*m
C[0]=-1
ans=0
now=0
flag=0
for a in A:
    if now!=a:
        flag=0
        now=a
    if now==a and flag:
        flag=0
        ans-=1
        continue
    if C[a]==0:
        ans+=1
        flag=1
        j=a
        while j<m:
            C[j]=1
            j+=a

print(ans)

Submission status: Accepted

Solution code:

def main():

    import collections

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

    max_A = max(A_s)

    # CNT_A = collections.Counter(A_s)
    CNT_A = collections.Counter(A_s).most_common()
    CNT_A.sort()

    NG_list = [True for i in range(max_A)]
    cnt = 0

    
    for i in range(len(CNT_A)):
        counter = CNT_A[i][1]
        num = CNT_A[i][0]
        # num = A_s[i]

        index_num = num - 1

        if (counter > 1):
            NG_list[index_num] = False
            # continue

        if (NG_list[index_num] == True):
            cnt += 1
            NG_list[index_num] = False

        coef = 1
        while (True):
            coef += 1
            tmp_num = coef * num
            
            if (tmp_num <= max_A):
                NG_list[tmp_num - 1] = False
            else:
                break

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
M=max(a)
num=[0]*M
for x in a:
	num[x-1]+=1
for i in range(M):
	if num[i]>=2:
		num[i]=2
ret=num.copy()
for i in range(M):
	if num[i]:
		j=i+i+1
		while j<M:
			ret[j]=0 
			j+=i+1
	if num[i]==2:
		ret[i]=0
print(ret.count(1))

Submission status: Accepted

Solution code:


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

ma = max(A)
first = [0]*(ma+3)
seen = [False]*(ma+3)
seens = set()
for i in range(N):
    a = A[i]
    if first[a] == 0:
        seens.add(a)
        ans += 1
        for j in range(a, ma + 3, a):
            first[j] += 1
    elif first[a] == 1 and (a in seens):
        ans -= 1
        first[a] += 1
    else:
        first[a] += 1

    #
    # if not seen[a]:
    #     print(i+1,a)
    #     ans += 1
    # for j in range(a,ma+3,a):
    #     seen[j] = True

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    A.sort()
    ans = set()
    table = {i:-1 for i in range(1, 10 ** 6 + 1)}
    for a in A:
        table[a] = 0
    for a in A:
        if table[a] == 0 and cnt[a] == 1:
            ans.add(a)
        elif table[a] == 1:
            continue
        i = 2
        target = a
        while True:
            target = a * i
            if target > A[-1]:
                break
            if table[target] == 0:
                table[target] = 1
            i += 1
    print(len(ans))
if __name__ == "__main__":
    main()

Submission status: Accepted

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

max_num = max(a)

if a.count(1) == 1:
    print(1)
    exit()
if a.count(1) >= 2:
    print(0)
    exit()
a.sort()
d = {}

ans = 0



for i in range(n):
    if a[i] not in d.keys():
        ans += 1
        j = 1
        #for j in range(1,100):
        while(a[i]*j <= max_num):
            if j == 1:
                d[a[i]*j] = 1
            else:
                #if a[i]*j > max_num:
                #    break
                d[a[i]*j] = 0
            j += 1
    else:
        if d[a[i]] == 1:
            ans -= 1
            d[a[i]] = 2

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    answer = n
    chk = [0 for _ in range(a[-1] + 1)]
    for aa in a:
        chk[aa] += 1
    if a[0] == 1:
        answer = 0 if chk[1] - 1 else 1
    else:
        for i in range(a[-1] + 1):
            if chk[i]:
                if chk[i] - 1:
                    answer -= chk[i]
                for j in range(2 * i, a[-1] + 1, i):
                    answer -= chk[j]
                    chk[j] = 0
        answer = max(answer, 0)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    huru = [False] * (10 ** 6 + 1)
    visited = [False] * (10 ** 6 + 1)
    for i in range(n):
        if huru[a[i]]:
            continue

        if visited[a[i]]:
            huru[a[i]] = True
        tmp = a[i] * 2
        while tmp <= 10 ** 6:
            huru[tmp] = True
            tmp += a[i]
        visited[a[i]] = True

    ans = 0
    for i in range(n):
        if not huru[a[i]]:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import collections
from collections import defaultdict
n= int(input())
a= list(map(int, input().split()))
d=defaultdict(int)
v=[0]*(pow(10,6)+1)
a.sort()
ans=0
for i in a:
    d[i]+=1

for i in a:
    if v[i]==0:
        if d[i]==1:
            ans+=1
        x = pow(10, 6) // i
        for j in range(1,x + 1):
            v[i*j]=1
print(ans)

Submission status: Accepted

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

U = A[-1]+1
is_prime = [1]*U
cnt = [0]*U
depri = 0
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and is_prime[a]:
        depri += 1
    if is_prime[a]:
        used.add(a)
        for q in range(2*a, U, a):
            is_prime[q] = 0
print(len(used)-depri)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = set(a)
    ma = max(a)
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        t = a[i]
        if c[t] > 1 and t in ans:
            ans.remove(t)
            continue
        j = 2
        tmp = t*j
        while tmp <= ma:
            if tmp in ans:
                ans.remove(tmp)
            j += 1
            tmp = t*j
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()
di = Counter(A)
A.sort()

ans = 0
l = set()
for item in A:
    if di[item] > 1:
        if item not in l:
            for i in range(1,1000000//item+1):
                l.add(item*i)
        continue
    if item not in l:
        for i in range(1,1000000//item+1):
            l.add(item*i)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#8:47
MOD=10**9+7
INT_MAX=10**20+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [False for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
#################################################################################
n=int(input())
A=INPUT()
C=LIST_1D_ARRAY(10**6+1)
count=[0]*(10**6+1)
for i in range(n):
    C[A[i]]=True
    count[A[i]]+=1
for i in range(1,10**6+1):
    if C[i]==True:
        for j in range(2*i,10**6+1,i):
            C[j]=False
ans=0
for i in range(1,10**6+1):
    if C[i]==True and count[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
As=[0]*(10**6 + 1)
for i in range(N): 
    As[A[i]]+=1
count=N
for i in range(1,10**6 + 1):
    if As[i]:
        for j in range(i*2,10**6 + 1,i):
            if As[j]:
                count-=As[j]
                As[j]=0
for i in range(1,10**6 + 1):
    if As[i]>1:
        count-=As[i]
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
arr1 = [int(i) for i in input().split()]
arr = []
Dict = defaultdict(int)
for i in range(N):
    Dict[arr1[i]] += 1
arr = list(Dict.keys())
n = int(10 ** 6)
prime = [True for i in range(n + 10)]
for p in arr:
    if prime[p]:
        start = p+p
        for j in range(start, n + 1, p):
            prime[j] = False
count = 0
for i in arr:
    if prime[i] and Dict[i] == 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
N = int(input())
A = list(map(int,input().split()))
A.sort()
if N == 1:
    print(1)
else:
    is_prime = [True]*(10**6+1)
    is_prime[0] = False
    old = -1
    for i in range(N):
        a = A[i]
        if old == a:
            is_prime[a] = False
            continue
        if not is_prime[a]:
            old = a
            continue
        else:
            old = a
            if a*2 <= 10**6:
                for j in range(a*2,10**6+1,a):
                    is_prime[j] = False
                
    ans = 0
    for i in range(N):
        a = A[i]
        if is_prime[a] == True:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
c=0
d={}
f=[0]*(max(l)+1)
for i in l:
	if i in d:
		d[i]+=1
	else:
		d[i]=1
x=sorted(list(set(l)))
for i in x:
	if d[i]==1 and f[i]==0:
		c+=1
	for j in range(2*i,len(f),i):
		f[j]=1 

print(c)

Submission status: Accepted

Solution code:
def d_not_divisible():
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]

    a_max = max(A)
    appear = [0] * (a_max + 1)
    for a in A:
        appear[a] += 1
    count = 0
    for j in range(1, a_max + 1):
        if appear[j] == 0:
            continue
        if appear[j] == 1:
            count += 1
        for k in range(j * 2, a_max + 1, j):
            if appear[k] != 0:
                appear[k] = 0
    return count

print(d_not_divisible())

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=list()
for i in range(10**6+1):
    b.append(0)
for i in range(n):
    if b[a[i]]==0:
        j=1
        while j*a[i]<=10**6:
            b[j*a[i]]=1
            j+=1
        if (i==n-1 or a[i+1]!=a[i]):
            ans+=1
print(ans)

Submission status: Accepted

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

a.sort()

MAXN = a[-1]


divisors = [False for _ in range(MAXN + 1)]
answer = 0
apast = None
for i, ai in enumerate(a):
    if ai == apast:
        is_good = False
    elif i < n - 1 and ai == a[i + 1]:
        is_good = False
        m = 1
        while m * ai <= MAXN:
            divisors[m * ai] = True
            m += 1
    else:
        is_good = not divisors[ai]

        m = 1
        while m * ai <= MAXN:
            divisors[m * ai] = True
            m += 1

    if is_good:
        answer += 1

    apast = ai


print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p, t

P, T = eratosthenes(int(math.sqrt(10**6))+1)

def e(n):
    c = []
    for p in P:
        while n % p == 0:
            # c[p] += 1
            c.append(p)
            n //= p
        if n == 1:
            break
    if n != 1:
        # c[n] += 1
        c.append(n)
    return c


@mt
def slv(N, A):
    ans = 0
    A.sort()
    ac = Counter(A)
    for i in range(N):
        # print(i)
        a = A[i]
        if ac[a] >= 2:
            continue
        c = e(a)
        for j in range(len(c)):
            f = False
            for i in combinations(c, r=j):
                m = reduce(mul, i, 1)
                # error_print(a, m)
                if ac[m] >= 1:
                    # error_print('b', a)
                    break
            else:
                f = True
            if not f:
                break
        else:
            ans += 1

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # from random import randint
    # N = 2* (10**5)
    # A = [randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    c = Counter(a)
    used = set()
    m = 10**6 + 1
    cnt = [0]*m
    ans = 0
    for ai in a:
        if c[ai]>1:
            if ai not in used:
                used.add(ai)
                for i in range(ai, m, ai):
                    cnt[i] += 1
        else:
            if cnt[ai] == 0:
                ans += 1
                for i in range(ai, m, ai):
                    cnt[i] += 1
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
l = [int(x) for x in input().split()] + [1000001]
l.sort()
ans = 0
t = 0
M = [False] * 10 ** 6
for i in range(N):
    if not M[l[i]-1]:
        if l[i] != l[i+1]:
            ans += 1
        t = l[i]
        while t <= 10 ** 6:
            M[t-1] = True
            t += l[i]
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
li = [True for _ in range(0, 10**6 + 1)]
A = list(map(int, input().split()))
A.sort()
used = {}
for i in range(N):
    if A[i] not in used.keys():
        used[A[i]] = 1
    else:
        used[A[i]] += 1
ans = 0
for k in used.keys():
    if used[k] > 1:
        for j in range(k, 10**6 + 1, k):
            li[j] = False
for i in range(N):
    if li[A[i]] and used[A[i]] == 1:
        ans += 1
    else:
        continue
    for j in range(A[i], 10**6 + 1, A[i]):
        li[j] = False
print(ans)

Submission status: Accepted

Solution code:
def main():

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

    d = dict()
    for v in A:
        d[v] = d.get(v, 0) + 1
    if 1 in d:
        if d[1] == 1: return 1
        else: return 0

    A = list(set(A))
    A.sort()
    s = set()
    ans = 0
    for i in range(len(A)):
        if d[A[i]] == 1:
            if A[i] not in s:
                ans += 1
        k = 1
        while k * A[i] <= A[-1]:
            s.add(k * A[i])
            k += 1

    return ans


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

Submission status: Accepted

Solution code:
from collections import Counter
 
N = int(input())
A_raw = Counter(list(map(int, input().split())))
A = [x[0] for x in A_raw.items() if x[1] == 1]
A.sort()
B = [x[0] for x in A_raw.items() if x[1] > 1]
B.sort()
seen = [0]*(1000000+1)
for b in B:
    if seen[b] == 0:
        x = b
        j = 1
        while x <= 1000000:
            seen[x] = 1
            j += 1
            x = b*j
ans = 0
for a in A:
    if seen[a] == 0:
        ans += 1
        x = a
        j = 1
        while x <= 1000000:
            seen[x] = 1
            j += 1
            x = a*j
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n!=1 and len(set(a))==1:
  print(0)
  exit()
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
if n!=1 and min(a)>max(a)/2:
  ct=0
  for i in range(len(l)):
    if l[i]==1:
      ct+=1
  print(ct)
  exit()
d={}
ans=0
for i in range(n):
  x=a[i]
  if x not in d:
    if l[a[i]]==1:
      flag=1
      for j in range(1,int(x**0.5)+2):
        if x%j==0:
          if x!=j and l[j]>0:
            flag=0
            break
          if x!=x//j and x%(x//j)==0 and l[x//j]>0:
            flag=0
            break
      if flag==1:
        ans+=1
        d[x]=1
      else:
        d[x]=0
  else:
    ans+=d[x]
print(ans)

Submission status: Accepted

Solution code:
bun = input()
lst = input().split()
nlst = []
for i in range(1000000):
    nlst.append(0)
for i in range(len(lst)):
    nlst[int(lst[i])-1] += 1
for i in range(1000000):
    if nlst[i] > 0:
        for j in range((i+i+1),1000000,i+1):
            nlst[j] = 0
count = 0
for i in range(1000000):
    if nlst[i] == 1 :
        count += 1
print(count)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
box = [1] * (a[-1] + 1)
ans = 0
if n == 1:
    print(1)
else:
    for i in range(n):

        if i == 0:
            for j in range(a[-1] // a[i]):
                box[a[i] * (j + 1)] = 0
            if a[1] != a[0]:
                ans += 1
        elif i == n - 1:
            if box[-1] == 1:
                ans += 1
        else:
            if a[i] != a[i - 1] and a[i] != a[i + 1]:
                if box[a[i]] == 1:
                    ans += 1
                    for j in range(a[-1] // a[i]):
                        box[a[i] * (j + 1)] = 0
            elif a[i] == a[i + 1]:
                for j in range(a[-1] // a[i]):
                    box[a[i] * (j + 1)] = 0
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect
from collections import defaultdict

def solve(data):
    is_unique = defaultdict(lambda: 0)
    times = [False] * (data[-1] + 3)
    for d in data:
        is_unique[d] += 1
        v = d * 2
        #print('v') # debug
        #print(v) # debug
        while v < len(times):
            times[v] = True
            v += d
    #print('times') # debug
    #print(times) # debug
    #print('is_unique') # debug
    #print(is_unique) # debug
    ans = 0
    for d in data:
        if is_unique[d] > 1:
            continue
        if times[d] == False:
            ans += 1
    return ans

if __name__ == '__main__':
    n = int(input())
    data = list(map(int, input().split()))
    data.sort()
    #print('data') # debug
    #print(data) # debug
    ans = solve(data)
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
A=n1()

A.sort()
m=A[-1]

d=defaultdict(int)
d2=defaultdict(int)

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

ans=0
for a in A:
    if d[a]==0:
        if d2[a]<=1:
            ans+=1
        i=a
        while i<=m:
            d[i]=1
            i+=a
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

maxA = max(A)
era = [0]*(maxA+1)

for i in range(0,N,1):
    if era[A[i]]==0:#脱落
        era[A[i]]=1#除＋カウント
    else:
        era[A[i]]=-1#除には参加カウントしない

ans = 0

for i in range(1,maxA+1,1):
    if era[i]==1:
        for j in range(2*i,maxA+1,i):
            era[j]=0
        ans+=1
    elif era[i]==-1:
        for j in range(2*i,maxA+1,i):
            era[j]=0

print(ans)

Submission status: Accepted

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

def multi(n):
    i = 2
    while True:
        yield n * i
        i += 1

d = {}
for a in an:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1

anmax = 10**6
# 小さい順に倍数要素を消しこんでいく.
for n in sorted(d):
    if n not in d:
        continue

    for m in multi(n):
        if m > anmax:
            break

        if m in d:
            del d[m]

    # 同じ値が複数ある場合は自分自身も消す.
    if d[n] > 1:
        del d[n]

#print(d)
print(len(d))

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    d_A = Counter(A)
    s = sorted(d_A.keys())
    if s[0] == 1:
        print((d_A[1] == 1)*1)
        return
    
    is_d = [0]*(2*10**6)

    for s_t in s:
        lim = 10**6 // s_t +1
        for i in range(1,lim):
            is_d[i*s_t] +=1
    
    ans = 0
    for s_t in s:
        if (d_A[s_t] == 1) and (is_d[s_t]==1):
            ans+=1
    print(ans)


        

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import  math
from heapq import *
import fractions
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


N=int(input())
A=nl()
A.sort()
A_MAX=10**6+5
p_l=[0]*(A_MAX)
c=0
if(len(A)==1):
    print(1)
    sys.exit(0)

for i in range(len(A)):
    if(p_l[A[i]]!=0):
        continue
    for k in range(A[i],A_MAX,A[i]):
        if(p_l[k]):
            continue
        p_l[k]=1
    if(i<(len(A)-1) and A[i]==A[i+1]):
        continue
    c+=1
    

print(c)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A=sorted(A)
up=max(A)
table=[0]*(up+1)
for i in range(n):
    table[A[i]]+=1
aset=set(A)

for i in range(len(aset)):
    if table[A[i]]>0:
        j=2
        while A[i]*j<up+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=-1
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)