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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
largest = max(a)
b = [True] * (largest+1)
dict = {}
ans = 0
for num in a:
    if num in dict.keys():
        b[num] = False
    else:
        dict[num] = 1
        y = num * 2
        while(y <= largest):
            b[y] = False
            y += num
for num in a:
    if b[num] == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
M = 1000005
l = [0 for i in range(M)]

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

    for i in range(a,M,a):
        l[i]+=1

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 1000005
cnt = [0]*M
for a in A:
    if cnt[a]!=0:
        cnt[a]+=1
        continue
        
    for i in range(a, M, a):
        cnt[i]+=1
        
ans = 0
for a in  A:
    if cnt[a] == 1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

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


if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:

def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
inf = 10**6+1
a = LI()
a.sort()
ans = 0
li = [0]*inf
for x in a:
    p = li[x]
    if p != 0:
        li[x] = 2
        continue
    for i in range(x,inf,x):
        li[i] += 1
for i in a:
    if li[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
MA = max(A)
dp = [True for _ in range(MA+1)]
flag = [False for _ in range(MA+1)]

for i in range(N):
    a = A[i]
    if not flag[a]:
        flag[a] = True
        t = a*2
        while t <= MA:
            dp[t] = False
            t += a
    elif flag[a] == 1:
        dp[a] = False
res = 0
for a in A:
    if dp[a]:
        res += 1
print(res)

Submission status: Accepted

Solution code:
# Not Divisible

N = int(input())
A = [int(n) for n in input().split()]

check = [0] * 1000001
A.sort()

ok = [-1]
p = 0
for a in A:
    if a == p:
        if ok[-1] == p:
            ok = ok[:-1]
        continue
    p = a
    if check[a] == 1:
        continue
    for i in range(a, 1000001, a):
        check[i] = 1
    ok.append(a)

print(len(ok) - 1)

Submission status: Accepted

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

m = max(a)
#約分できちゃう数値リスト
lis = [0]*(m + 1)
for i in a:
  for j in range(i, m + 1, i):
    lis[j] += 1
#iが1なら、lisの要素全てに+1されてる。
count = 0
for i in a:
  if lis[i] == 1:
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort()
A_counter = Counter(A)

dp = [True for _ in range(10**6+1)]
for a in A_counter:
    if dp[a] == False:
        continue
    for j in range(a*2, 10**6+1, a):
        dp[j] = False

c = 0
for a, v in A_counter.items():
    if dp[a] and v == 1:
        c += 1

print(c)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, *a = map(int, read().split())
    a.sort()
    a = tuple(a)
    TorF = [0] * (a[-1] + 1)
    for ae in a:
        TorF[ae] = 1
    for i1 in range(n - 1):
        a1 = a[i1]
        if TorF[a1]:
            m = a[-1] // a1 + 1
            for i2 in range(2, m):
                TorF[a1 * i2] = 0
        if a[i1 + 1] == a[i1]:
            TorF[a[i1]] = 0
    r = sum(TorF)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

f = [0 for i in range(10**6+5)]
for x in a:
    f[x] += 1
for i in range(1, len(f)):
    if f[i] == 0:
        continue
    for j in range(2*i, len(f), i):
        f[j] = 0
ans = 0
for v in f:
    if v == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                r = 1
                for p in j:r *= p
                res |= {r}
        return res

if __name__ == "__main__":
    n, *a = map(int, open(0).read().split())
    b, c = set(a), Counter(a)
    P = Osa_k(10**6)
    cnt = 0
    for i in b:
        if c[i] > 1:continue
        for d in P.div(i):
            if d != i and d in b:break
        else:cnt += 1
    print(1 if n == 1 else cnt)

Submission status: Accepted

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

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

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if i != 0 and a[i-1] == value:
            count -= 1
            kSet.add(value)
            continue
        count += 1
        j = 2
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())

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

aMax = a[-1]
l = len(a)
count = 0
k = 0
kSet = set()

for i in range(n):
    value = a[i]
    if not(value in kSet):
        if i != 0 and a[i-1] == value:
            count -= 1
            kSet.add(value)
            continue
        count += 1
        j = 2
        k = 0
        while k < aMax:
            k = a[i] * j
            kSet.add(k)
            j += 1
    #if value ** 2 > aMax:
    #    break

print(count)

Submission status: Accepted

Solution code:
import sys

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

array = [0 for i in range((10 ** 6)+1)]
for v in a:
  array[v] += 1
  
for i in range(1, len(array)):
  if array[i] == 0:
    continue
    
  for j in range(i*2, len(array), i):
    array[j] = 0
    
count = 0
for v in array:
  if v == 1:
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]==1:
            for item in range(2*rep,m,rep):
                ava[item] += 2

    print(ava.count(1))
    return

if __name__=='__main__':
    n = I()
    a = list(IL())
    a.sort()
    solve()

Submission status: Accepted

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

a_max = a[-1]
dp = [1]*a_max

for i in set(a):
    j = 2
    while i*j <= a_max:
        dp[i*j-1] = 0
        j += 1

a.append(0)
ans = 0
for i in range(n):
    if dp[a[i]-1] and a[i-1] != a[i] and a[i] != a[i+1]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

from collections import Counter

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


lim = 10 ** 6 + 10
ok = [True] * (lim + 1)
ans = 0
ctr = Counter(X)
for n in sorted(X):
    if ok[n]:
        if ctr[n] == 1:
            ans += 1
        for j in range(n, lim + 1, n):
            ok[j] = False

print(ans)

Submission status: Accepted

Solution code:
# 30分ぐらい？で溶けた！計算量は直感だよりだったが。
# → エラトステネスの篩 に相当する実装らしい。

# リスト内の倍数・約数関係を判定し、カウントする。
# 二重ループで判定するとTLEになるため、小さい値の可能な倍数を計算して保存するようにした。
# メモを set() ではなく 配列 で実装するテスト

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

# 小さい側から処理する。a[i]について、10**6 以下のすべての倍数をset()として持つ。
# ただし、set内に存在しない==初出の約数のみ倍数計算をしてカウントする。
# 例えば、2,6,... となった場合、(6の倍数セットは2の倍数セットの下位集合となるため計算不要)

s=[False]*(10**6+1)
cnt=0
for i,aa in enumerate(a):
  if s[aa]:
    continue

  # 同値が複数ある場合、カウントしない。
  if i+1 == len(a) or aa != a[i+1]:
    cnt+=1
  for i in range(1,10**6+1):
    ma=aa*i
    if ma > 10**6:
      break
    s[ma]=True

print(cnt)

Submission status: Accepted

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

# 小さい側から処理する。a[i]について、10**6 以下のすべての倍数をset()として持つ。
# ただし、set内に存在しない==初出の約数のみ倍数計算をしてカウントする。
# 例えば、2,6,... となった場合、(6の倍数セットは2の倍数セットの下位集合となるため計算不要)

s=set()
cnt=0
for i,aa in enumerate(a):
  if aa not in s:
    # 同値が複数ある場合、カウントしない。sortしているため、同値は並ぶ
    if i+1 == len(a) or aa != a[i+1]:
      cnt+=1
    
    for i in range(1,10**6+1):
      ma=aa*i
      if ma > 10**6:
        break
      s.add(ma)

print(cnt)

Submission status: Accepted

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

Amax = max(A)
dp = [True] * Amax
seen = set()

for a in A:
    if a in seen:
        dp[a-1] = False
        continue
    i = 2
    while i * a <= Amax:
        dp[i*a-1] = False
        i += 1
    seen.add(a)


B = [dp[a-1] for a in A]
print(sum(B))

Submission status: Accepted

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

Amax = max(A)
dp = [True] * Amax
seen = set()

for a in A:
    if a in seen:
        dp[a-1] = False
    i = 2
    while i * a <= Amax:
        dp[i*a-1] = False
        i += 1
    seen.add(a)


B = [dp[a-1] for a in A]
print(sum(B))

Submission status: Accepted

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

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

for i in range(n):
    cnt[a[i]] += 1

a_uniq = []

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

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

for i in list(set(a)):
    for j in range(2 * i, 10 ** 6 + 1, i):
        cnt[j] = 1

ans = 0

for i in a_uniq:
    if cnt[i] == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(1+A[-1])
for i in A:
    B[i]+=1
    if B[i]==1:
        for j in range(2*i,A[-1]+1,i):
            B[j]+=1
    else:
        continue
ans=0
for i in A:
  if B[i]==1: ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

a.sort()
tf = [True] * a[-1]
dup = [False] * a[-1]


for i in range(n):
    if tf[a[i]-1] == True:
        #print(a[i])
        if dup[a[i]-1] == True:
            tf[a[i]-1] = False
        else:
            dup[a[i]-1] = True
            for j in range(a[i]*2, a[-1]+1, a[i]):
                tf[j-1] = False
                

c = 0

#print(tf)

for x in a:
    if tf[x-1]:
        c += 1

print(c)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
li = [0]*(m+1)
cnt = 0
        
for i in arr:
  for j in range(i, m+1, i):
    li[j] += 1

for i in arr:
  if li[i] == 1:
    cnt += 1

print(cnt)

Submission status: Accepted

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

for i in a:
  for j in range(i,m+1,i):
    arr[j]+=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)

Submission status: Accepted

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

maxVal = max(A)+1
isPrime = [0] * maxVal
isDuplicate = [0] * maxVal
isDivisible = [0] * maxVal

for i in range(len(A)-1):
    if A[i] == A[i+1]:
        isDuplicate[A[i]] = 1

for i in range(len(A)):
    if not isDivisible[A[i]]:
        isPrime[A[i]] += 1

        j = 2
        while A[i] * j < maxVal:
            isDivisible[A[i] * j] = 1

            j += 1

ans = isPrime.count(1)

print(ans)

Submission status: Accepted

Solution code:
def solve(ls):
    n = len(ls)
    lim = max(ls)
    sieve = [1] * (lim + 1)
    result = 0
    ls.sort()
    for i in range(n):
        x = ls[i]
        if sieve[x] == 0:
            continue
        # Don't count if ls[i] = ls[i+1]
        if not (i + 1 < n and x == ls[i + 1]):
            result += 1
        y = x
        while y <= lim:
            sieve[y] = 0
            y += x
    return result


def main(istr, ostr):
    n = list(map(int, istr.readline().strip().split()))
    ls = list(map(int, istr.readline().strip().split()))
    result = solve(ls)
    print(result, file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
a_max = a_list[-1]

divisible = [False] * (a_max + 1)

count = 0
i = 0
for i in range(n):
    if divisible[a_list[i]]:
        continue
    if i < n - 1 and a_list[i] == a_list[i + 1]:
        while i < n - 1 and a_list[i] == a_list[i + 1]:
            i += 1
    else:
        count += 1
    x = a_list[i]
    while x <= a_max:
        divisible[x] = True
        x += a_list[i]
print(count)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = list(map(int, input().split()))
count = {}
for a in A:
  if a not in count:
    count[a] = 0
  count[a] += 1

def check(a):
  if count[a] > 1:
    return 0

  if 1 in count:
    if a == 1 and count[1] == 1:
      return 1
    return 0

  #print(a)
  ok = True
  sqr_a = 1 + int(a**0.5)
  for s in itertools.chain([2], range(3, sqr_a, 2)):
    if a % s:
      continue
    c = s
    while c < sqr_a:
      if a % c == 0 and (c in count or (a//c) in count):
        #print(a, c)
        ok = False
        break
      c *= 2
  return ok
  
ans = 0
for a in A:
  ans += check(a)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
num=[0]*(max(a)+1)
maxa=max(a)
cnt=1

for i in a:
  while 1:
    try:
      num[i*cnt]+=1
      cnt+=1
      
      
    except IndexError:
      break
  cnt=1      

count=0

for i in range(n):
  if num[a[i]]==1:
    count+=1
    
print(count)

Submission status: Accepted

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

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

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

print(dp.count(1))

Submission status: Accepted

Solution code:
M = 10**6
N = int(input())
A = list(map(int, input().split()))


def solve():
    amax = max(A)+1
    memo = [0] * amax
    for a in A:
        i = 1
        while i*a < amax:
            memo[i*a] += 1
            i += 1

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

    return count

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort()
a_max = a_ls[-1]
times_ls = [0] * (a_max + 1)
divisible_ls = [0] * (a_max + 1)
for i in range(n):
    base = a_ls[i]
    times_ls[base] += 1
    times = 2
    while base*times <= a_max:
        divisible_ls[base*times] = 1
        times += 1
ans = 0
for i in range(1,a_max+1):
    if times_ls[i] == 1 and divisible_ls[i] == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())

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

m = max(A)

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

dp = [True] * m

for a in A:
  if C[a] > 0:
    C[a] += 1
    continue
  C[a] += 1
  i = 2
  while a * i <= m:
    dp[a*i - 1] = False
    i += 1
    
ans = 0

for a in A:
  if C[a] < 2 and dp[a - 1] == True:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(A[-1]+1)
for i in A:
  B[i]+=1
  if B[i]>=2:
    continue
  for j in range(2*i,A[-1]+1,i):
    B[j]+=1
ans=0
for i in A:
  if B[i]==1:
    ans=ans+1
print(ans)

Submission status: Accepted

Solution code:
n,a=int(input()),sorted(list(map(int,input().split())))
m=a[-1]+1
s=[0]*m
for i in a:
  s[i]+=1
for i in set(a):
  if s[i]:
    for j in range(i*2,m,i):
      s[j]=0
print(s.count(1))

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

M=10**6+10
n=int(input())
a=Counter(lmp()).most_common()
a=sorted(a, key=lambda x: x[0])
c=[0]*M
for j,x in a:
    if c[j]==0:
        k=2
        while j*k<M:
            c[j*k]=1
            k+=1
ans=0
for x,y in a:
    if c[x]==0 and y==1:
        ans+=1
print(ans)

Submission status: Accepted

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

MAX_A = 1000001

dp = [0]*MAX_A

for i in A:
  if dp[i] == 0:
    for j in range(i, MAX_A,i):
      dp[j] += 1
  else:
    dp[i] += 1

c = 0
for i in A:
  if dp[i] == 1:
    c += 1

print(c)

Submission status: Accepted

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

List = [0 for x in range(1000001)]
answer = 0

def main(a, List):
    if List[a] >= 1:
        List[a] = List[a] + 1
        return List
    else:
        for i in range(a, 1000001, a):
            List[i] = List[i] + 1
    return List

def Answer(A, List):
    answer = 0
    for a in A:
        if List[a] == 1:
            answer += 1
    return answer

for a in A:
    main(a, List)

print(Answer(A, List))

Submission status: Accepted

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

for i in range(len(A)-1):
    p = A[i]
    if dp[A[i]] == 1:
        for j in range(A_max // p + 1):
            dp[j*p] = 0
        if A[i] != A[i+1]:
            ans += 1
            
if dp[A_max] == 1:
    ans += 1

print(ans)

Submission status: Accepted

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


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

  not_divisible = [False]*(10**6+1)
  for i in range(N):
    not_divisible[A[i]] = True

  prev = 0
  for i in range(N):
    if not_divisible[A[i]]:
      j = A[i] + A[i]
      while j <= A[-1]:
        not_divisible[j] = False
        j += A[i]
    if prev == A[i]:
      not_divisible[A[i]] = False
    prev = A[i]

  cnt = 0
  for i in range(N):
    if not_divisible[A[i]]:
      cnt += 1

  print(cnt)


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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))

    MAX = max(A) + 1
    flg = [0] * MAX
    tmp = set()
    for a in A:
        if a in tmp:
            flg[a] = 1
        tmp.add(a)

    res = 0
    for a in A:
        if not flg[a]:
            res += 1
        for i in range(a, MAX, a):
            flg[i] = 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
ans = 0
from collections import Counter
N = int(input())
A = inputlist()
A.sort()
dic = Counter(A)
dp = [1 for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]]:
        j = 2
        while A[i]*j <= A[-1]:
            dp[A[i]*j] = 0
            j +=1
        if dic[A[i]] == 1:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

a = [int(x) for x in input().split()]

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

for i in a:
	if baisuu[i]>=1:
		baisuu[i]=2
		continue

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

ans=0

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

print(ans)

Submission status: Accepted

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

A = sorted(A, key=lambda x: x)
all = [True] * 1000001
ans = 0
for i in range(N):
    if all[A[i]] == False:
        continue
    if i == N - 1 or A[i+1] > A[i]:
        ans += 1
    b = A[i]
    while b < 1000001:
        all[b] = False
        b += A[i]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
LN = max(A) + 1
L = [0 for i in range(LN)]
count = 0
for i in A:
    for j in range(i, LN, i):
        L[j] += 1
for i in A:
    if L[i] == 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
inf =  1100000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for x in a:
    if detect[x] != 0:
      detect[x] = 2
      continue
    for i in range(x, inf, x):
      detect[i] += 1
  ans = 0
  for i in range(N):
    if detect[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

num_list=set()
prime_list=set()

from collections import Counter
dic=Counter(a)
a=set(a)

for i in dic:
  if dic[i]>=2:
    dic[i]=0
  if i not in num_list:
    for j in range(i*2,k+1,i):
      if j in a:
        dic[j]=0
        num_list.add(j)

print(sum(dic.values()))

Submission status: Accepted

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()
freq = [0] * (10**6+1)
for a in A:
    freq[a] += 1
m = A[-1]
ans = n
for i in range(n):
    a = A[i]
    if freq[a] > 1:
        ans -= freq[a]
        freq[a] = 0
    for j in range(2 * a, m+1, a):
        if freq[j] > 0 and j % a == 0:
            ans -= freq[j]
            freq[j] = 0
print (ans)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = [int(x) for x in input().split()]
a.sort()

m = np.zeros(max(a)+1, dtype=int)
cnt = 0

for i in range(n):
    x = a[i]
    if i == n-1:
        if m[x] == 0:
            cnt +=1
    else:
        if m[x] == 0 and a[i] != a[i+1]:
            cnt +=1
    m[x::x] += 1
print(cnt)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    a = [0] * 1000005
    A_max = A[-1]

    for i in A:
        for j in range(1, A_max//i + 1):
            a[i * j] += 1

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

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

for aa in a:
    for j in range(2*aa,len(b), aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
from functools import reduce

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

a.sort()

count = Counter(a)

b = [1]*(max(a) + 1)

for aa in a:
    for j in range(2*aa,len(b), aa):
        b[j] = 0

c = 0
for d in count.items():
    if d[1] == 1 and b[d[0]] == 1: c += 1

print(c)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.readline
import time
import math
import itertools as it
def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
start_time = time.perf_counter()
# ------------------------------

N = inp()
A = inpl()
A.sort()
dp = [False] * 1001001
nt = -1

for i in A:
    if i != nt:
        dp[i] = True
    else:
        dp[i] = False
    nt = i

ans = 0
mx = A[N-1]
nt = -1
for i in A:
    if dp[i]:
        ans += 1
    if i == nt:
        continue
    nt = i
    j = i
    while j <= mx:
        dp[j] = False
        j += i

print(ans)

# -----------------------------
end_time = time.perf_counter()
print('time:', end_time-start_time, file=sys.stderr)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
B = [1] * (max(A) + 1)
for a in A:
    for k in range(a  * 2,len(B),a):
            B[k] = 0
print(sum(B[a] == 1 and counter[a] == 1 for a in A))

Submission status: Accepted

Solution code:

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

MAX = 10 ** 6 + 1
prime = [True] * MAX
counted = set()
for v in X:
    if v in counted:
        prime[v] = False
        continue
    for j in range(2 * v, MAX, v):
        prime[j] = False
    counted.add(v)

ans = 0
for v in X:
    ans += int(prime[v])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = [int(Ai) for Ai in input().split()]

counter = Counter(A)

dp = [1] * (max(A) + 1)
for Ai in A:
    for j in range(Ai * 2, len(dp), Ai):
        dp[j] = 0

print(sum([dp[Ai] == 1 and counter[Ai] == 1 for Ai in A]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0]*(10**6+1)
for x in a:
    if num[x] != 0:
        num[x] = 2
        continue
    for i in range(x, 10**6+1, x):
        num[i] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())
A.sort()
max_A=A[-1]

L=[ 0 for _ in range(max_A+1) ]
for a in A:
    L[a]+=1

for i,x in enumerate(L):
    if 1<x:
        L[i]=0

for a in A:
    for i in range(a*2,max_A+1,a):
        L[i]=0

print sum(L)

Submission status: Accepted

Solution code:
n,a=int(input()),sorted(list(map(int,input().split())))
m=a[-1]+n
dp=[0]*m
for i in a:dp[i]+=1
for i in set(a):
    if dp[i]:
        for j in range(i*2,m,i):
            dp[j]=0

print(dp.count(1))

Submission status: Accepted

Solution code:
n,a=int(input()),sorted(list(map(int,input().split())))
m=a[-1]+1
s=[0]*m
for i in a:s[i]+=1
for i in set(a):
	if s[i]:
		for j in range(i*2,m,i):s[j]=0
print(s.count(1))

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
num = set(A)
count = Counter(A)
dp = [True] * (10**6 + 1)

for a in num:
    for n in range(a+a, 10**6+1, a):
        dp[n] = False

ans = 0
for a in num:
    if count[a] == 1 and dp[a] == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 問題文誤読して30分経過してた
# ソートしたとき「自分より小さいいずれの値も自分の素因数に含まれない」
# これはなんか実装しにくいので、A<10^6を利用して、調和級数的なノリでやってみる
n = int(input())
a = sorted(list(map(int, input().split())))

t = {}
for av in a:
    if av not in t:
        t[av] = 1
    else:
        t[av] += 1
limit = a[-1]

d = [True] * (limit + 1)
for av in a:
    start = av
    # 複数あった場合は自分自身も粛清の対象になる
    if t[av] == 1:
        start *= 2
    for i in range(start, limit + 1, av):
        d[i] = False

ans = 0
for av in a:
    if d[av]:
        ans += 1

print(ans)

Submission status: Accepted

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

xs = [0] * (max(a) + 1)

for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
dp = [0] * (10 ** 6 + 10)
for x in A:
    i = 0
    while x + i <= 10 ** 6 + 10:
        if dp[(x-1)] == 2:
            break
        else:
            dp[(x-1) + i] += 1
            i += x

cnt = 0
for x in A:
    if dp[x-1] == 1:
        cnt += 1

print(cnt)