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

Solution (Python):
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq

import bisect
import sys

sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    
    check=[False for _ in range(n)]
    check[s]=True
    
    queue=deque([s])
    visited_num=1

    
    
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        
        if len(queue)==0:
            
            
            return color

        now_vertex=queue.popleft()
        
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color




ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



n=int(input())
a=list(map(int,input().split()))
a.sort()
s=10**6
s+=100
sosu_flag=[True for i in range(s)]


ans=0
cal=[]
for i in a:
    if not sosu_flag[i]:
        continue
    ans+=1
    cal.append(i)
    for j in range(i,s,i):
        sosu_flag[j]=False

c=Counter(a)
for key in cal:
    if c[key]>1:
        ans-=1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
L = [0] * (10 ** 6 + 1)
S = set()

for a in A:
    if L[a]:
        continue
    if a in S:
        L[a] = 1
    S.add(a)
    for i in range(2, 10 ** 6 + 1):
        if a * i > 10 ** 6:
            break
        L[a * i] = 1

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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split())) 
A.sort()
mx = A[-1]
E = [False]*(mx + 3)
ans = 0
A += [float("inf")]*2
for i in range(N):
    a = A[i]
    if not(E[a]) and A[i+ 1] != A[i]:
        ans += 1
    for j in range(1,(mx // a )+ 1):
        E[a*j] = True

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            yakusu.append(i)
            if n // i != i:
                yakusu.append(n//i)
    return yakusu
     
baisu = [False] * (10**6 + 1)
def main():
    N = I()
    A = LI()

    ok = 0
    for a in set(A):
        if baisu[a]:
            continue
        if not baisu[a]:
            num = a + a
            while num < 10**6+1:
                baisu[num] = True
                num += a
    s = collections.Counter(A)
    for a in A:
        if not baisu[a]:
            if s[a] > 1:
                continue
            ok += 1
    print(ok)
main()

Solution (Python):
from time import time


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    now = time()

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

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

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        if time() - now >= 1.8:
            print(n)
            exit()

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import collections
N = int(input())
cA = collections.Counter([int(_) for _ in input().split()])
cand = set(range(1, 1000001))
ans = 0
for a in sorted(cA.keys()):
    if a in cand:
        if cA[a] == 1:
            ans += 1
        for c in range(a, 1000001, a):
            if c in cand:
                cand.remove(c)
print(ans)

Solution (Python):
MAXA = 10**6+1
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.append(0)
hurui = [0]*(MAXA)
ans = 0
for i in range(N):
    a = A[i]
    if hurui[a] == 0:
        if A[i] != A[i+1]:
            ans += 1
    else:
        continue
    for j in range(a,MAXA,a):
        hurui[j] = 1
print(ans)

Solution (Python):
"""
~~ Author : Bhaskar
~~ Dated : 07~06~2020
"""

import sys
from bisect import *
from math import floor,sqrt,ceil,factorial as F,gcd,pi,log
from itertools import chain,combinations,permutations,accumulate
from collections import Counter,defaultdict,OrderedDict,deque
from array import array
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
mod = 1000000007
ch = "abcdefghijklmnopqrstuvwxyz"
lcm = lambda a,b : (a*b)//gcd(a,b)
setbit = lambda x : bin(x)[2:].count("1")

def solve():
    nn = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    tra = Counter(a)
    s = dict()
    n = len(a)
    max_ele = INT_MIN
    for i in range(n):
        s[a[i]] = 1
        max_ele = max(max_ele,a[i])

    res = dict()
    for i in range(n):
        if a[i] !=0 :
            for j in range(a[i]*2,max_ele+1,a[i]):
                if j in s.keys():
                    res[j]  = 1
    
    c =0
    for k,v in tra.items():
        if k not in res:
            if v == 1:
                c += 1


    print( c)

if __name__ == "__main__":
    
    
    
    
    solve()

Solution (Python):
import sys
from collections import deque
import copy
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    MAX = (10 ** 6) + 5
    prime = [True] * MAX
    ans = 0
    for i in range(1, N):
        if A[i] == A[i - 1] and prime[A[i]]:
            prime[A[i]] = False
            for j in range(A[i] * 2, MAX, A[i]):
                prime[j] = False
    for i in range(N):
        now = A[i]
        if prime[now]:
            ans += 1
            for j in range(now * 2, MAX, now):
                prime[j] = False
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
a.sort()
m=max(a)
x=[1 for i in range(m+1)]
for p in a:
    if m//p:
        for k in range(2,m//p+1):
            x[p*k]=-1

ans=0
dic=defaultdict(int)
for i in a:
    dic[i]+=1

for p in a:
    if x[p]==1 and dic[p]==1: ans+=1
print(ans)

Solution (Python):
n=int(input())
from collections import Counter as co
l=co(list(map(int,input().split())))
ans=len(l)
ng=set()
for k in l:
    if l[k]>=2:ng.add(k)
    for i in range(2*k,10**6+1,k):

        if i in l:
            ng.add(i)
            
            

print(ans-len(ng))

Solution (Python):
import sys
from collections import defaultdict

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    A.sort()
    L = max(A)
    ad = defaultdict(int)
    for a in A: ad[a] += 1

    ans = 0
    B = [True] * (L + 1)
    for a in A:
        if B[a]:
            if ad[a] == 1: ans += 1
        k = 2 * a
        while k <= L:
            B[k] = False
            k += a

    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
from sys import stdin
from collections import Counter
def main():
    
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))
    a.sort()

    a_max=max(a)+1
    table=[False]*a_max
    cnt=0
    s=set()
    t=set()
    for i in range(n):
        a_i=a[i]
        if table[a_i]==False:
            s.add(a_i)
            if table[a_i]==False:
                cnt+=1
            for x in range(a_i,a_max,a_i):
                table[x]=True
        else:
            if a_i in t:
                pass
            elif a_i in s:
                cnt-=1
                t.add(a_i)

    print(cnt)

if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
r = [0 for _ in range(max(a)+1)]
l = [0 for _ in range(max(a)+1)]
ans = n
for i in a:
    r[i] += 1
    l[i] = 1
for i in range(len(r)):
    if r[i]:
        if 1 < r[i]:
            l[i] = 0
        for j in range(2*i,len(r),i):
            if r[j]:
                l[j] = 0
print(sum(l))

Solution (Python):
from collections import Counter

n=int(input())
A=Counter(sorted(list(map(int,input().split()))))
number=[True for i in range(10**6+1)]

cnt=0
for v,m in A.items():
    if m!=1:
        for i in range(v,10**6+1,v):
            number[i]=False
    else:
        if number[v]==True:
            cnt +=1
            for i in range(v,10**6+1,v):
                number[i]=False
print(cnt)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
mx = a[-1]
c = [0 for _ in range(mx+1)]
ans = 0
if a[0] == 1:
  if n == 1:
    print(1)
    exit()
  if a[1] == 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
i = 0
while i < n:
  if c[a[i]] == 0:
    p = a[i]
    for _ in range(2,mx//a[i]+1):
      p += a[i]
      c[p] = 1
    flag = True
    while i+1 < n and a[i+1] == a[i]:
      i += 1
      flag = False
    if flag:
      ans += 1
  i += 1
print(ans)

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    check = Counter(a).items()
    memo = [True] * (2 * 10 ** 6 + 1)
    a = []
    for k, v in check:
        if v == 1:
            a.append(k)
        else:
            memo[k] = False
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * k:
                    break
                memo[i * k] = False
    ans = 0
    a.sort()
    for aa in a:
        if memo[aa]:
            ans += 1
            for i in range(1, 10 ** 6 + 1):
                if 10 ** 6 + 1 < i * aa:
                    break
                memo[i * aa] = False
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

from decimal import *
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
b = set(a)

NN = 10 ** 6 + 100
primes = set([])
isprime = [False for _ in range(NN + 1)]
cnt = [True for _ in range(NN + 1)]
for i in a:
    if cnt[i]:
        isprime[i] = True
        cnt[i] = False
    else:
        isprime[i] = False
for i in range(1, NN + 1):
    if not cnt[i]:
        for j in range(i * 2, NN + 1, i):
            isprime[j] = False
    if isprime[i]:
        primes.add(i)
ans = 0
for i in b:
    if isprime[i]:
        ans += 1
print(ans)

Solution (Python):
import sys
from collections import Counter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = _i()
    a = Counter(_ia())
    k = sorted(a.keys())
    m = max(k) + 1
    c = [False for i in range(m)]
    cnt = 0
    for ki in k:
        if c[ki]:
            continue
        if a[ki] == 1:
            cnt += 1
        for j in range(ki+ki, m, ki):
            c[j] = True

    return cnt


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

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
if N==1:
  print(1)
else:
  A.sort()
  import numpy as np

  l = np.array([0] * (10**6 + 10))
  m = np.array([0] * (10**6 + 10))
  for i in range(N):
    l[A[i]] += 1
    m[A[i]] += 1

  ans = 0
  length = len(l)
  for i in range(length):
    if l[i]==1:
      ans += 1
    
    if m[i]>=1:
      l[i::i] = 0

  print(ans)

Solution (Python):
from __future__ import print_function
import sys


if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    count = 0
    for i in range(n):
        for div in divisors[a[i]]:
            if (div in hm and (div!=a[i] or hm[a[i]]>1)) or ((a[i] // div in hm) and (div!=1 or hm[a[i]]>1)):
                count -= 1
                break
        count += 1
    print(count)
    return


def get_divisors():
    divisors = [[] for _ in range(mxa+1)]
    for i in range(1, 10**3+1):
        for j in range(i, mxa+1, i):
            divisors[j].append(i)
    return divisors


n = RN()
a = RA()
mxa = max(a)
hm = {}
for ai in a:
    if not ai in hm:
        hm[ai] = 0
    hm[ai] += 1
divisors = get_divisors()
solve()

Solution (Python):
from collections import Counter

n = int(input())
*arr, = map(int, input().split())
arr.sort()
mx = max(arr)
is_enabled = [1] * (mx + 1)

counter = Counter(arr)
for val, cnt in counter.items():
    if cnt > 1:
        is_enabled[val] = 0

for i, v in enumerate(arr):
    if i == 0 or arr[i - 1] != v:
        x = v * 2
        while x <= mx:
            is_enabled[x] = 0
            x += v

cnt = 0
for v in arr:
    if is_enabled[v]:
        cnt += 1
print(cnt)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(0)
b = {}
c = 0
for i in range(n):
    if a[i] not in b:
        for j in range(1, 10**6//a[i]+1):
            b[a[i]*j] = 1
        if a[i] != a[i+1]:
            c += 1
print(c)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
used = [False] * (10 ** 6 + 1)
A.sort()
ans = 0
for j in range(n):
    a = A[j]
    if used[a]:
        continue
    ans += 1
    if j < n - 1:
        aa = A[j + 1]
        if aa == a:
            ans -= 1
    for i in range(1, 10 ** 6 // a + 1):
        used[a * i] = True
print(ans)

Solution (Python):
from collections import Counter

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

B = Counter(A)
C = list(B.keys())
C.sort()

table = [1] * (M + 1)
cnt = 0
for c in C:
    if B[c] == 1:
        if table[c] == 1:
            cnt += 1
    for i in range(M):
        if c * i > M:
            break
        else:
            table[c * i] = 0

print(cnt)

Solution (Python):
N = int(input())
A = sorted(map(int, input().split()))
if A[0] == 1:
    if N > 1 and A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = 0
    MAX = 10 ** 6 + 3
    C = [False] * MAX
    for i in range(N):
        if not C[A[i]]:
            if i != N - 1 and A[i] != A[i + 1]:
                ans += 1
            elif i == N - 1:
                ans += 1
            cur = 1
            while cur * A[i] <= MAX:
                C[cur * A[i]] = True
                cur += 1
    print(ans)

Solution (Python):
import sys
from collections import Counter

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

def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    MAX_A = max(A)
    A_COUNT = Counter(A)

    if min(A) == 1:
        if A_COUNT[1] == 1:
            print(1)
        else:
            print(0)
        exit()

    ans = 0
    prime = [False] * 2 + [True] * (MAX_A - 1)
    for a in A:
        if prime[a]:
            if A_COUNT[a] == 1:
                ans += 1
            for j in range(a, MAX_A + 1, a):
                prime[j] = False
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline


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

MAX = 10**6+1

used = [False]*MAX


res = 0

for i in range(n):
    if used[a[i]]:
        continue
    if i+1 == n or a[i+1] != a[i]:
        res += 1
    for j in range(a[i],MAX,a[i]):
        used[j] = True

print(res)

Solution (Python):
N = int(input())
Ali = list(map(int,input().split()))
Alis = set()
Blis = set()

Ali.sort()

for i in range(N):
  if Ali[i] in Alis:
    Blis.add(Ali[i])
    continue
  Alis.add(Ali[i])

Alis -= Blis

for i in range(N):
  Alis.difference_update(range(Ali[i]*2, Ali[-1]+1, Ali[i]))
  
print(len(Alis))

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

A.sort()
numbers = range(M)
not_divisible = [True] * (M)

result = 0
for i in range(N):
    target = A[i]
    if not_divisible[target]:
        if i+1 <= N-1 and A[i+1] == A[i]:
            pass
        else:
            result += 1
        for j in range(target, M, target):
            not_divisible[j] = False
print(result)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
ca=dict(Counter(a))
ablans=set([k for k,v in ca.items() if v==1])
notans=set([k for k,v in ca.items() if v>1])
if len(a)==0:
  print(0)
  exit()
a.sort()
maxa=a[-1]
for ai in a:
  i=2
  while maxa>=i*ai:
    ablans.discard(i*ai)
    i+=1
print(len(ablans))

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

cands = [False for i in range(0, 1000000 + 1)]
dir_cands = [False for i in range(0, 1000000 + 1)]
for a in A:
    if dir_cands[a]:
        cands[a] = True
    dir_cands[a] = True

    if cands[a]:
        continue

    x = 2 * a
    while x <= 1000000:
        cands[x] = True
        x += a

res = 0
for a in A:
    if not cands[a]:
        res += 1

print(res)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
"""
すべてのjで割れない場合、カウントする。
逆に言えば、一つでもiをjで割れるようなjが存在するならば、それはカウントしない。
一番小さい数が2つあればそれはカウントしないが、基本的に一番小さい数はほかのどの数字でも割れない
Aiの制約が10**6であることから、小さい数から数えていって、10**6までの倍数の場所にマークを付ける。
初めて出てくるような数字に関して、カウントを1足してやる。
一番小さい数のコーナーケースに注意
"""
n = int(readline())
lst1 = list(map(int,readline().split()))

lst1.sort()

memo = [0]*(10**6+1)
if n == 1:
    print(1)
    exit()

ans = 0
for i in range(n):
    if memo[lst1[i]] == 0:
        if i < n-1:
            if lst1[i] != lst1[i+1]:
                ans += 1
        elif i == n-1:
            ans += 1
        j = 1
        while lst1[i]*j <= 10**6:
            memo[lst1[i]*j] = 1
            j += 1

print(ans)

Solution (Python):
n = int(input())
dat = list(map(int, input().split()))

import collections
buf = collections.Counter(dat)
dat = []
dat = list(buf.keys())

dat.sort()

res = 0

used = [False] * (1000100)

for i in range(len(dat)):
    ok = True

    if used[dat[i]]:
        ok = False
    if buf[dat[i]] != 1:
        ok = False

    c = 0
    v = -1
    while True:
        c += 1
        v = dat[i] * c
        if v > 1000010:
            break
        used[v] = True

    used[dat[i]] = True

    if ok:
        res += 1

print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]





N = ii()
A = sorted(li())

max_a = A[-1]

flag = [0] * (A[-1]+1)
cnt = 0

for i, num in enumerate(A):
    
    if i == N-1 and not flag[num]:
        cnt += 1
    elif not flag[num] and A[i+1]!=num:
        cnt += 1
    x = num
    while True:
        flag[x] = 1
        x += num
        if x > max_a:
            break

print(cnt)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
ctr = Counter(A)
B = [k for k,v in ctr.items() if v == 1]
B.sort()
D = {b:i for i,b in enumerate(B)}

ok = [1] * len(B)
MX = 10**6+1
for k in ctr.keys():
    for n in range(2*k,MX,k):
        if n in D:
            ok[D[n]] = 0
print(sum(ok))

Solution (Python):
def main():
    N = int(input())
    A_list = sorted(list(map(int, input().split())))
    max_a = A_list[-1]

    res = 0
    multi_set = set([])
    for i,a in enumerate(A_list):
        if a not in multi_set:    
            for j in range(1,max_a//a + 1):
                multi_set.add(a*j)
            
            if i == N-1:
                res += 1
            elif A_list[i+1] != a:
                res += 1
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):
n,*a=map(int,open(0).read().split())
a.sort()
b=[0]*(10**6+1)
for i in a:
    b[i]+=1
    if b[i]==1:
        for j in range(2*i,10**6+1,i):
            b[j]+=100
print(b.count(1))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

n = int(input())
a = list(map(int,input().split()))
ma = max(a)
lis = [i for i in range(1,ma+1)]
a.sort()
f = [-1 for i in range(ma+1)]
ans = 0

for i in a:
    if f[i]==-1:
        ans +=1
        f[i]=2
        for j in range(i+i,ma+1,i):
            f[j] = 1
    elif f[i]==2:
        ans-=1
        f[i] = 1
    else:
        continue

print(ans)

Solution (Python):
MAX = 10**6
N = int(input())
A = list(map(int, input().split()))
B = [0] * (MAX+1)
for i in range(N):
  B[A[i]] += 1
L = [0] * (MAX+1)
for k in range(MAX+1):
  if(B[k] >= 1 and L[k] == 0):
    tmp = 2*k
    while(tmp <= MAX):
      L[tmp] = 1
      tmp += k

ans = 0
for i in range(N):
  if(B[A[i]] == 1 and L[A[i]] == 0):
    ans += 1
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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 zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7



N = INT()
A = LIST()
A.sort()

A_max = max(A)

a = [0]*(A_max+1)

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

for i in range(A_max+1):
	if a[i] == 1:
		ans += 1
	if 0 < a[i]:
		for j in range(A_max//i + 1):
			a[i*j] = 0

print(ans)

Solution (Python):

from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline


def array(size,init=0):
    return [[init for j in range(size[1])] for i in range(size[0])]



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


def II():
    return int(input())


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact


def permutate(x,A):
    n=len(x)
    res=[-1]*n
    for i in range(n):

        res[i]=x[A[i]]
    return res


def generate_bin(digit):
    for b in range(2**digit):
        b=bin(b)
        tmp=b[2:].zfill(digit)
        yield list(map(int,tmp))
        
        
        

def search(x, count):
    
            

    for d in directions:
        nx = d+x
        
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N=int(input())
A=acinput()


M=max(A)
m=[0]*(M+1)
for i in range(N):
    
    x=A[i]
    m[x]+=1
    
    k=2
    while True:
        if x*k<=M:
            m[x*k]+=1
        
            k+=1
        else:
            break


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

        
print(res)

Solution (Python):

def Sieve(n): 

    ret = []
    divlis = [-1] * (n+1) 
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis

N = int(input())

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

ans = 0
lis = [0] * (10**6+1)
tmp,dl = Sieve(10**6+2)

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        lis[A[i]] = 1
        continue

    dic = {}
    now = A[i]
    while dl[A[i]] != -1:

        if dl[A[i]] not in dic:
            dic[dl[A[i]]] = 1
        else:
            dic[dl[A[i]]] += 1
        A[i] //= dl[A[i]]

    if A[i] != 1:
        if A[i] not in dic:
            dic[A[i]] = 1
        else:
            dic[A[i]] += 1

    l1 = [1]
    
    for i in dic:
        l2 = [i**j for j in range(dic[i]+1)]

        tmp = len(l1)
        for x in range(tmp):
            for y in l2:
                if y != 1:
                    l1.append(l1[x]*y)

    flag = True
    
    for i in l1:
        if lis[i] > 0:
            flag = False
            break

    if flag:
        ans += 1
    lis[now] = 1

print (ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

M = A[N-1]
K = [False]*(M+1)
ans = 0
for i in range(N-1):
    a = A[i]
    if K[a]:
        continue
    if A[i+1] != a:
        ans += 1
    for i in range(a, M+1, a):
        K[i] = True
if not K[ A[N-1] ]:
    ans += 1
print(ans)

Solution (Python):

from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
a.sort()
b = [True]*(a[n-1]+1)
ans = 0
for i in range(n):
    x = a[i]
    if not b[x]:
        continue
    if not (i<n-1 and a[i+1]==a[i]):
        ans += 1
    for j in range(x,a[n-1]+1,x):
        b[j] = False
print(ans)

Solution (Python):
import sys, math




from collections import defaultdict as dd, deque, Counter

def data(): return sys.stdin.buffer.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')

INF = float('inf')
mod = 998244353


n=int(data())
A=mdata()
d=dd(int)
for i in range(n):
    d[A[i]]+=1
cnt=0
m=max(A)
P=[0]*(m+1)
for i in range(1,m+1):
    if d[i]>0:
        if P[i]==0:
            for j in range(2*i,m+1,i):
                P[j]=1
            if d[i]==1:
                cnt+=1
out(cnt)

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
A.sort()
B=[1]*(10**6+1)
counter=0

if N==1:
  print(1)
  exit()
  
if N==2:
  if A[0]==A[1]:
    print(0)
  elif A[1]%A[0]==0:
    print(1)
  else:
    print(2)
  exit()
  
for i in range(N):
  if 0<i<N-1 and (A[i]==A[i-1] or A[i]==A[i+1]):
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  elif i==0 and A[i]==A[i+1]:
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  elif i==N-1 and A[i-1]==A[i]:
    if B[A[i]]!=0:
      B[A[i]]=0
      j=2
      while A[i]*j<=10**6:
        B[A[i]*j]=0
        j+=1
    continue
  
  if B[A[i]]==1:
    counter+=1
    j=2
    while A[i]*j<=10**6:
      B[A[i]*j]=0
      j+=1
print(counter)

Solution (Python):
X=10**6+1
E=[1 for i in range(X)]
E[0]=0
N=int(input())
A=list(map(int,input().split()))

import copy
B=copy.deepcopy(A)
B.sort()

D={}
for i in range(N):
    if A[i] not in D:
        D[A[i]]=1
    else:
        D[A[i]]=2
ANS=0
for i in range(N):
    if D[B[i]]==2 and E[B[i]]==1:
        for j in range(1,10**7):
            if B[i]*j>=len(E):
                break
            else:
                E[B[i]*j]=0
    elif D[B[i]]==2 and E[B[i]]==0:
        continue
    else:
        if E[B[i]]!=0:
            ANS+=1
            for j in range(1,10**7):
                if B[i]*j>=len(E):
                    break
                else:
                    E[B[i]*j]=0
print(ANS)

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

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

ans = 0
for i in range(1, a[-1] + 1):
    if cnt[i] > 0:
        if cnt[i] == 1:
            ans += 1
        for j in range(2, a[-1] + 1):
            na = i * j
            if na <= a[-1]:
                cnt[na] = 0
            else:
                break

print(ans)

Solution (Python):


LI = lambda: list(map(int, input().split()))


N = int(input())
A = LI()

MAX = 10 ** 6


def main():
    A.sort()
    s = set()
    ans = N
    for i in range(N):
        a = A[i]
        if a in s:
            ans -= 1
            continue
        if i < N - 1 and A[i + 1] == a:
            ans -= 1
        n = MAX // a
        for i in range(1, n + 1):
            s.add(a * i)
    print(ans)


if __name__ == "__main__":
    main()

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

A.sort()
from collections import Counter
L = dict(Counter(A))

Xs = list(L.keys())
NX = len(Xs)

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

if NX!=1:
    cnt = 0
    for X in Xs:
        if B[X]>0:
            continue
        else:
            if L[X]==1:
                cnt += L[X]
            check = X
            t = 2
            while check*t<10**6+1:
                B[check*t]=1
                t+=1
    print(cnt)
else:
    if N==1:
        print(1)
    else:
        print(0)