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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=1)
bl=[0]*(10**6+1)
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            B.append(x)
        else:
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
            xx=x
            while x<=10**6:
                bl[x]=1
                x+=xx
    else:
        B.append(x)


ans=0
for x in B:
    ans+=not bl[x]
    xx=x
    while x<=10**6:
        bl[x]=1
        x+=xx
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    elif not checks[a]:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)

Submission status: Accepted

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

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

A.sort()

is_ok = [False] * (10 ** 6 + 1)
is_exist = [False] * (10 ** 6 + 1)

for a in A:
    if is_exist[a]:
        is_ok[a] = False
    else:
        is_exist[a] = True
        is_ok[a] = True
        for i in range(1, 10 ** 6 // a + 1):
            if a * i <= 10 ** 6:
                is_exist[a * i] = True

print(is_ok.count(True))

Submission status: Accepted

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

si = set()
do = set()
for i in range(n):
    if(a[i] in si):
        do.add(a[i])
    else:
        si.add(a[i])
m = max(si)

li = [1]*m

for i in si:
    if(i in do):
        li[i-1] = 0
    for j in range(i*2,m+1,i):
        li[j-1] = 0

ans = 0
for i in si:
    if(li[i-1]==1):
        ans += 1
print(ans)

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 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)

    return divisors

def solve():
    N = II()
    A = LI()

    mx = max(A)

    memo = [0] * (mx + 1)
    for a in A:
        for i in range(a, mx+1, a):
            memo[i] += 1
    # print(memo)

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

num = 10 ** 6 + 1 #適当に値を入れる
L = [0 for i in range(num)]
ans = 0
N = int(input())
A = getlist()
for i in range(N):
	L[A[i]] += 1

for i in range(num):
	if L[i] >= 1:
		if L[i] == 1:
			ans += 1
		c = 2
		while i * c <= num - 1:
			L[i * c] = 0; c += 1

print(ans)

Submission status: Accepted

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

mx_a = max(A)
cand = [0] * (mx_a + 1)

for i in range(N):
    j = 1
    while True:
        if A[i] * j > mx_a:
            break
        cand[A[i] * j] += 1
        j += 1

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え
    import random
    N = int(input())
    #N, K = map(int, input().split())
    A = list(map(int, input().split())) #1行ベクトル
    #A=[random.randrange(1,10**6) for _ in range(100)]
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    #A=[i+1 for i in range(1,200000)]
    A.sort()
    ma=A[-1]
    l=[0]*(ma+10)
    ca=Counter(A)
    count=0
    pa=0
    f=0
    for a in A:
        if l[a]==0:
            if ca[a]==1:
                count+=1
            i=a
            while i<ma+10:
                l[i]=1
                i+=a
        pa=a
    print(count)

    #print(A,ma)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

c = Counter(A)

yes_or_no = [True for i in range(A[n-1]+1)]

for a in A:
  t = a*2
  while t <= A[n-1]:
    yes_or_no[t] = False
    t += a
ans = 0
for a in A:
  if c[a] == 1 and yes_or_no[a] == True:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    MX = 10**6
    ans = []
    a_map = Counter(A)

    is_prime = [True] * (MX + 1)
    is_prime[0] = False
    is_prime[1] = 1 in a_map
    for i in range(1, MX + 1):
        if not is_prime[i]:
            continue
        if i not in a_map:
            continue
        for j in range(i * 2, MX + 1, i):
            is_prime[j] = False

    ans = 0
    for i in range(N):
        if is_prime[A[i]] and a_map[A[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
arr = list(map(int,input().split()))
arr.sort()
maxn = 1000005
d = [0 for i in range(maxn)]
prime = [True for i in range(maxn)]
for i  in range(n):
	cur = arr[i]
	d[cur]+=1
	if prime[cur]==True and d[cur]==1:
		for j in range(2*cur,len(prime),cur):
			prime[j] = False
ans = 0
for i in arr:
	if prime[i]==True and d[i]==1:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from functools import lru_cache, reduce
from math import gcd
from operator import add, itemgetter, mul, xor

import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

counter = Counter(A)
A.sort()

dp = [True] * (max(A) + 10)
ans = 0
for a in A:
    if not dp[a]:
        continue
    if counter[a] == 1:
        ans += dp[a]
    j = a
    while j < len(dp):
        dp[j] = False
        j += a
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    searched = [0 for _ in range(10 ** 6 + 1)]
    ans = 0
    for i in range(1, 10 ** 6 + 1):
        if counter[i] == 0:
            continue
        if searched[i] == 0 and counter[i] == 1:
            ans += 1
        for j in range(1, ((10 ** 6) // i) + 1):
            searched[i * j] = 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    n = int(input())
    a= list(map(int, input().split()))
    a.sort()
    ans = 0
    flag = [1]*(10**6+1)
    for i in range(n):
        if (flag[a[i]]==0):
            continue
        tmp = a[i]
        while tmp < 10**6+1:
            flag[tmp] = False
            tmp += a[i]
        if i<n-1:
            if (a[i+1]==a[i]):
                continue
        ans += 1
    #x = collections.Counter(a)
    #ans = 0
    #for i in a:
        #if (flag[i]==1):
            #ans += 1
            #flag[i]=0
            #if (x[i]>1):
                #ans -=1
    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from math import sqrt
from sys import stdin, stdout
out = lambda o: stdout.write("{}\n".format(o))


def solve(a):
    a.sort()
    size = a[-1] + 1

    seive = [1] * size

    seen = set()
    for item in a:
        if item in seen:
            seive[item] = 0
        seen.add(item)

    for item in a:
        for j in range(2 * item, size, item):
            seive[j] = 0

    return sum(map(lambda x: seive[x], a))


if __name__ == "__main__":
    n = int(stdin.buffer.readline())
    a = [int(x) for x in stdin.buffer.readline().split()]
    out(solve(a))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
nmax = 10 ** 6 + 1
cnt = [False] * nmax
ans = 0
for i, x in enumerate(a):
    if cnt[x]:
        continue
    if i == n - 1 or a[i + 1] > x:
        ans += 1
    xx = x
    while xx < nmax:
        cnt[xx] = True
        xx += x

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ok=[0]*(a[-1]+1)
for i in range(n):
  ok[a[i]]+=1
for i in range(n):
  if ok[a[i]]>1:
    ok[a[i]]=0
  elif ok[a[i]]==0:
    continue
  j=a[i]
  while 1:
    j += a[i]
    if j > a[-1]:
      break
    ok[j]=0
    
print(sum(ok))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
count = [0 for _ in range(10**6+10)]
for a in A:
    if count[a] > 1:
        continue
    for x in range(0, 10**6+10, a):
        count[x] += 1
ans = 0
for a in A:
    if count[a] == 1:
        ans += count[a]
print(ans)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())           
a.sort()                                           
s = set()                                          
checked = set()                                    
dup = set()                                        
count = 0                                          
for x in a:                                        
    if x in s:                                     
        if x in checked:                           
            dup.add(x)                             
        continue                                   
    count += 1                                     
    checked.add(x)                                 
    for i in range(1, 10**6 // x + 1):             
        s.add(x * i)                               
                                                   
print(count - len(dup))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


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)
    return divisors


def solve():
    _ = int(rl())
    A = list(map(int, rl().split()))
    
    a_set = set()
    memo = set()
    for ai in A:
        if ai in a_set:
            memo.add(ai)
            if ai == 1:
                print(0)
                return
        else:
            a_set.add(ai)
    if 1 in a_set:
        print(1)
        return
    
    counter = [0] * (10 ** 6 + 1)
    for ai in A:
        for m in range(ai, 10 ** 6 + 1, ai):
            counter[m] += 1
    
    ans = 0
    for ai in A:
        if counter[ai] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

import numpy as np
from collections import Counter
from numba import njit




N = int(input())
A = np.array(readline().split(), np.int32)

count = np.zeros((A.max() + 1))
for a in A:
    if count[a] > 1:
        continue
    count[::a] += 1

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

print(ret)

Submission status: Accepted

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

import sys
from math import gcd
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, *A = map(int, read().split())
A = sorted(A)
M = pow(10, 6) + 1
divs = [False] * M
cnt = 0
for i, a in enumerate(A):
    if divs[a]:
        continue

    if i == N - 1 or a != A[i + 1]:
        cnt += 1

    acc = a
    while acc < M:
        divs[acc] = True
        acc += a
print(cnt)

Submission status: Accepted

Solution code:
n,x=int(input()),10**6+100
a,b,c=list(map(int,input().split())),[0]*(2*x),0
for i in a:
    b[i]+=1
for i in range(x):
    c+=1 if b[i]==1 else 0
    if b[i]==0:
        continue
    for j in range(1,x):
        if i*j>=x:
            break
        b[i*j]=0
print(c)

Submission status: Accepted

Solution code:
INF=10**6+1
n,*l=map(int,open(0).read().split())
from collections import *
c=Counter(l)
l=sorted(c.keys())
a=[]
b=[0]*INF
for i in l: b[i]=1  
for i in l:
  if b[i]:
    if c[i]<2: a+=[i]
    for j in range(2*i,INF,i): b[j]=0
print(len(a))

Submission status: Accepted

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

A.sort()
max_num = A[-1]
counter = Counter(A)
s = set()
cnt = 0
for a in A:
    if a in s:
        continue
    if counter[a] == 1:
        cnt += 1
    idx = 1
    while a * idx <= max_num:
        s.add(a * idx)
        idx += 1
print(cnt)

Submission status: Accepted

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

    N = int(input())
    A = list(map(int, input().split()))
    counter_A = Counter(A)
    flag = [True] * 1000001

    count = 0
    for i in sorted(counter_A.keys()):
        if counter_A[i] == 1 and flag[i]:
            count += 1
        multiple = i
        while multiple < 1000001:
            flag[multiple] = False
            multiple += i

    print(count)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import Counter
from itertools import accumulate

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    # 倍数リストを保持して、チェックしていく
    B = [0] * (A[N-1]+1)
    for i in range(N):
        j = A[i]
        while j <= A[N-1]:
            B[j] += 1
            j += A[i]
    # print(B)
    ans = 0
    for i in range(N):
        if B[A[i]] == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

A.sort()
b = [0]*(10**6+1)

for a in A:
  b[a] += 1
  if b[a] == 1:
    for i in range(2*a,10**6+1,a):
      b[i]+=100
print(b.count(1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter, defaultdict
def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    T = [False]*(10**6+1)
    A.sort()
    Z = [False]*(10**6+1)
    ans = 0
    for a in A:
        if CA[a] == 1 and not T[a]:
            ans += 1
        if not Z[a]:
            Z[a] = True
            for i in range(1, 10**6+1):
                if i*a > 10**6:
                    break
                T[i*a] = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = 10 ** 6 + 1
flg_lst = [False] * MAX
res = 0
for i in range(n):
    if flg_lst[a[i]]:
        continue
    if i + 1 == n or a[i+1] != a[i]:
        res += 1
    for j in range(a[i], MAX, a[i]):
        flg_lst[j] = True
print(res)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
B = [0]*(A[-1]+1)
ans = 0
for i,a in enumerate(A):
    if B[a]:
        continue
    else:
        if i+1 == n or A[i+1] != a:
            ans += 1
        x = a
        while x <= A[-1]:
            B[x] = 1
            x += a
print(ans)

Submission status: Accepted

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

    count = 0
    for ix, a in enumerate(A):
        if sieve[a] == 0:
            if ix == len(A) - 1 or a != A[ix+1]:
                count += 1
        else:
            continue
        intermediate_a = a
        while intermediate_a < sieve_len:
            sieve[intermediate_a] += 1
            intermediate_a += a
    print(count)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

table = [0 for i in range(10**6 + 1)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el] != 0:
        continue
    else:
        if el != a[i + 1]:
            ans += 1
    idx = el
    while idx <= 10**6:
        table[idx] += 1
        idx += el

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    M = 10 ** 6
    B = [True] * (M + 1)
    B[0] = False
    ans = 0
    for i in range(N):
        if not B[A[i]]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[A[i]] = False
        else:
            ans += 1
        for n in range(2 * A[i], M + 1, A[i]):
            B[n] = False

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnt = [0]*(10**6+10)
for a in al:
    if cnt[a]>1:
        continue
    for i in range(0,10**6+10,a):
        cnt[i] += 1

res = 0
for a in al:
    if cnt[a]==1:
        res += 1
print(res)

Submission status: Accepted

Solution code:

import collections

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

    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    m = max(A)
    S = set()

    ans = 0
    for i in range(n):
        a = A[i]

        if a in S:
            continue

        if D[a] == 1:
            ans += 1

        num = a
        while num <= m:
            S.add(num)
            num += a

    print(ans)


main()

Submission status: Accepted

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

a.sort()
li = [True] * (10**6 + 10)
ans = 0

for i in range(n):
    if not li[a[i]]:
        continue
    li[a[i]] = False
    tmp = a[i]
    while tmp < len(li):
        li[tmp] = False
        tmp += a[i]
    if i < n-1:
        if a[i+1] == a[i]:
            continue
    ans += 1


print(ans)