Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()
    num_list = i_list()

    count = 0
    num_list.sort()
    max_num = num_list[n-1]
    ans_list = [0] * (max_num + 1)

    num_list_counter = Counter(num_list)

    for k, v in num_list_counter.items():
        if v == 1:
            continue
        ans_list[k] = 1

    for num in num_list:
        if ans_list[num] == 0:
            count += 1
        for i in range(num, max_num+1, num):
            ans_list[i] = 1

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

Submission status: Accepted

Solution code:
from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict

d=defaultdict(int)
m=10**6+1
sieve=[-1]*m
n=IN()
a=sorted(LI())
for i in a:
    if d[i]==0:
        d[i]+=1
        for j in range(2*i,m,i):
            sieve[j]=1
    else:
        sieve[i]=1
ans=0
for i in a:
    if sieve[i]==-1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# revie series
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
divisible = [False for i in range(10**6+1)]
visited = [False for i in range(10**6+1)]
for x in A:
    if visited[x] == False:
        visited[x] = True
        cnt = 2*x
        while cnt <= 10**6:
            divisible[cnt] = True
            cnt += x
    elif visited[x] == True:
        divisible[x] = True

ans = 0
for x in A:
    if divisible[x] == False:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')


n = int(input())
seq = [int(x) for x in input().split()]
ans = 0
d = {}
for val in seq:
    try:
        d[val] += 1
    except:
        d[val] = 1
mm  = max(seq)
lst = [True for _ in range(mm+1)]
for val in seq:
    f = 2
    while val*f <= mm:
        lst[val*f] = False
        f += 1
ans = 0
for val in seq:
    if lst[val] and d[val] == 1:
        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

from collections import defaultdict
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    
    dd = defaultdict(int)
    #Aを昇順にソートしておく
    #昇順にすることで前から値iを取り出して以降のある範囲のiの倍数をもれなくチェックすることができる
    #チェックされた回数が2以上の値は自分以外の要素の倍数である（自分は自分自身の倍数であるからどの値も少なくとも1回はチェックされる）
    A.sort()

    #mx:=Aの最大値
    mx = A[-1]
    for i in A:
        #mxまでのiの倍数を調べる
        j = i
        while j <= mx:
            dd[j] += 1
            j += i
    cnt = 0
    for e in A:
        #チェックされた回数が1の要素つまり与えられた配列の中で自分自身でしか割り切れない要素の数が答え
        cnt += (dd[e] == 1) 
    print(cnt)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import defaultdict
from collections import Counter
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    
    dc = Counter(A)
    dd = defaultdict(int)

    A.sort()
    mx = A[-1]
    for i in A:
        j = i
        while j <= mx:
            dd[j] += 1
            j += i
    cnt = 0
    for e in A:
            cnt += (dd[e] == 1) 
    print(cnt)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


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

ok = [False] * (10**6 + 1)
for a in A:
    ok[a] = True

for i in range(10**6 + 1):
    if ok[i]:
        j = 2
        while i * j <= 10**6:
            ok[i * j] = False
            j += 1

for a, cnt in Counter(A).items():
    if cnt >= 2:
        ok[a] = False

print(sum(ok))

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int, input().split()))
A.sort()
chk = [True]*1000001
if n == 1:
    ans = 1
else:
    for i in range(n):
        num = A[i]
        if chk[num] == True:
            if i == 0:
                if num != A[i+1]:
                    ans += 1
                for j in range(num, 1000001, num):
                    chk[j] = False
            elif i == n-1:
                if num != A[n-2]:
                    ans += 1
            else:
                if num != A[i+1] and num != A[i-1]:
                    ans += 1
                for j in range(num, 1000001, num):
                    chk[j] = False
print(ans)

Submission status: Accepted

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

A.sort()
count=[0]*(A[-1]+1)
i=0
while i<N:
    j=A[i]
    if 2<=count[j]:
        i+=1
        continue
    k=1
    while j*k<=A[-1]:
        count[j*k]+=1
        k+=1
    i+=1

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

Submission status: Accepted

Solution code:
def primes(n,num):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    rec = {}
    ans = len(num)
    for i in num:
        if i in rec:
            if rec[i] == 1:
                ans -= 1
                continue
            else:
                if is_prime[i]:
                    ans -= 2
                else:
                    ans -= 1
                rec[i] = 1
                continue
        if not is_prime[i]:
            ans -= 1
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
        rec[i] = 0
    return(ans)
n = int(input())
a = list(map(int,input().split()))
a.sort()
ma = max(a)
ans = primes(ma,a)
print(ans)

Submission status: Accepted

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

a.sort()

table=[True]*1000001
count=0
if n==1:
  count=1
else:
  for i in range(0,n):
    pp=a[i]
    if table[pp]==True:
      if i==0:
        if pp!=a[i+1]:
          count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
      elif i==n-1:
        if pp!=a[n-2]:
          count+=1
      else:
        if pp!=a[i+1] and pp!=a[i-1]:
          count+=1
        for j in range(pp,1000001,pp):
          table[j]=False
      
print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()                  #エラトステネスの篩にかけるためソート
Amax = A[-1]
dp = [1]*(Amax+1)         #Aの最大値までのエラトステネスの篩を作る。
ans = 0
for i in range(len(A)-1):
  p = A[i]
  if dp[p] == 1:          #A[i]がA[j]の倍数でないかをエラトステネスの篩でチェック
    for q in range(Amax//p+1):
      dp[p*q] = 0         #A[i]の倍数をすべて0にする
    if A[i] != A[i+1]: 
      ans += 1            #A[i]が重複していなければカウント
if dp[Amax] == 1:         #重複チェック時にレンジオーバーするためAmaxだけ別で判定 
  ans += 1
print(ans)

Submission status: Accepted

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

max_num = max(As)
tfs = [0 for _ in range(max_num+1)]

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

result = 0
for A in As:
    if tfs[A] == 1:
        result+=1
print(result)

Submission status: Accepted

Solution code:
from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])
a = [int(s) for s in data[1].split()]
a = sorted(a)

max = a[-1]

l = [0]*(max+1)

for i in a:
    l[i] += 1
    if l[i] == 1:
        for j in range(i*2,max+1,i):
            l[j] = 2
print(l.count(1))

Submission status: Accepted

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

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

checked = [False] * (A_max+1)
ans = 0
for i in range(N):
    if i < N-1:
        if A[i] == A[i+1]:
            for j in range(A[i], A_max+1, A[i]):
                checked[j] = True
    if checked[A[i]]:
        pass
    else:
        ans += 1
        for j in range(A[i], A_max+1, A[i]):
            checked[j] = True

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N=int(input())
A=Counter(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for k in A.keys():
    if iscop[k]==False:
        continue

    for j in range(2,nmax//k+1):
        iscop[k*j]=False
ans=0
for k,v in A.items():
    if v<2 and iscop[k]:
        ans+=1

print(ans)

Submission status: Accepted

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

top = max(A)
out = [0]*(10**6+1)

for i in range(N):
  acm = A[i]
  while acm<=top:
    out[acm] += 1
    acm += A[i]
    
count = 0
for i in range(N):
  if out[A[i]] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = sorted(il())
    mx = max(A)
    st = set()
    cnt = collections.Counter(A)
    ret = 0
    for n in range(N):
        if A[n] not in st and cnt[A[n]] == 1:
            st.add(A[n])
            ret += 1

        a = 1
        while A[n] * a <= mx:
            st.add(A[n] * a)
            a+=1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

num = [0] * (10**6+10)
A.sort()
for a in A:
    if num[a]==1:
        num[a] = -1
    elif num[a] ==0:
        num[a]+=1
        for i in range(2,(A[n-1]//a)+1):
            num[i*a]=-1

print(num.count(1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]


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


def main():
    N = INT()
    A = LIST()
    A.sort()
    M = A[-1] + 1
    table = [0] * (M)

    for i in A:
        if table[i] == 0:
            table[i] = -1
            for j in range(i + i, M, i):
                table[j] = 1
        elif table[i] == -1:
            # 重複しているということ
            table[i] = -2
    # print(table)
    cnt = 0
    for i in range(N):
        if table[A[i]] == -1:
            cnt += 1
    print(cnt)

    return


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

    num = [True] * (max(A) + 1)
    appear = set()
    for a in A:
        if a not in appear:
            appear.add(a)
        else:
            num[a] = False

    for a in A:
        for i in range(a * 2, len(num), a):
            num[i] = False

    res = 0
    for a in A:
        if num[a]:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
#create date: 2020-06-28 12:09

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = na()
    d = [0] * (10**6+1)
    for ai in a:
        if d[ai] < 2:
            for i in range(1, (10**6//ai)+1):
                d[ai*i] += 1
    ans = 0
    for ai in a:
        if d[ai] == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=set()

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.add(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.add(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(A)

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

total = 10 ** 6 + 1

X = [0] * total

for a in A:
    for aa in range(a + a, total, a):
        X[aa] = 1

ans = 0
for i in range(1, total):
    if X[i] == 0 and c[i] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
div = [0] * 1000005

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

for num in A:
    if div[num] == 0:
        for i in range(num, 1000005, num):
            div[i] += 1
    else:
        div[num] += 1
ans = 0
for num in A:
    if div[num] == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

a_max = a[-1]
ans_list = [0] * a_max

ans = 0

for i in range(n-1):

    p = a[i]

    if ans_list[p-1] == 0:
        for q in range(1, (a_max//p)+1):
            ans_list[p*q-1] = 1
            
        if a[i] != a[i+1]:
            ans += 1

if ans_list[a_max-1] == 0:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().rstrip().split(' ')))
    M = 10**6 + 5
    cnt = [0 for _ in range(M)]
            
    for ai in a:
        if cnt[ai] != 0:
            cnt[ai] = 2
            continue
        for i in range(ai, M, ai):
            cnt[i] += 1
    ans = 0
    for ai in a:
        if cnt[ai] == 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  # if the same number appears as before, that number cannot be counted in the answer.
  if prev_num != i:
    for j in range(i * 2, THE_NUM, i):
      dp[j] = False
  else:
    dp[i] = False
  prev_num = i

ans = 0
for i in A:
  # the same number after the second will not counted in the answer.
  if dp[i] == True:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    _ = input()
    a_list = list(map(int, input().split()))
    res_set = set(a_list)
    # キーに要素、値に出現回数を持つカウンタ
    a_counter = Counter(a_list)
    for e in a_counter.items():  # e:(整数，出現回数)
        if e[1] == 1:
            for i in range(e[0] * 2, 10**6 + 1, e[0]):  # その整数を含まない倍数
                res_set.discard(i)
        else:
            for i in range(e[0], 2 * 10**6 + 1, e[0]):  # その整数を含む倍数
                res_set.discard(i)
    print(len(res_set))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
a_max=a[-1]
count=0
b=Counter(a)
count_list=[0]*(a_max)
for i in a:
  if b[i]==1:
    if count_list[i-1]==0:
      count+=1
      j=1
      while i*j<=a_max:
        count_list[i*j-1]+=1
        j+=1
  else:
    j=2
    while i*j<=a_max:
      count_list[i*j-1]+=1
      j+=1
print(count)

Submission status: Accepted

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

is_prime = [False] * (A_max+1)


for i in A_list:
    is_prime[i] = True

x = -1
for i in A_list:
    if not is_prime[i]:
        continue
    elif x == i:
        is_prime[i] = False
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    x = i

count = 0
for i in A_list:
    if is_prime[i]:
        count += 1


print(count)

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[-1]
count = 0
cnt_list = [1] * ((10 ** 6) + 1)
for i in range(len(A_list)-1):
    if cnt_list[A_list[i]] == 1:
        for j in range((A_max // A_list[i]) + 1):
            cnt_list[A_list[i] * j] = 0
        if A_list[i] != A_list[i+1]:
            count += 1
if cnt_list[A_list[-1]] == 1:
    count += 1
print(count)

Submission status: Accepted

Solution code:
# D
n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = max(a)
ans = [1 for _ in range(max_a + 1)]
b = -1#存在しない数
#エラトステネスの篩･･･有名な素数判別法

# 1  2  3  4  5  6  7  8  9 
# 11 12 13 14 15 16 17 18 19
#    ×　   ×  ×  ×     ×
#             :

for j in a:
    if b == j:  #行ったところはもう行かない
        ans[j] = 0
    divided = j + j
    while divided < max_a + 1:#jの倍数を0として記録する
        ans[divided] = 0
        divided += j
    b = j

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

Submission status: Accepted

Solution code:

import math

n = int(input())
given_lst = sorted(list(map(int,input().split())))
max_num = max(given_lst)
lst_status = [1 for _ in range(max_num+1)]


prev_e = -99999
for e in given_lst:
    if prev_e == e:
        lst_status[e] = 0
    divided_num = e + e
    while(divided_num <= max_num):
        lst_status[divided_num] = 0
        divided_num += e

    prev_e = e

ans = 0
for e in given_lst:
    if lst_status[e] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        if b[a[i]]:
            continue
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

print(ans)

Submission status: Accepted

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

d = {}
for a in A:
  d.setdefault(a,0)
  d[a] += 1
  
A = sorted(set(A))
t = [True] * (10 ** 6 + 1)
for a in A:
    if d[a] > 1:
        t[a] = False
    for i in range(a + a, 10 ** 6 + 1, a):
        t[i] = False
print(sum(1 for a in A if t[a]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()] 

c = Counter(a)
a.sort()
max_a = a[-1]
flag = [True for _ in range(max_a+1)]
ans = []
for i in a:
    if c[i] >= 2:
        flag[i] = False
    
    for j in range(i + i, max_a + 1, i):
        flag[j] = False
for i in a:
    if flag[i]:
        ans.append(i)
#print(ans)
print(len(ans))

Submission status: Accepted

Solution code:
N = int(input())
nums = list(map(int, input().split()))
nums.sort()
div_length = max(nums)+1
divisible_list = {}
#initialize
for i in range(0, div_length):
  divisible_list[i] = 0

#count divisible numbers
for fNum in nums:
  for j in range(fNum, div_length, fNum):
   	divisible_list[j] += 1

#check for numbers
answer = 0
for num in nums:
  if (divisible_list[num] == 1):
    answer += 1
print(answer)

Submission status: Accepted

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

C = {a:0 for a in A}

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

maxA = max(A)

D = {a:0 for a in A}

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

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter += 1
        
print(counter)

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 A}
for a in A:
    C[a] += 1
# D[a]=1: Aにaより小さいaの約数が存在する
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)

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    s = set()
    cnt = collections.Counter(arr)
    for i in range(n):
        if arr[i] in s:
            continue
        elif 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 arr:
        if i in s:
            continue
        ans += 1
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = int(1e6) + 10
sieve = [0] * int(MAX)
for i in a:
    sieve[i] += 1
ans = 0
for idx, val in enumerate(sieve):
    if val == 0:
        continue
    elif val > 1:
        sieve[idx] = 0
    else:
        ans += 1
    for i in range(idx * 2, MAX, idx):
        sieve[i] = 0
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


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

sifter = {i: True for i in range(1, A[N - 1] + 1)}
counter = Counter(A)
ans = 0
for A_i in A:
  if sifter[A_i]:
    if counter[A_i] == 1:
      ans += 1
    for i in range(A_i, A[N - 1] + 1, A_i):
      sifter[i] = False
      
print(ans)

Submission status: Accepted

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

An.sort()
max_num = An[-1]

primes = [True] * max_num
once = [False] * max_num

i = 0
while i < n:
    once[An[i] - 1] = True

    j = 1
    while i + j < n:
        if An[i] == An[i + j]:
            once[An[i] - 1] = False
            j += 1
        else:
            break

    i += j

for i in range(n):
    if primes[An[i] - 1]:
        base = An[i]
        idx = An[i] * 2 - 1
        while idx < max_num:
            primes[idx] = False
            idx += base

ans = [x and y for (x, y) in zip(once, primes)]
print(ans.count(True))

Submission status: Accepted

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

pre_a = 0
for a in A:
    if a == pre_a:
        S.discard(a)
    if a in S:
        j = a * 2
        while j <= M:
            S.discard(j)
            j += a
    pre_a = a
print(len(S))

Submission status: Accepted

Solution code:
sieve=[0]*1000009
n=int(input())
s=sorted(map(int,input().split()))
for i in s:
    if sieve[i]<2:
        for j in range(i,1000009,i):sieve[j]+=1
print(sum(sieve[i]==1for i in s))

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
a.sort()
era=[1]*(ma+1)
#0と1はふるいにかけられている。
cn=Counter(a)

count=0
for i in range(n):
  if era[a[i]]==0:continue
  else:
    era[a[i]]=0
    if cn[a[i]]==1:
      count+=1
    for j in range(2*a[i],ma+1,a[i]):
      era[j]=0
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

cnt_A = Counter(A_list)
A_list.sort()

max_num = A_list[-1]
cnt = 0


for i in range(len(A_list)):
    if A_list[i] not in cnt_A:
        continue
    
    if cnt_A[ A_list[i] ] == 1:
        cnt += 1
    
    for j in range( 2, max_num // A_list[i] + 1 ):
        n = A_list[i] * j
        
        if n in cnt_A:
            del cnt_A[n]


print(cnt)

Submission status: Accepted

Solution code:
import sys
N = int(input())
if N == 1:
    print(1)
    sys.exit()
A = [int(i) for i in input().split()]
ls = [0 for i in range(10**6+1)]
s = set()
for a in A:
    if ls[a] == 0:
        cur = 1
        while a*cur <= 10**6:
            ls[a*cur] += 1
            cur += 1
        s.add(a)
    else:
        ls[a] += 1
ans = 0
for a in A:
    if ls[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

cnt_A = Counter(A_list)
max_num = max(A_list)


for i in range(len(A_list)):
    if A_list[i] not in cnt_A:
        continue
    
    for j in range( 2, max_num // A_list[i] + 1 ):
        n = A_list[i] * j
        
        if n in cnt_A:
            del cnt_A[n]


ans = [ k for k,v in cnt_A.items() if v == 1 ]
print( len(ans) if ans else 0 )

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations

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

    multiples = [1] * (10 ** 6 + 1)

    bucket = Counter(A)
    res = 0

    for num in A:
        if bucket[num] == 1 and multiples[num] == 1:
            res += 1
        if multiples[num] == 1:
            for i in range(num, 10**6+1, num):
                multiples[i] = 0
    
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

cntList = [1] * (intList[-1] + 1)

i = 0
j = 1
ans = 0

while i < (N - 1):
  base = intList[i]
  j = 1
  num = base
  if cntList[num] == 1:
    while num <= intList[-1]:
      if cntList[num] == 1:
        cntList[num] = 0
      j += 1
      num = base * j
    if intList[i] != intList[i+1]:
      ans += 1
  i += 1

if cntList[intList[-1]] == 1:
  ans += 1
  
print(ans)

Submission status: Accepted

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  maxa=a[-1]+1
  tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if tf[a_i] ==False:
      for j in range(a_i,maxa,a_i):
        tf[j]=True
      if a_i  <a[i+1]:
        #print(a_i)
        r+=1
  if tf[-1] ==False:
    r+=1
  print(r)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N = II()
    A = LI()
    mx = max(A)+1
    B = np.zeros(mx)

    for a in A:
        for b in range(a, mx, a):
            B[b] = B[b] + 1
    # print(B)

    cnt = 0
    for a in A:
        if B[a] == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    x = sorted(list(set(p_list)))
    max_num = 10**6

    dp = [0] * (max_num + 1)
    for j in p_list:
        dp[j] += 1

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

    print(dp.count(1))
   
   
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    ng = [False] * (A[-1] + 1)
    check = [False] * (A[-1] + 1)
    for a in A:
        if check[a]:
            ng[a] = True
        check[a] = True

    if len(A) == 0:
        print(0)
        return
    MAX_PRIME = A[-1] + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in A:
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    ans = 0
    for a in A:
        if is_prime[a] and not ng[a]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()