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()))
MAX = 10**6+1

is_divided = [0]*MAX 
is_appeared = [0]*MAX

for i in range(n):
  if not is_divided[a[i]]:
    if not is_appeared[a[i]]:
      is_appeared[a[i]] = 1
      k = a[i]*2
      while k < MAX:
        is_divided[k] = 1
        k += a[i]
    else:
      is_divided[a[i]] = 1
      
ans = 0      
for i in range(n):
  if not is_divided[a[i]]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
INF = 10**6+1
lis = [1]*INF
exist = [0]*INF
for i in range(N):
    a = A[i]
    if lis[a] and exist[a] < 1:
        q = 2
        while a*q < INF:
            lis[a*q] = 0
            q += 1
    exist[a] += 1
cnt = 0
for a in A:
    if lis[a] and exist[a] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

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

divisible = [False for _ in range(int(1e6+1))]
cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
    if divisible[a] == False and cnt[a] <= 1:
        for i in range(a+a, len(divisible), a):
            divisible[i] = True
ans = 0
for a in A:
    if divisible[a] is False and cnt[a] <= 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
M = 10 ** 6
A = list(map(int, input().split()))
B = [0] * (M + 1)
for a in A:
    B[a] +=1
C = [1] * (M + 1)
A = set(A)
for i in A:
    for j in range(i, M + 1, i):
        if i == j:
            if B[i] > 1:
                C[i] = 0
        else:
            C[j] = 0
ans = 0
for a in A:
    if C[a]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
n = int(input())
A = list(map(int,input().split()))
a_ = max(A)
A_ = list(set(A))
dp = [True] * (a_+1)
C = [0] * (a_+1)
for a in A:
    C[a]+=1
A_.sort()
ans = 0

for a in A_:
    tmp = a
    if dp[tmp]:
        tmp += a
        while tmp <= a_:
            dp[tmp] = False
            tmp += a
#print(dp)
for a in A_:
    if dp[a]:
        if C[a]==1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
minNum = A[0]
maxNum = A[N - 1]
countList = [0]*(10**6 + 1)
answer = 0

# Aにnがm個あるときcountList[n] = m
for i in A:
  countList[i] += 1

for j in range(minNum, maxNum + 1):
  # Aにjが含まれていれば、jの倍数をすべてcountListから除外
  # jの倍数pはjで割り切れるので除外可能
  # pの倍数qはjでも割り切れるのでjの時の処理によって除外される
  if countList[j] > 0:
    for k in range(2 * j, maxNum + 1, j):
      countList[k] = 0
  # jが2個以上ある場合にはそれを正解としてカウントしない
  if countList[j] == 1:
      answer += 1

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
minNum = A[0]
maxNum = A[N - 1]
countList = [0]*(10**6 + 1)
answer = 0

# Aにnがm個あるときcountList[n] = m
for i in A:
  countList[i] += 1

for j in range(minNum, maxNum + 1):
  # Aにjが含まれていれば、jの倍数をすべてcountListから除外
  # jの倍数pはjで割り切れるので除外可能
  # pの倍数qはjでも割り切れるのでjの時の処理によって除外される
  if countList[j] > 0:
    for k in range(2 * j, 10**6 + 1, j):
      countList[k] = 0
  # jが2個以上ある場合にはそれを正解としてカウントしない
  if countList[j] == 1:
      answer += 1

print(answer)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
countList = [0]*(10**6 + 1)
answer = 0

# Aにnがm個あるときcountList[n] = m
for i in A:
  countList[i] += 1

for j in range(10**6 + 1):
  # Aにjが含まれていれば、jの倍数をすべてcountListから除外
  # jの倍数pはjで割り切れるので除外可能
  # pの倍数qはjでも割り切れるのでjの時の処理によって除外される
  if countList[j] > 0:
    for k in range(2 * j, 10**6 + 1, j):
      countList[k] = 0
  # jが2個以上ある場合にはそれを正解としてカウントしない
  if countList[j] == 1:
      answer += 1

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
from operator import mul
from functools import reduce


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [1] * 1000001
for a in A:
    memo[a] = 1
A.sort()
a_max = max(A)
for a in A:
    if not memo[a]:
        continue
    for i in range(a * 2, a_max + 1, a):
        memo[i] = -1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
mod = 10**9 + 7

#maincode-------------------------------------------------

n = ini()
a = inl()
A = 10**6 + 5
b = [0] * A
ans = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n=int(input())
    A=list(map(int, input().split()))
    counts=[0]*(10**6+5)
    for AA in A:
        counts[AA]+=1
    ans=0
    for i in range(1,10**6+5):
        if counts[i]>0:
            for j in range(i+i,10**6+5,i):
                counts[j]=-1
        if counts[i]==1:
            ans+=1
    print(ans)
        

        
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
dp = [0] * a[-1]
c = Counter(a)
for i in a:
    for j in range(i, a[-1]+1, i):
        dp[j-1] += 1
ans = 0
for i in a:
    if dp[i-1] == 1 and c[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
num_of_nums = int(input())
nums = sorted(map(int, input().split(' ')))

d = {}

for num in nums:
	if num not in d:
		d[num] = [0, False]
	
	d[num][0] += 1


biggest_number = nums[-1]

for num in nums:
	if d[num][0] > 1:
		d[num][1] = True
	
	multiplier = 2
	product = num * multiplier
	
	while product <= biggest_number:
		if product in d:
			d[product][1] = True
		
		multiplier += 1
		product = num * multiplier

answer = 0
for key in d:
	if not d[key][1]:
		answer += d[key][0]

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_max = A[-1]
dp = [1]*(A_max+1)
# dp[i] = 1: iはAのどの要素の倍数でもない
# dp[i] = 0: iはAの要素の倍数である
for a in A:
    if not dp[a]:
        continue
    y = a*2
    while y <= A_max:
        dp[y] = 0
        y += a
# Aの要素それぞれについて、dp[a] = 1ならよいが
# Aの要素ai,ajでai=ajとなる場合、上の篩では通過しているのに
# 条件を満たさない
cnt = dict(Counter(A))
ans = 0
for a in A:
    if cnt[a] >= 2:
        continue
    if dp[a]:
        ans += 1
print(ans)

Submission status: Accepted

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

for x in A:
  if cnt[x] != 0:
  	cnt[x] = 2
  else:
    for i in range(x, MAX, x):
      cnt[i] += 1
  
ans = 0
for x in A:
  # 2回以上通った数字 (cnt[x]>1) は，その数字より小さい約数が存在する (割り切れる他の数が存在する)。
  if cnt[x] == 1:  
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
nums = list(map(int, input().split()))
nums.sort()
checked = [0 for _ in range(nums[-1]+1)]
answer = 0
for i in range(N-1):
  if checked[nums[i]] == 1:
    continue
  else:
    if nums[i] != nums[i+1]:
      answer += 1
    count = 1
    temp = nums[i]
    while(temp <= nums[-1]):
      checked[temp] = 1
      count += 1
      temp= nums[i]*count
if checked[nums[-1]] == 0:
  answer += 1
print(answer)

Submission status: Accepted

Solution code:
#https://at274.hatenablog.com/entry/2020/06/29/181102
import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
A=set(A)
MAX_A=10**6
X=[0]*(MAX_A + 1)#0-MAX_Aまでの整数がAの倍数で何回割られるか
for i in A:
  for j in range(i,MAX_A + 1,i):
    X[j]+=1

#割られた回数が1つしかないものはその数自身で割ったのでカウント
#ただし複数ある場合は除外
ans = len([a for a in A if (X[a] == 1) and (c[a] == 1)])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

A.sort()

count = Counter(A)

divisible = [False] * (max_a + 1)

ans = 0

for a in A:
    if divisible[a]:
        continue
    for i in range(1, max_a // a + 1):
        divisible[i * a] = True
    if count[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = [0] * 1000005
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,1000005,x):
            cnt[i] += 1

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

print(ans)

Submission status: Accepted

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

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

cnt = [0] * 1000005
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,1000005,x):
            cnt[i] += 1

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

print(ans)

Submission status: Accepted

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

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

cnt = [0] * 1000005
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,1000005,x):
            cnt[i] += 1

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

print(ans)

Submission status: Accepted

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

cnt = [0] * 1000005
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,1000005,x):
            cnt[i] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = list(map(int, input().split()))
dp = [0] * (pow(10, 6) + 5)
heapq.heapify(a)
heapq.heappush(a, 1000003)
ans = -1
y = 0
for _ in range(n + 1):
    x = heapq.heappop(a)
    if x == y and dp[x] == 2:
        dp[x] = 1
        ans -= 1
        continue
    elif dp[x] == 0:
        ans += 1
        dp[x] = 2
        i = 2
        while i * x <= 1000000:
            dp[i * x] = 1
            i += 1
    y = x
print(ans)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = sorted([int(i) for i in input().split()])
cnt = collections.Counter(a)
max_i = a[-1] + 1
for i in a:
  if cnt[i] >= 2:
    del cnt[i]
  for j in range(i*2, max_i, i):
    del cnt[j]
print(len(cnt))

Submission status: Accepted

Solution code:
#D - Not Divisible
import collections
N = int(input())
a = list(map(int,input().split()))
a = sorted(a,reverse = False)

#collections.Counterは存在しない値を指定すると0を返す
cnt = collections.Counter(a)
m = max(a)+1
for i in a:
    if cnt[i] >= 2:
        del cnt[i]
    for j in range(i*2,m,i):
        del cnt[j]
print(len(cnt.keys()))

Submission status: Accepted

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

a.sort()

x=a[-1]

dp=[0 for _ in range(x+1)]

for b in a:
  y=b
  while y<=x:
    dp[y]+=1
    y+=b

    
ans=0
for c in a:
  if dp[c]==1:
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
an=[int(i) for i in input().split()]
an.sort()
maxA=an[-1]

ans_table=[0]*(maxA+1)


for ai in an:
    for k in range(1,int(maxA/ai)+1):
        ans_table[ai*k]+=1
ans=0
for ai in an:
    if ans_table[ai]==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
am=max(a)
dp=[[True,0] for _ in range(am+1)]
count=0
for i in a:
    if dp[i][0]==False:
        continue
    else:
        if dp[i][1]==1:
            dp[i][0]=False
            count-=1
        else:
            dp[i][1]=1
            count+=1
            for j in range(2*i,am+1,i):
                dp[j][0]=False
print(count)

Submission status: Accepted

Solution code:
import numba
from numba import njit, b1, i4, i8, f8
import numpy as np  # noqa

N = int(input())
A = np.array([int(x) for x in input().split()], dtype=np.int32)


@njit((i4[:], ), cache=True)
def main(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret


print(main(A))

Submission status: Accepted

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

count = [0] * (M + 1)
for i in range(N):
    count[A[i]] += 1

check = [True] * (M + 1)
for a in range(1, M + 1):
    if count[a] > 0 and check[a] == True:
        for k in range(2, M // a + 1):
            check[a * k] = False      

ans = 0
for i in range(N):
    if count[A[i]] == 1 and check[A[i]] == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain
import numpy as np

# from itertools import combinations as comb
# form bisect import bisect_left, bisect_right, insort_left, insort_right
# from collections import Counter


def solve(N: int, A: "List[int]"):
    check = np.zeros(max(A) + 1, dtype=np.uint8)
    for ai in A:
        if check[ai] == 0:
            check[ai::ai] += 1
        else:
            check[ai] = 2

    answer = 0
    for ai in A:
        if check[ai] == 1:
            answer += 1

    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    # N, A = map(int, line.split())
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, A)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

D = [0] * (10**6 + 1)
A.sort()
for i in range(N):
    D[A[i]] += 1
    
ans = 0
for i in range(1, 10**6+1):
    if D[i]:
        if D[i]==1:
            ans += 1
        for j in range(i,A[-1]+1,i):
            D[j] = 0
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = read_ints()
    max_A = max(A)
    is_divisible = [False]*(max_A+1)
    A.sort()
    answer = 0
    last_a = None
    for a in A:
        if a == last_a:
            is_divisible[a] = True
        for step in range(2*a, max_A+1, a):
            is_divisible[step] = True
        last_a = a
    return sum([not is_divisible[a] for a in A])


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

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

def primes(array,n):
    C = collections.Counter(array)
    count = 0
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    for i in array:
      if is_prime[i]:
        if C[i] == 1: count += 1
        for j in range(i, n + 1, i):
            is_prime[j] = False
    return count

n = int(input())
A = list(map(int,input().split()))
A.sort()
data = [0] * (10**6+1)


print(primes(A,10**6))

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    a = LI()
    lst = [0 for _ in range(10**6+1)]
    a.sort()
    cnt = 0
    st = set()

    for i in a:
        if lst[i] == -1:
            pass
        elif lst[i] == 0:
            cnt += 1
            lst[i] = 1
            time = 10**6//i
            for j in range(2,time+1):
                lst[i*j] = -1
        elif lst[i] == 1:
            st.add(i)
    
    ans = cnt - len(st)
    print(ans)
main()

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
l = [0]*(10**6+1)
M = max(a)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N = I()
A = LI()
A.sort()
cnt = collections.Counter(A)
end = A[-1] + 1

for a in A:
    if cnt[a] >= 2:
        del cnt[a]
    for i in range(a * 2, end, a):
        del cnt[i]

print(sum(cnt.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


N = I()
A = LI()
A.sort()
cnt = collections.Counter(A)
MAX = A[-1] + 1
# end = A[-1] ** 0.5

for a in A:
    if cnt[a] >= 2:
        del cnt[a]
    for i in range(a * 2, MAX, a):
        del cnt[i]

print(sum(cnt.values()))

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=[int(x) for x in input().split()]
A=sorted(A)
maxA=max(A)
ans=0
so_list=[1]*(maxA+1)
index=0
i=0

while(i<N):
    flag=0
    now=A[i]
    if so_list[now]==1:
        index=0
        flag=1
        while(index+now<=maxA):
            so_list[index+now]=0
            index+=now
    right=bisect.bisect_right(A,now)#同じ数字はいくつある？
    if right-i==1:
        if flag==1:
            ans+=1
            #print(now)
        i=right
    else:
        i+=1

print(ans)

Submission status: Accepted

Solution code:
def abc170d_not_divisible():
    n = int(input())
    cnt = 0
    a = sorted(list(map(int, input().split())))
    flgs = [True] * (a[-1]+1)
    if n == 1:
        print(1)
        return
    for i in range(n):
        if i != n - 1 and a[i] == a[i + 1]:
            flgs[a[i]] = False
            continue
        for j in range(a[i] * 2, a[-1] + 1, a[i]):
            flgs[j] = False
        if flgs[a[i]]:
            cnt += 1
    print(cnt)


abc170d_not_divisible()

Submission status: Accepted

Solution code:
import collections
n = int(input())
line = list(map(int, input().split( )))
arr = sorted(line)
coll = collections.Counter(arr)
#最大値
Ma = arr[-1]
#ソートしたn番目のやつの判定はn+1以降でおっけい. 
#同じ数字がある敵は無視
s = set()
for i in range(n):
  if coll[arr[i]] >= 2:
    s.add(arr[i])
  for j in range(2, Ma//arr[i]+1):
    s.add(arr[i]*j)
cnt = 0

#print(s)
for a in arr:
  if a in s: continue
  cnt += 1
print(cnt)

Submission status: Accepted

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

A.sort()

dp=[False]*(10**6*2)
ans=0
for idx,i in enumerate(A):
  if dp[i]:continue
  tmp=i
  ans+=1
  while tmp<10**6*2-1:
    dp[tmp]=True
    tmp+=i
  if idx!=len(A)-1 and A[idx+1]==i:
    ans-=1
print(ans)

Submission status: Accepted

Solution code:
def main():

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

    A = sorted(A)
    Amax = A[-1]
    count = [0 for _ in range(Amax+1)]

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

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
Amax=A[-1]
dp=[True]*(Amax+1)
ans=0
for i in range(N-1):
    p=A[i]
    if dp[p]:
        for j in range(1,Amax//p+1):
            dp[p*j]=False
        if p!=A[i+1]:
            ans+=1
if dp[Amax]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
max_a = max(A) + 1
counter = [0 for _ in range(max_a)]
 
for i in A:
    for j in range(i, max_a, i):
        counter[j] += 1
res = 0
 
for a in A:
    if counter[a] == 1:
        res += 1
#print(counter)
print(res)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
max_a = max(A) + 1
counter = [0 for _ in range(max_a)]

for i in A:
    for j in range(i, max_a, i):
        counter[j] += 1

res = 0

for a in A:
    if counter[a] == 1:
        res += 1

print(res)

Submission status: Accepted

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

a.sort()
c=[0]*(10**6+1)
ans=0
for i in range(n):
    x=a[i]
    if c[x]:
        continue
    else:
        if i<=n-2:
            if x!=a[i+1]:
                ans+=1
        else:
            ans+=1
        for j in range(x,10**6+1,x):
            c[j]=1
print(ans)

Submission status: Accepted

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

if N == 1:
  print(1)
  exit()

flag = [0]*(10**6+5)
for i in range(N):
  flag[A[i]] = 1

for i in range(N):
  if flag[A[i]] == 0:
    continue
  if i>0 and A[i]==A[i-1]:
    flag[A[i]] = 0
    continue
  for num in range(A[i]*2,A[-1]+1,A[i]):
    flag[num] = 0
  
print(sum(flag))

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
m=A[-1]
dp=[True]*m
ans,p,q=0,0,False
for a in A:
  if p==a and q:
    ans-=1
    q=False
  if dp[a-1]:
    p,q=a,True
    ans+=1
    aa=a
    while m>=aa:
      dp[aa-1]=False
      aa+=a
print(ans)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    C = [0] * (10**6 + 1)
    for a in A:
        if C[a] == 1:
            C[a] = -1
            continue
        if C[a] == -1:
            continue
        C[a] = 1
        for b in range(a + a, 10 ** 6 + 1, a):
            C[b] = -1
    ans = 0
    for a in A:
        if C[a] == 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

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

x=[0]+[True]*10**6

for i in range(len(a)):
  cnt=a[i]
  if x[a[i]]==True and (i==0 or a[i]!=a[i-1]) and (i==(n-1) or a[i]!=a[i+1]):
        ans+=1
        while cnt<=10**6:
          x[cnt]=False
          cnt+=a[i]
          
  elif x[a[i]]==True and ((i!=0 and a[i]==a[i-1]) or (i!=(n-1) and a[i]==a[i+1])):
        while cnt<=10**6:
          x[cnt]=False
          cnt+=a[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (10**6+1)
ans = 0
for a in A:
    if B[a] == 0:
        ans += 1
        B[a] = 2
        tmp = 2*a
        while tmp <= 10**6:
            B[tmp] = 1
            tmp += a
    elif B[a] == 2:
        B[a] = 1
        ans -= 1
print(ans)

Submission status: Accepted

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

#篩
M = 10**6+ 10
c = [0] * M
for i in range(N):
    if c[A[i]-1] >= 1:
        c[A[i]-1] = c[A[i]-1] + 1
    else:
        for j in range(1, M//A[i] + 1):
            c[A[i]*j-1] += 1

#チェック
ans = 0
for i in range(N):
    if c[A[i]-1] <= 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
A.sort()

log=[0]*10**6
ans=len(A)

for a in A:
    if log[a-1]==0:
        log[a-1]=-1
        for index in range(a-1+a,10**6,a):
            log[index]=1
    elif log[a-1]==-1:
        log[a-1]=1
        ans-=2
    else:
        ans-=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
data = [0 for _ in range(1000001)]
for x in a:
    data[x] += 1

ans = 0
for i in range(1,1000001):
    if not data[i]:continue
    if data[i] == 1:ans += 1
    j = i
    while j < 1000001:
        data[j] = 0
        j += i

print(ans)

Submission status: Accepted

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A)-1]
valid = [True] * (maxA+1)

for i in range(len(A)):
    if valid[A[i]] == False:
        continue
    if i != 0 and A[i-1] == A[i]:
        valid[A[i]] = False
    else:
        for j in range(A[i]*2, maxA+1, A[i]):
            valid[j] = False

count = 0
for i in range(len(A)):
    if valid[A[i]] == True:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
maxA = A[len(A)-1]
valid = [True] * maxA

for i in range(len(A)):
    if valid[A[i]-1] == False:
        continue
    if i != 0 and A[i-1] == A[i]:
        valid[A[i]-1] = False
    else:
        for j in range(A[i]*2, maxA+1, A[i]):
            valid[j-1] = False

count = 0
for i in range(len(A)):
    if valid[A[i]-1] == True:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
m=a[-1]+1
cnt=[0]*m
for ai in a:
  if cnt[ai]!=0:
    cnt[ai]+=1
    continue
  for i in range(ai,m,ai):
    cnt[i]+=1
ans=0
for ai in a:
  ans+=(cnt[ai]==1)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
maxA = max(A)
dp = {}
for each in A:
    dp[each] = True
for i in range(N):
    if dp[A[i]]:
        tmp = 2 * A[i]
        while maxA >= tmp:
            if tmp in dp and dp[tmp]:
                dp[tmp] = False
            tmp += A[i]
counter = 0
t = Counter(A)
for i in range(N):
    if dp[A[i]] and t[A[i]] == 1:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
maxA = max(A)
dp = {}
for i in range(1, maxA+1):
    dp[i] = True
for i in range(N):
    if dp[A[i]]:
        tmp = 2 * A[i]
        while maxA >= tmp:
            if dp[tmp]:
                dp[tmp] = False
            tmp += A[i]
counter = 0
t = Counter(A)
for i in range(N):
    if dp[A[i]] and t[A[i]] == 1:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
m = max(a)
c = [0]*(m+1)

for x in a:
    c[x] += 1

for i in range(1, m+1):
    if c[i] > 0:
        if c[i] > 1:
            c[i] = 0
        j = i + i
        while j <= m:
            c[j] = 0
            j += i    
ans = sum(c)
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    ls = [0 for i in range(a[-1])]
    for i in range(n):
        if ls[a[i]-1] == -1:
            continue
        elif ls[a[i]-1]==1:
            ls[a[i]-1] = -1
        else:
            ls[a[i]-1] = 1
            for j in range(2,a[-1]//a[i]+1):
                ls[a[i]*j-1] = -1
    ans = 0
    for i in range(len(ls)):
        if ls[i]==1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    cnt = [0]*(10**6+1)
    for a in A:
        if cnt[a]==0:
            x = 2*a   
            while x <= 10**6:
                cnt[x] += 1    
                x += a
        cnt[a] += 1
    print(len([1 for a in A if cnt[a]==1]))

if __name__ == '__main__':
    main()