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:
n = int(input())
l = list(map(int,input().split()))

num = max(l)+1
rcd = [0 for _ in range(num)]

for v in l:
    rcd[v] += 1

unq = []
for w in range(num):
    if rcd[w] == 1:
        unq.append(w)
#print(unq)

rcd = [0 for _ in range(num)]
l = set(l)
for x in l:
    for y in range(2*x, num, x):
        rcd[y] = 1
#print(rcd)

ans = 0
for z in unq:
    if rcd[z] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    a_max = a[-1]
    is_divisible = [True]*(a_max+1)
    ans = 0
    is_divisible[0]= False
    el_old = 0
    for el in a:
        if is_divisible[el]:
            if el == el_old:
                ans-=1
                is_divisible[el] = False
                continue
            ans +=1
            k = 2
            while k*el <= a_max:
                is_divisible[k*el] = False
                k+=1
        el_old = el
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
remain = [0 for i in range(max(a) + 1)]
for ai in a:
    remain[ai] += 1
res = 0
max_a = max(a)
for i in range(1, max_a + 1):
    if remain[i] == 1:
        res += 1
    if remain[i]:
        for j in range(i * 2, max_a + 1, i):
            remain[j] = 0
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
c=[0]*8**7
for a in input().split():
    c[int(a)] += 1
i=r=0
for t in c:
    if t:
        c[::i]=[0]*-(-8**7//i)
    i+=1
    r+=t==1
print(r)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
cnt = [0] * (10**6 + 1)

dic = Counter(a)

for i in set(a):
    if 1 < dic[i]:
        cnt[i] += 1
        
a = list(set(a))
a_max = max(a)
for i in a:
    for j in range(1, 10**6 + 1):
        if a_max < i * j:
            break
        
        cnt[i * j] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n = inp()
a = inpl()
c = Counter(a)
a.sort()
s = set()
res = 0
for x in a:
    if x in s:
        continue
    if c[x] == 1:
        res += 1
    b = 1
    while b*x <= 10**6:
        s.add(b*x)
        b += 1
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
bs = [True] * (A[-1] + 1)
bs[0] = False
last = None
for a in A:
    if bs[a]:
        start = 2 * a if a != last else a
        for j in range(start, A[-1] + 1, a):
            bs[j] = False
    last = a
print(len({a for a in A if bs[a]}))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = [True] * (a[-1] + 1)
memo = -1
for i in a:
    if memo == i:
        flag[i] = False
        continue
    memo = i
    tmp = 2 * i
    while tmp <= a[-1]:
        flag[tmp] = False
        tmp += i
ans = 0
for i in a:
    if flag[i]: ans += 1
print(ans)

Submission status: Accepted

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

num = 0

a_max = max(as_)
a_valid_map = [True] * (a_max + 1)
for i in range(len(as_) - 1):
    a = as_[i]
    if a_valid_map[a]:
        for j in range(a_max // a + 1):
            a_valid_map[a * j] = False
        if a != as_[i + 1]:
            num += 1
if a_valid_map[a_max]:
    num += 1

print(num)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    pre_A = -1
    dp = [True for i in range(A[-1]+1)]
    for i in range(N):
        if pre_A != A[i]:
            for j in range(2, A[-1]+1):
                x = j*A[i]
                if x <= A[-1]:
                    dp[x] = False
                else:
                    break
            pre_A = A[i]
        else:
            dp[A[i]] = False

    count = 0
    for i in range(N):
        if dp[A[i]]:
            count += 1
    print(count)

resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_max = A[N-1]

boo = [1 for _ in range(A_max +1)]
tmp = A[0] 
kosuu = 2
while tmp * kosuu <= A_max:
    boo[tmp * kosuu] = 0
    kosuu += 1
pre = tmp
for i in range(1,N):
    tmp = A[i]
    if tmp == pre:
        boo[tmp] = 0
    else:
        kosuu = 2
        while tmp * kosuu <= A_max:
            boo[tmp * kosuu] = 0
            kosuu += 1
        pre = tmp
        
total = 0
for x in A:
    total += boo[x]
print(total)

Submission status: Accepted

Solution code:
def main():
    s = [input() for l in range(2)]
    N, A = int(s[0]), [int(x) for x in s[1].split()]
    """
    results = []

    for i in range(0, (N), 1):
        flag = 0
        for j in range(0, (N), 1):
            if i == j:
                pass
            else:
                if A[i] % A[j] == 0:
                    flag = 1
                    break
                else:
                    pass
        if flag == 1:
            results.append(0)
        else:
            results.append(1)
    cnt = 0
    for x in results:
        if x == 1:
            cnt += 1
    print(cnt)
    """
    # 最大値
    maxA = max(A)
    # 要素の個数を管理
    C = {a: 0 for a in A}
    # 同じ要素が複数ある時点で必ず割り切れる
    # c[a] > 1なら無視できるよ
    for a in A:
        C[a] += 1
    # D
    D = {a: 0 for a in A}
    for a in A:
        if C[a] > 0:
            t = 2
            while a * t <= maxA:
                D[a*t] = 1
                t+= 1

    ans = 0
    for a in A:
        # 重複なし&約数なし
        if C[a] == 1 and D[a] == 0:
            ans += 1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
max_a = a[-1]

q = [0] * (max_a + 1)
for i in a:
    if q[i] == 1 or q[i] == -1:
        q[i] = -1
        continue
    for j in range(2*i, max_a+1, i):
        q[j] = -1
    q[i] = 1

total = 0
for i in q:
    if i == 1:
        total += 1
print(total)

Submission status: Accepted

Solution code:
n = int(input()) #このnは使わない
*A, = map(int, input().split())
maxA = max(A)

# 連想配列 [key : value]
# C[a : count]
C = {a : 0 for a in A}
#要素を見つけるたびに1増える
#重複がある場合はC[a] >= 2になる
#例えば5が4つ見つかると C[5] = 4
for a in A:
    C[a] += 1


D = {a : 0 for a in A}
#Aの数値をkeyとして扱う
for a in A:
    if C[a] > 0:
        t = 2
        while a*t <=maxA:
            #aの倍数にフラグを立てる
            # D[2]が存在する場合, D[4]やD[6]は約数が存在することになる
            D[a*t] = 1
            t += 1

ans = 0
for a in A:
    # 重複がないもので,約数が存在しないものが答え
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Submission status: Accepted

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

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

if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

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

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return ret
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set(divisors(i))
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i)

print(ans)

Submission status: Accepted

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

limit = max(A) + 1

dp = [True] * (limit + 1)
d = {}

for i in A:
    p = 2
    while i*p<=limit:
        dp[i*p] = False
        p += 1
    d.setdefault(i, 0)
    d[i] += 1

ans = []
for i in A:
    if dp[i] and d[i] == 1:
        ans.append(i)
print(len(ans))

Submission status: Accepted

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

count = Counter(lista)
lista.sort()

M = 1000001
P = [0] * (M+1)
ans = 0

for i in lista:
    if P[i] == 0:
        for j in range(M+1):
            x = i * j
            if x > M:
                break
            P[x] = 1
        if count[i] == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = 5
ARR = [24, 11, 8, 3, 16]

N = 4
ARR = [5, 5, 5, 5]

N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):
    krr = [0 for i in range(1, 1000007)]

    for i in range(n):
        start = arr[i]

        if krr[start] > 0:
            krr[start] = 2
            continue

        for j in range(start, 1000006, start):
            krr[j] += 1

    result = 0
    for i in range(n):
        if krr[arr[i]] == 1:
            result += 1

    print(result)


calculate(N, ARR)

Submission status: Accepted

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


from collections import Counter
def Main(N, A):
    A.sort()
    amax = A[-1]+1
    d = {}
    for i in range(1, amax):
        d[i] = 0
    for a in A:
        i = 1
        while a*i < amax:
            d[a*i] += 1
            i += 1
    ans = 0
    for a in A:
        if d[a] == 1:
            ans += 1
    return ans

print(Main(N, A))

Submission status: Accepted

Solution code:

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

    m = max(A) + 1
    dp = [0] * m

    for a in sorted(A):
        if dp[a] != 0:
            dp[a] = 2
            continue
        for i in range(a, m, a):
            dp[i] += 1

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
aL = sorted(list(map(int, input().split(" "))))
# aL = sorted(list(set(aLP)))

dp = [False for _ in range(1000001)]

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

ans = 0
for a in aL:
    if dp[a]:
        continue
    if d[a] > 1:
        c = 1
        while a * c <= 1000000:
            dp[a * c] = True
            c += 1
        continue
    ans += 1

    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

multiple = [False] * 1_000_001
once = set()
twice = set()
count = 0

for a in sorted(map(int, input().split())):
  if a in once:
    if a in twice:
      continue
    else:
      count -= 1
      twice.add(a)
  elif multiple[a]:
    continue
  else:
    count += 1
    once.add(a)
    for x in range(a, 1_000_001, a):
      multiple[x] = True
print(count)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = Counter(A)
    one = []
    for k,v in m.items():
        if v == 1:
            one.append(k)
        else:
            for i in range(k,M+1,k):
                erato[i] = False
    one.sort()
    ans = 0 
    for i in one:
        ans += 1 if erato[i] else 0
        for j in range(i,M+1,i):
            erato[j] = False

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
 
N = int(input())
A = sorted(int(x) for x in input().split())
max_num = A[-1] + 1
count = [0] * max_num

for i in A:
    if count[i] != 0:
        count[i] = 2
        continue
    else:
        for j in range(i, max_num, i):
            count[j] += 1

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

Submission status: Accepted

Solution code:
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = dict()
    for i in A:
        if i in m:
            m[i] += 1
        else:
            m[i] = 1
    one = []
    for k,v in m.items():
        if v == 1:
            one.append(k)
        else:
            for i in range(k,M+1,k):
                erato[i] = False
    one.sort()
    ans = 0 
    for i in one:
        ans += 1 if erato[i] else 0
        for j in range(i,M+1,i):
            erato[j] = False

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if dp[i] == 0:
            pass
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split(" ")))
a_max = max(A)
cnts = [0] * (a_max + 1)
for a in A:
    v = a
    while v <= a_max:
        cnts[v] += 1
        v += a
cnt = 0
for a in A:
    if cnts[a] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
amax = a[-1]

ans = 0
tmp = 0
prev = 0
t = [False] * (amax + 1)
for i in a:
    if i != prev:
        ans += tmp
    tmp = 0
    if not t[i]:
        tmp += 1
        k = i
        while k <= amax:
            t[k] = True
            k += i
    prev = i
ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    s.add(arr[i])
  for j in range(2,10**6//arr[i]+1):
    s.add(arr[i]*j)
ans=0
for i in range(n):
  if arr[i] in s:
    continue
  ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = sorted([int(a) for a in input().strip().split()])
    Acnt = Counter(A)
    if Acnt[1] == 1:
        print(1)
        return True
    elif Acnt[1] > 1:
        print(0)
        return True

    max_A = max(A)
    f = [True] * (max_A + 1)
    ans = 0
    for i in range(2, max_A + 1):
        if Acnt[i] > 0 and f[i]:
            if Acnt[i] == 1:
                ans += 1
            j = 1
            k = i
            while k <= max_A:
                f[k] = False
                j += 1
                k = i * j

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
            '''
            elif dp[2*i] == 0:
            pass
            '''
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Submission status: Accepted

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

max_A = A[-1]
# df[i]...数字iが条件満たす:1、条件満たさない:0
df = [True for _ in range(max_A + 1)]

for i, a in enumerate(A):
    if i > 0:
        if A[i] == A[i - 1]:
            df[a] = False
            continue
    if df[a]:
        for num in range(2*a, max_A+1, a):
            df[num] = False
count = 0
for a in A:
    if df[a]:
        count += 1
print(count)

Submission status: Accepted

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

# if n == 1:
#     print(1)
#     sys.exit()

d = defaultdict(int)

for key in A:
    d[key] += 1

# if len(d) == 1: # 全部同じ数
#     print(0)
#     sys.exit()

B = list(d)
# B.sort()

# if B[0] == 1: # 1が含まれる場合
#     print(d[1])
#     sys.exit()
# length = len(d)
m = max(d)
flag = [0 for i in range(m+1)]

for i in B:
    t = i
    while t <= m:
        flag[t] += 1
        t += i

ans = 0
for i in B:
    if flag[i] == 1 and d[i] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    #s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        if 2*i > len(dp)-1:
            pass
            '''
            elif dp[2*i] == 0:
            pass
            '''
        else:
            for j in range(2*i, len(dp), i):
                dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    l_a = list(map(int, input().split()))
    s_a = list(set(l_a))

    #s_a.sort()

    dub_a = [0]*(max(s_a)+1)

    for i in l_a:
        dub_a[i] += 1

    dp = [1]*(max(s_a)+1)

    for i in s_a:
        for j in range(2*i, len(dp), i):
            dp[j] = 0


    count = 0
    for i in s_a:
        if dp[i]==1 and dub_a[i]==1:
            count += 1
    print(count)

Submission status: Accepted

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

Cnt = [0 for i in range(10**6 + 8)]
for i in A:
    if Cnt[i] != 0:
        Cnt[i] = 2
        continue
    else:
        pass
    for j in range(i, 10**6 + 8, i):
        Cnt[j] += 1

ans = 0
for i in A:
    if Cnt[i] == 1:
        ans += 1
    else:
        pass

print(ans)

Submission status: Accepted

Solution code:
N= int(input())
a =list(map(int,input().split()))
a.sort()
ans=0
Amax=max(a)
DP=[1]*(Amax+1)#これが0のとき、該当する数はカウント済み
#上から順に攻めていく
for i in range(N-1):
    p=a[i]
    if DP[p]==1:#まだ数えられていなかったら
        for j in range(Amax//p+1):#倍数をすべて0にする
            DP[p*j]=0
        if p!=a[i+1]:#隣の数と違うならば
            ans+=1
if DP[Amax]==1:#最後の数は隣の数と比べられんので個別判断
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
A.sort()
dp = [True] * (max(A) + 1)
ans = 0
for n in A:
    ans += int(dp[n] and cnt[n] == 1)
    tmp = n
    while tmp < len(dp):
        dp[tmp] = False
        tmp += n
print(ans)

Submission status: Accepted

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

ma = 10**6+1
div = [0]*ma #div[i] == 1::iを割り切るものが存在
cnt = 0
prev = -1
for a in A:
    if div[a] == 1:
        continue
    if co[a]==1:
        cnt+=1
    for i in range(a,ma,a):
        div[i] = 1

print(cnt)

Submission status: Accepted

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

c = Counter(a)
b = [k for k, v in c.items() if v == 1]
b.sort()
d = {b: i for i, b in enumerate(b)}

gg = [True] * len(b)
mx = 10 ** 6 + 1
for i in c.keys():
    for j in range(2 * i, mx, i):
        if j in d:
            gg[d[j]] = False

print(sum(gg))

Submission status: Accepted

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()
#first = True  # firstのフラッグの使い回しをしていた．複数に分かれる条件分岐はしっかりとどのような分岐をするか書く癖をつけたほうがよい
for a in A:
    if L[a] == 2:
        continue
    if a in used:
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Accepted

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

def main():
    N,*A = map(int, read().split())

    A.sort()
    table = [0] * (A[-1] + 1)
    n = len(table)

    for a in A:
        if table[a] > 1:
            continue

        if table[a] == 0:
            for i in range(2*a, n, a):
                table[i] = 2
        
        table[a] += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

maxA = max(A)
C = Counter(A)

D = {a: 0 for a in A}
for a in A:
  t = 2
  while a * t <= maxA:
      D[a * t] = 1
      t += 1

ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = [int(i) for i in input().split()]
A.sort()
dp = np.array([True for _ in range(A[-1]+1)])
A = np.array(A)
prev = 0
for a in A:
  if dp[a]:
    if prev == a:
      dp[a] = False
    for i in range(A[-1]//a+1):
      if i > 1:
        dp[i*a] = False
  prev = a
print(dp[A.tolist()].sum())

Submission status: Accepted

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

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

for i in range(n):
  if dp[a[i]]==False:
    #print(dp)
    continue
  if a[i]*2<=a[-1]+1:
    for j in range(a[i]*2,a[-1]+1,a[i]):
      dp[j]=False
      #print(dp)
for i in range(len(cnt)):
  if cnt[i]>=2:
    dp[i]=False
    
for i in range(n):
  if dp[a[i]]:
    ans+=1
print(ans)

Submission status: Accepted

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

a.sort()

ma = max(a)
f = [1] * (ma + 1)

count = collections.Counter(a)
ans = 0

for i in a:
    if f[i]:
        if count[i] == 1:
            ans += 1
        for j in range(i, min(ma + i, ma + 1), i):
            f[j] = 0

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
MAX = A[-1]+1
num_tmp = [0]*MAX

for a in A:
    num_tmp[a] += 1
    if num_tmp[a] == 1:
        for i in range(2*a,MAX,a):
            num_tmp[i] = 2

print(num_tmp.count(1))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    MAX = A[-1]+1
    num_tmp = [0]*MAX

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,MAX,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()

Submission status: Accepted

Solution code:

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

List.sort()
seive=[0]*(List[~0]+1)
count=0
for each in List:
    for i in range(each,List[-1]+1,each):
        seive[i]+=1
        
for each in List:
    if(seive[each]==1):
        count+=1


print(count)

Submission status: Accepted

Solution code:
_,*A = map(int,open(0).read().split())
A.sort()
M = 10**6 + 1
l = [0] * (M)
for a in A:
    if l[a] == 0:
        l[a] = 2
        for x in range(a*2, M, a):
            l[x] = 1
    elif l[a] == 2:
        l[a] += 1
print(l.count(2))

Submission status: Accepted

Solution code:
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = sum(counter[x] == 1 for x in array)
    print(ans)


main()

Submission status: Accepted

Solution code:
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = sum(counter[x] == 1 for x in array)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    a = list(map(int, input().split()))
    arr = [0]*(10**6 + 1)
    for x in a:
        if arr[x] == 0:
            for i in range(x, 10**6 + 1, x):
                arr[i] += 1
        else:
            arr[x] += 1
    ans = 0
    for i in a:
        if arr[i] == 1:
            ans += 1
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = array[-1] + 1
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    is_ans[a] += 1
    if is_ans[a] == 1:
        b = 2*a
        while b < ans_len:
            is_ans[b] += 2
            b += a

ans = 0
for a in a_list:
    # print(a, is_ans[a])
    ans += (is_ans[a] == 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = 1000003

    counter = defaultdict(int)
    for x in array:
        counter[x] += 1
    maximum = array[-1] + 1
    candidates = [True] * maximum
    for key, value in counter.items():
        if value > 1:  # duplicate
            candidates[key] = False
        for i in range(key * 2, maximum, key):
            candidates[i] = False

    ans = sum(candidates[x] for x in array)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
lis = list(map(int, input().split()))
maxL = max(lis)+1
t = [0] * maxL
lis.sort()
for k in lis:
    t[k] += 1
    if t[k] == 1:
        for p in range(k * 2, maxL, k):
            t[p] += 2
print(t.count(1))

Submission status: Accepted

Solution code:
def main():
    input()
    array = sorted(int(x) for x in input().split())
    maximum = 1000001
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    numbers = int(input())
    array = [int(x) for x in input().split()]
    maximum = 1000001
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for elem in a:
    cnt[elem] += 1

unique = []

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

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

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0

for elem in unique:
    if cnt[elem] == 0:
        ans += 1

print(ans)