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

from collections import Counter
C = dict(Counter(A))  #辞書型にする
#print('C',C)
Ckey = list(C.keys())
#print('Ckey',Ckey)

B = sorted(Ckey)
#print('B',B)

out=0
table=[0]*(10**6)
for i in range(len(B)):
        if table[B[i]-1]==1:
            continue
        elif C[B[i]]==1:
            out+=1
        k=1
        while k*B[i]<=10**6:
            table[k*B[i]-1]=1
            k+=1

print(out)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
a=collections.Counter(a)
b,c=[],[]
for t in a:
  if a[t]==1:
    b.append(t)
  else:
    c.append(t)
if len(b) == 0:
  print(0)
  exit()
b.sort()
bm = b[-1]
ok = [True]*(bm+1)

if len(c)>0:
  c.sort()
  for t in c:
    if t>=bm: continue
    if ok[t] == False: continue
    i = 1
    while i*t<=bm:
      ok[i*t]=False
      i+=1
for t in b:
  if ok[t] == False: continue
  i = 2
  while i*t<=bm:
    ok[i*t]=False
    i+=1
ans = 0
for t in b:
  if ok[t]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

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

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


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

dp=[False]*(A_max+1)
ans=0

temp=A[0]
while True:
    if temp>A_max:
        break
    dp[temp]=True
    temp+=A[0]

if A[0]!=A[1]:
    ans+=1


for i in range(1,n-1):
    if dp[A[i]]:
        continue

    temp=A[i]
    while True:
        if temp>A_max:
            break
        dp[temp]=True
        temp+=A[i]
    
    if A[i-1]!=A[i] and A[i]!=A[i+1]:
        ans+=1


if not dp[A[n-1]] and A[n-2]!=A[n-1]:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import math

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  MAX = A[-1]
  dp = [True] * MAX
  c = [0] * MAX
  ans = 0

  for a in A:
    i = a - 1
    c[i] += 1

    if((not dp[i]) and c[i] > 1):
      continue

    e = a * 2    
    while e <= MAX:
      dp[e-1] = False
      e += a
      
  for v in A:
    i = v - 1
    if dp[i] and c[i] == 1:
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

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


maxA = max(a)
dp = [0]*(maxA+1)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in a:
    if dp[e] == 1:
        count += 1

print(count)

Submission status: Accepted

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

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


print(ok.count(1))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
maxA = max(A)
# C[a] = A内のaの個数
C = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
D = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    if C[a] > 0:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 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
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))

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

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            memo[a * i] += 1

    ans = 0
    c = collections.Counter(A)
    for a in A:
        # 同じ数が複数入っていた場合もカウントしない
        if memo[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import sqrt
from collections import Counter, deque
N = int(input())
As = list(mapint())
As.sort()
C = Counter(As)
S = set()

MAX = As[-1]
cnt = 0
for n in range(N):
    p = As[n]
    if p in S:
        continue
    i = 1
    while MAX>=p*i:
        S.add(p*i)
        i += 1
    if C[p]>=2:
        continue
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))

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

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            memo[a * i] += 1

    ans = 0
    c = collections.Counter(A)
    for a in A:
        # 同じ数が入っていた場合もカウントしない
        if memo[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))
A.sort()
A_max = A[-1]
dp = [1] * (1 + A_max)
from bisect import bisect_left, bisect_right

for x in A[1:]:
    if dp[x] == 0:
        continue
    y = x * 2
    while y <= A_max:
        dp[y] = 0
        y += x
ans = []
for i in range(1, A_max+1):
    if dp[i] == 1:
        idx_l = bisect_left(A, i)
        idx_r = bisect_right(A, i)
        if idx_r - idx_l > 1:
            continue
        if A[idx_l] == i:
            ans.append(idx_l)
print(len(ans))

Submission status: Accepted

Solution code:
import math
num = int(input())
arr = input().split()
arr = sorted([int(i) for i in arr])

lis1 = [0]*(arr[-1]+1)

for num in arr:
  for j in range(0, len(lis1), num):
    lis1[j] += 1

cnt = 0
for num in arr:
  if lis1[num]==1: cnt+=1
    
print(cnt)

Submission status: Accepted

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

maxA = max(a)
dp = [0]*(maxA+1)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in a:
    if dp[e] == 1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = map(int, input().split())
a = list(sorted(a))
big = a[n-1]
mark = [0]*(big+1)
for x in a:
    mark[x] += 1
    if mark[x] > 1:
        continue
    for j in range(x*2, big+1, x):
        mark[j] += 1

ans = 0
for x in a:
    if mark[x] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
l = [0] * A[-1]
for i in range(N):
    l[A[i] - 1] += 1
for i in range(N):
    if l[A[i] - 1] > 1:
        l[A[i] - 1] = 0
    elif l[A[i] - 1] == 0:
        continue
    temp = A[i]
    while True:
        temp += A[i]
        if temp > A[-1]:
            break
        l[temp - 1] = 0
print(sum(l))

Submission status: Accepted

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

A.sort()

isWari = [True] * (10**6+1)

before = 0

for i in range(len(A)):
    if(before == A[i]):
        continue
    index = A[i]
    for j in range(index*2,10**6+1,index):
        isWari[j] = False
    before = A[i]

count = 0

for i in range(len(A)):
    if(i!=0 and A[i-1] == A[i]):
        continue
    if(i!=len(A)-1 and A[i] == A[i+1]):
        continue
    
    if(isWari[A[i]]):
        count += 1

print(count)

Submission status: Accepted

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

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

for i in A:
    if l[i] <= 1:
        for j in range(0,10**6+1,i):
            l[j] += 1
count = 0
for i in A:
    if l[i] == 1:
        count += 1
print(count)

Submission status: Accepted

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

l = [0]*(10**6 +1)
for i in a:
    l[i]+=1
num = 0

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

Submission status: Accepted

Solution code:
N = int(input())
AS = [int(x) for x in input().split()]

AS.sort(reverse=True)
MAX_AS = AS[0]
table = [0] * (MAX_AS + 1)  # 1..max(AS)

alreadyVisited = {}
for i in range(N):
    x = dx = AS[i]
    if alreadyVisited.get(x, False):
        table[x] = 0
        continue
    alreadyVisited[x] = True

    table[x] = 1
    while True:
        x += dx
        if x > MAX_AS:
            break
        table[x] = 0

print(sum(table))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, *a = map(int, open(0).read().split())
a.sort()
m = a[-1]  # m = max(a)
s = [0]*(m+1)  # インデックスを合わせる
ans = 0
for i in a:
    if s[i] <= 1:  # 2以上なら計算しても意味ない
        for j in range(i, m+1, i):
            s[j] += 1  # sのiの倍数の部分を増やす
# ここで、s[i] == 1なら、自分自身で一度だけ+1されてることと同値なので他の数字と互いに素。
# 逆に2以上なら自分自身と自分の倍数で+1されてるから互いに素ではない。
for k in a:
    if s[k] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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


b = sorted(list(A))
dp = [0]*(max(A)+1)

m_a = max(A)+1
for i in b:
    dp[i] += 1
    if dp[i]==1 :
        for j in range(i*2, m_a,i):
            dp[j] +=100

print(dp.count(1))

Submission status: Accepted

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

def main(n,a):
    maxa=10**6
    isprime=[True]*(maxa+1)
    sa=sorted(a)

    prevx=0
    for x in sa:
        if isprime[x]==False:
            continue
        if prevx==x:
            isprime[x]=False
            continue

        i=x*2
        while(i<=maxa):
            isprime[i]=False
            i+=x
        prevx=x
    
    count=0
    for x in sa:
        if isprime[x]==True:
            count+=1
    return count

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)

Submission status: Accepted

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

a.sort()

# 整数0から配列のmax値までの入れ物を用意しでデフォルト0
# 配列内の数字は +1
# 配列内の数字の倍数値は +2（倍数値 = 元の数値で割られてしまう）
# 結果、どの配列内の数値の倍数にもなっていない 値が 1 のデータの数が答えとなる
max_a = max(a)
i_list = [0] * (max_a + 1)

for i in a:
    i_list[i] += 1
    if i_list[i] == 1:

        # 自身の値は除くため開始値は2倍したものからスタート
        for j in range(2*i, max_a + 1, i):
            i_list[j] += 2

print(i_list.count(1))

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  a_max=a[-1]
  x=[True]*(a_max+1)
  a=a+[0]
  for i in range(n):
    ai=a[i]
    if x[ai]:
      l=a_max//ai-1
      aj=ai
      for _ in range(l):
        aj+=ai
        x[aj]=False
    if a[i]==a[i+1]:
      x[a[i]]=False
  ans=0
  x[0]=False
  for i in a:
    if x[i]:
      ans+=1
  print(ans)
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
m = max(A)
U = [0]*(m+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,m+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,m+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

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

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

print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def enum_duplicate_num(L):
        cnt = Counter(L)
        dup_num_set = set()
        buf = []
        for num in L:
            if cnt[num] > 1 and num not in dup_num_set:
                dup_num_set.add(num)
                buf.append(num)
            elif cnt[num] == 1:
                buf.append(num)
        return dup_num_set, buf


    def fill_mul_false(num, table):
        for ind in range(num*2, 10**6+1, num):
            table[ind] = False
    
    
    n = ii()
    command = lmi()
    dup_num_set, command = enum_duplicate_num(command)
    table = [False] * (10 ** 6 + 1)
    for num in command:
        table[num] = True
    for num in command:
        if table[num]:
            fill_mul_false(num, table)
    for num in dup_num_set:
        table[num] = False
    
    print(table.count(True))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = [0]*1000001

s = set()

for i in a:
    if b[i]:
        continue
    if i in s:
        b[i] = 1
    s.add(i)
    for j in range(2, 1000001):
        if i*j > 10 ** 6:
            break
        b[i*j] = 1

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

print(ans)

Submission status: Accepted

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

for a in a_list:
    if ans_list[a] >= 1:
        ans_list[a] += 1
        continue
    for j in range(2 * a, a_list[n - 1] + 1, a):
        ans_list[j] += 1
    ans_list[a] = 1

for a in a_list:
    if ans_list[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(A) 

A = list(set(A))
A.sort()


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

for a in A:
    if C[a] == 0:
        i = 1
        while True:
            if a*i > 10**6:
                break
            C[a*i] = 1
            i += 1
        if cnt[a] == 1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
max_A = A[-1]
cnt = Counter(A)
admissible = [True] * (max_A + 1)
checked = [False] * (max_A + 1)
ans = 0
for a in A:
    if not admissible[a] or checked[a]: continue
    ans += 1
    i = 2
    while a * i <= max_A:
        admissible[a * i] = False
        i += 1
    checked[a] = True
    if cnt[a] > 1: ans -= 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,max(A)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    A_MX = 10 ** 6

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

    ctr = [0] * (A_MX + 1)
    for x in A:
        ctr[x] += 1

    B = [0] * (A_MX + 1)

    ans = 0
    for x in A:
        if B[x]: continue
        if ctr[x] == 1:
            ans += 1
        y = x
        while y <= A_MX:
            B[y] = 1
            y += x
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    n = int(input())
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    flag = [True] * (A[-1] + 1)
    for i in A:
        if flag[i]:
            result += 1
            for j in range(2*i, A[-1] + 1, i):
                flag[j] = False
    for k, v in c.items():
        if v > 1:
            if flag[k]:
                result -= v
    print(result)
main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
a_max = max(A)
table = [True for i in range(a_max+1)]
for a in A:
    i = 2
    k = a * 2
    while k <= a_max:
        table[k] = False
        k += a
count = 0
for i, a in enumerate(A):
    if i < N - 1 and A[i] == A[i+1]:
        table[a] = False
    if table[a]:
        count += 1
print(count)

Submission status: Accepted

Solution code:
## coding: UTF-8
N = int(input())
A = sorted(list(map(int,input().split())))


#print(A)

MAX = 10**6+1000
l = [True] * MAX


count = 0
last = -1
mode = 0
for i in range(len(A)):
    e = A[i]
    if(last == e):
        count -= 1
        last = -1
    if(l[e]):
        count += 1
        for j in range(MAX):
            try:
                l[j*e] = False
            except IndexError:
                break
        last = e

    #print(l)

print(count)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))+[1000001]
A.sort()
m,ans=max(A)+1,0
li=[0 for _ in range(m)]
li[0]=1

for i in range(n):
  a=A[i]
  if not li[a]:
    if A[i+1] != a:
      ans += 1
    for i in range(a,m,a):
      li[i] = 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [True for i in range(a[-1])]
ans = n
for k in range(n-1):
    if p[a[k]-1]:
        if a[k] != a[k+1]:
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break
        else:
            ans -= 1
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break  
    else:
        ans -= 1    
k = n-1
if p[a[k]-1]:
    for i in range(1,a[-1]+1):
        if a[k]*i <= a[-1]:
            p[a[k]*i-1] = False
        else:
            break
else:
        ans -= 1   
print(ans)

Submission status: Accepted

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

def main():
    N = int(input().strip())
    l = [int(i) for i in input().strip().split()]
    ans = 0
    m = max(l)
    dp = [0] * (m+1)
 
    for n in l:
        for j in range(n, m + 1, n):
            dp[j] += 1
 
    for n in l:
        if dp[n] == 1:
            ans += 1
 
    return ans
 
if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    ma = max(a)+1
    al = [True]*ma
    ans = 0
    pi = 0
    for i in a:
        if al[i]:
            ans += 1
            for j in range(i,ma,i):
                al[j] = False
            pi = i
        else:
            if i == pi:
                ans -= 1
                pi = 0

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    w = [0] * (10 ** 6 + 1)
    for a in A:
        w[a] += 1
    f = [False] * (10 ** 6 + 1)
    for a in A:
        if f[a]:
            w[a] = 0
            continue
        for b in range(a * 2, 10 ** 6 + 1, a):
            w[b] = 0
        f[a] = True
    print(sum(w))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a.sort()

#print(a)
import numpy as np
U=10**6 + 5
is_prime = np.zeros(U,np.bool)
#is_prime[2] = 1
is_prime[1::] = 1
M = int(U**.5)+1
for ai in a:#range(3,M,2):
    if is_prime[ai]:
        is_prime[ai*2::ai] = 0
    #print(is_prime.nonzero()[0])

ans = 0

import collections
cnt = collections.Counter(a)
for ai in a:
    if is_prime[ai] and cnt[ai] == 1:
        ans += 1

print(ans)

"""
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)
"""

"""
p = list(range(10**6+10))

a = list(sa)
a.sort()

print(a)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(a, b)

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans)

"""

Submission status: Accepted

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

A.sort()

maxnum = A[-1]
checklist = [True]*(maxnum+1)
before = 0

for a in A:
    if before == a:
        checklist[a] = False
        continue
    num = 2
    while num * a <= maxnum:
        checklist[a * num] = False
        num += 1
    before = a

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A.sort()
ans = 0
max_A = max(A)
dp = [True]*(max_A+1)  # 0~max(A)の数についてのリスト
happend = set()
for a in A:
    if C[a] >= 2:
        if a in happend:
            continue
        else:
            # aが存在したという証拠だけは残しておく
            x = a * 2
            while x <= max_A:
                dp[x] = False
                x += a
            happend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a * 2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)

Submission status: Accepted

Solution code:
# MAX = int(1e6)+2


n = int(input())
lis = list(map(int,input().split()))
lis.sort()
MAX = lis[-1]
lis2 = [0]*(MAX+1)
# lis.sort()
# m = max(lis)
ans = 0

for num in lis:
    for i in range(num, MAX+1, num):
            lis2[i] += 1

for j in set(lis):
    if lis2[j] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    A.sort()
    ans=0
    # print(A)

    T=[True]*A[-1]
    # T[0]=False

    for i,a in enumerate(A):
        if T[a-1]:
            j=2*a
            while j <= A[-1]:
                T[j-1]=False
                j+=a
            if not i+1==len(A):
                if A[i]==A[i+1]:
                    T[a-1]=False

    for a in A:
        if T[a-1]:
            ans+=1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(sorted(map(int, readline().split())))

amax = max(A)
dp = [True] * (amax + 1)
count = [0] * (amax + 1)

for a in A:
    count[a] += 1
    b = 2 * a
    while b <= amax:
        dp[b] = False
        b += a

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

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
for i in A:
   dic[i] += 1
A = list(set(A))
# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(len(A)):
    #ll += 1
    #print(i)
    #print(A[i])
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

for i in A:
    dp[i] += 1
    if dp[i]==1:
        for j in range(i*2, m_a, i):
            dp[j] += 2
    # print(dp)
print(dp.count(1))

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
max_arr = max(arr)
mark = [0 for i in range(max_arr+1)]

for i in range(n):
    for j in range(arr[i], max_arr+1, arr[i]):
        mark[j] += 1
# print(mark)
count = 0
for i in range(n):
    if mark[arr[i]] == 1:
        count += 1
print(count)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = A[-1]
divisible = [False] * (M + 1)
ans = 0
for i, a in enumerate(A):
    if not (i < N - 1 and A[i+1] == a) and not divisible[a]:
        ans += 1
    for b in range(a, M + 1, a):
        divisible[b] = True
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)

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

for a in A:
    for mul in range(2, A[-1] // a + 1):
        flags[a * mul] = False
print(sum([flags[a] and c[a] == 1 for a in A]))