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):
def main():
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()

    ans = 0
    sieve = [False for _ in range(1000001)]
    for i in range(n):
        if sieve[a[i]]:
            continue
        for j in range(a[i], 1000001, a[i]):
            sieve[j] = True
        if i > 0:
            if a[i] == a[i-1]:
                continue
        if i < n-1:
            if a[i] == a[i+1]:
                continue
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

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

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

A.sort()
Sum = 0

d = defaultdict(int)
for key in A:
    d[key] += 1

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1, 10 ** 6):
            if A[i] * j <= 10 ** 6:
                DP[A[i] * j] = 1
            else:
                break

        if d[A[i]] == 1:
            Sum += 1
print(Sum)

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

l = [False]*(A[n-1] + 1)
fix = []
for i in A:
    if l[i]:
        fix.append(i)
    l[i] = True
    
for i in range(A[n-1]+1):
    if l[i]:
        for j in range(i*2, A[n-1]+1, i):
            l[j] = False

for i in fix:
    l[i] = False
    
ans = [i for i in range(A[n-1] + 1) if l[i]]

print(len(ans))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
M = A[-1]+1
DP = [0]*M
for i in A:
  DP[i] += 1
  for j in range(i*2,M,i):
    DP[j] = 2
print(DP.count(1))

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
maxa = max(A)
minx = min(A)
lista = [0]*(max(A)+1)
for i in range(len(A)):
  
  for j in range(0,maxa+1,A[i]):
    lista[j] += 1
    
count = 0
for i in range(len(A)):
  if lista[A[i]] == 1:
    count += 1
print(count)

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

a_max = A[-1]
dp = [True]*(a_max+1)
ans = 0
for i in range(N-1):
    p = A[i]
    if dp[p] == True:
        
        for q in range(a_max//p+1):
            
            dp[p*q] = False
        if A[i] != A[i+1]:
            ans += 1
if dp[A[-1]]:
    ans += 1
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a= list(map(int,input().split()))
if n == 1:
  print(1)
  exit()

a.sort()

c = Counter(a)
a = list(set(a))
dp = [0] * (10**6 +1)

for x in a:
  t = x * 2
  while t <= 10**6:
    dp[t] = 1
    t += x

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

print(ans)

Solution (Python):
import collections
import heapq
import math
import random
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500005)
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
rs = lambda: input().rstrip()

n = ri()
a = rl()
N = 1000000
f = [0] * (N + 10)
for v in a:
    f[v] += 1
for i in range(N, 0, -1):
    if f[i] == 0:
        continue
    j = i * 2
    while j <= N:
        f[j] += f[i]
        j += i
cnt = sum(f[i] == 1 for i in a)
print(cnt)

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

A.sort()
A.append(0)
dp = [True] * (10 ** 6 + 5)
ans = 0
for i in range(N):
    if dp[A[i]-1]:
        if A[i] != A[i + 1]:
            ans += 1
        dp[A[i]-1::A[i]] = [False] * (len(dp) // A[i])

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

INF = 10**18
eps = 10**-7

import itertools

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

A.sort()


check = [[False,False] for i in range(10**6+1)]
ans = 0
for a in A:
    if check[a][1]:
        check[a][0] = True
    if check[a][0]:
        continue
    for j in range(2*a,10**6+1,a):
        check[j][0] = True
    check[a][1] = True
 
for a in A:
    if not check[a][0]:
        ans += 1
print(ans)

Solution (Python):
from collections import Counter

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

c=Counter(a)

def eratosthenes(lim):
  is_p=[1]*lim
  is_p[0]=1
  is_p[1]=1

  for i in set(a):
    if is_p[i]:
      for j in range(i*2,lim,i):
        is_p[j]=0

  return is_p

lim=10**6+5
is_p=eratosthenes(lim)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

Solution (Python):
from collections import Counter

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

c=Counter(a)

def eratosthenes(lim):
  is_p=[1]*lim
  is_p[0]=1
  is_p[1]=1

  for i in set(a):
    if is_p[i]:
      for j in range(i*2,lim,i):
        is_p[j]=0

  return is_p

lim=10**6+5
is_p=eratosthenes(lim)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

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

a = sorted(a)
max_a = max(a)
dp = [1 for i in range(max_a+1)]
a_num = [0 for i in range(max_a+1)]
ans = 0

for i in a:
    a_num[i] += 1
    if a_num[i] == 2:
        tmp = i
        while tmp+i <= max_a:
            tmp += i
            dp[tmp] = 0
        dp[i] = 0

for i in a:
    if dp[i] == 0:
        continue
    else:
        ans += 1
        tmp = i
        while tmp+i <= max_a:
            tmp += i
            dp[tmp] = 0

print(ans)

Solution (Python):




import sys
from io import StringIO
import unittest
import collections

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    c=collections.Counter(arr)
    tb=[False]*(10**6 + 10)
    ans=0
    for x in c.keys():
        for j in range(x*2,10**6+5,x):
            tb[j]=True
    for x in c.keys():
        if tb[x]==0 and c[x]==1:
            ans+=1
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

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

mina = min(A)
maxa = max(A)
AA = [0]*(maxa-mina+1)

for i in range(N):
    maxj = maxa//A[i]
    for j in range(1,maxj+1):
        AA[j*A[i]-mina]+=1

ans = 0

for i in range(N):
    if AA[A[i]-mina] == 1:
        ans += 1
        
print(ans)

Solution (Python):
n = int(input())
a_li = list(map(int,input().split()))
cnt = [0]*(10**6+1)


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


a_li = set(a_li)

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

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

ans = 0
for i in unique:
    if cnt[i] == 0:
        ans += 1
print(ans)

Solution (Python):
from numba import njit


@njit
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()))

    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

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):


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

a.sort()
a_max = max(a)
dp = [True for _ in range(a_max+1)]

ans = 0
for i in range(n):
    if dp[a[i]]:
        for j in range(0, a_max+1, a[i]):
            dp[j] = False
        if i > 0:
            if a[i] == a[i-1]:
                continue
        if i < n-1:
            if a[i] == a[i+1]:
                continue
        ans += 1

print(ans)

Solution (Python):
import numpy as np
from collections import Counter


len_arr = int(input())
arr = list(map(int, input().split(' ')))
counter = Counter(arr)
x_max = max(counter.keys())

dp = np.empty(x_max+1, dtype=np.bool_)
dp[:] = True

ans = 0

for x, count in sorted(counter.items()):
    multi = [x*y for y in range(1, x_max//x+1)]
    if count == 1 and dp[x]:
        ans += 1
    dp[multi] = False

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
ma = max(A)
l = [0 for _ in range(ma + 10)]
for i in range(N):
    temp = A[i]
    while(temp <= ma + 5):
        l[temp] += 1
        temp += A[i]
ans = 0
for i in range(N):
    if l[A[i]] == 1:  ans += 1
print(ans)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
max_a = max(a)
cnt_d = [0] * (max_a + 1)
for ai in a:
    for multi in range(ai, max_a + 1, ai):
        cnt_d[multi] += 1
print(sum(cnt_d[ai] == 1 for ai in a))

Solution (Python):
n = int(input())
a = sorted(list(map(int,input().split())))
am = a[-1]+1
div = [1]*am
ans = 0

for i in range(n-1):
  a_i = a[i]
  if div[a_i]:
    for j in range(a_i,am,a_i):
      div[j] = 0
    if a_i < a[i+1]:
      ans += 1
      
if div[-1]:ans += 1
print(ans)

Solution (Python):
n = int(input())
a = sorted([int(_) for _ in input().split(' ')])
a.append(0)

d = set()
answer = 0

for i in range(n):
    if not(a[i] in d):
        if a[i] != a[i + 1]:
            answer += 1
        for j in range(a[i], 1000001, a[i]):
            d.add(j)

print(answer)

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

nums = list(set(arr))
nums.sort()
last = nums[-1]
from collections import Counter
arr = Counter(arr)
ans = 0

for i in nums:
    if arr[i] == 1:
        ans += 1
    for j in range(last//i+1):
        del arr[i*j]

print(ans)

Solution (Python):


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

A.sort()
A_max = A[-1]
table = [0] * (A_max + 1)

for x in A:
    table[x] += 1
    for y in range(x * 2, A_max + 1, x):
        table[y] += 1

result = sum([1 for x in A if table[x] == 1])
print(result)

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

M=1000050

dp=[0 for i in range(M)]

ans=0
for x in A:
    if dp[x]!=0:
        dp[x]=2
        continue
    for i in range(x,M,x):
        dp[i]+=1

for x in A:
    if dp[x]==1:
        ans+=1

print(ans)

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

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



from collections import Counter
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
 
    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return ret
  
n=int(readline())
a=list(map(int,readline().split()))  
A=set(a)
ans=0
c=Counter(a)
for i in a:
  if c[i]>=2:
    continue
  chk=set(divisors(i))
  if chk&A=={i}:
    ans+=1
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
 
    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return ret
  
a = int(readline())
n = list(map(int,readline().split()))
c = Counter(n)
ss = set(n)

ans = 0
for m in ss:
  if c[m] >= 2:
    continue
  chk = set(divisors(m))
  if chk & ss == {m}:
      ans += 1
print(ans)

Solution (Python):
mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    n = int(raw_input())
    
    arr = map(int,raw_input().split())
    
    ans = 0
    
    max_ele = max(arr)
    
    arr.sort()
    
    marked = [False] * (max_ele+5)
    
    for i in range(n):
        diff_prev = i-1 < 0 or arr[i] != arr[i-1]
        diff_next = i+1 >= n or arr[i] != arr[i+1]
        num = arr[i]
        if not marked[num]:
            cur = num 
            if diff_next and diff_prev:
                ans += 1
            while cur <= max_ele:
                marked[cur] = True
                cur += num
    
    print(ans)
    

main()

Solution (Python):
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N=II()
A=LI()
cnt=[0]*((10**6)+1)
for elem in A:
  cnt[elem]+=1
unique=[]
for i in range((10**6)+1):
  if cnt[i]==1:
    unique.append(i)
cnt=[0]*((10**6)+1)
A=list(set(A))
for elem in A:
  for m in range(elem*2,10**6+1,elem):
    cnt[m]=1
ans=0
for i in unique:
  if cnt[i]==0:
    ans+=1
print(ans)

Solution (Python):
import numpy as np
from collections import Counter
from math import sqrt
from time import time


def main():
    N = int(input())
    np_a_o = list([int(x) for x in input().split()])
    np_a = Counter(np_a_o)

    np_a_keys = set(np_a.keys())

    div_list = set()
    key_max = max(np_a_keys)

    c = 0

    for key in np_a_keys:
        for div in range(key*2, key_max+1, key):
            div_list.add(div)

    r = np_a_keys - div_list

    u, count = np.unique(np.array(np_a_o), return_counts=True)
    r -= set(u[count > 1])

    print(len(r))


if __name__ == '__main__':
    main()

Solution (Python):



from math import *
from copy import *					
from heapq import *					
from string import *				
from random import *				
from bisect import *				
from sys import stdin				
from sys import maxsize				
from operator import *				
from itertools import *				
from decimal import Decimal 		
from collections import Counter		
from collections import defaultdict 

'''
5
24 11 8 3 16
'''

def solve(l):
	n = len(l)
	ans,maxx = 0,max(l)
	done = [0]*(maxx+1)
	l.sort()
	ans = 0
	d = dict(Counter(l))
	for i in l:
		zz = 2
		while(i*zz <= maxx):
			done[i*zz] = 1
			zz += 1
	for i in l:
		if(not done[i] and d[i] == 1):
			ans += 1
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

Solution (Python):
def II(): return int(input())
def LI(): return list(map(int, input().split()))

N=II()
A=LI()
cnt=[0]*((10**6)+1)
for a in A:
  cnt[a]+=1
  
unique=[]
for i in range((10**6)+1):
  if cnt[i]==1:
    unique.append(i)
    
ans=0
cnt=[0]*((10**6)+1)
A=list(set(A))
for elem in A:
  for i in range(elem*2,(10**6)+1,elem):
    cnt[i]=1
for i in unique:
  if cnt[i]==0:
    ans+=1
print(ans)

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

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

for x in a:
    if b[x] == 0:
        for y in list(range(2 * x, N, x)):
            b[y] += 1
    b[x] += 1

ans = 0
for x in a:
    if b[x] == 1:
        ans += 1
print(ans)

Solution (Python):
def solve(A):
    n = A[-1]
    is_nodiv = [True] * (n+1)

    pre = 0
    for a in A:
        if pre == a or not is_nodiv[a]:
            is_nodiv[a] = False
            continue

        for j in range(2*a, n+1, a):
            is_nodiv[j] = False
        
        pre = a

    return sum([is_nodiv[a] for a in A])



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = solve(A)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def solve(A):
    n = A[-1]
    is_nodiv = [True for _ in range(n+1)]

    pre = 0
    for a in A:
        if pre == a or not is_nodiv[a]:
            is_nodiv[a] = False
            continue

        for j in range(2*a, n+1, a):
            is_nodiv[j] = False
        
        pre = a
        
    return sum([is_nodiv[a] for a in A])



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = solve(A)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from numba import njit

N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
dp = [0] * maxA

for i in range(N):
    if dp[A[i]-1] != 0:
        dp[A[i]-1] = 2
        continue
    else:
        for j in range(1, maxA//A[i]+1):
            dp[A[i]*j-1] += 1

ans = 0
for i in range(N):
    if dp[A[i]-1] == 1:
        ans += 1

print(ans)

Solution (Python):
from bisect import bisect
from collections import Counter
n=int(input())
b=sorted(list(map(int,input().split())))
a=Counter(b)
mA=b[-1]
acc=0
dp=[True]*(mA+1)
for i,v in a.items():
  if dp[i]==True and v==1:
    acc+=1
  else:dp[i]=False
  for k in range(mA//i+1):
    dp[k*i]=False
print(acc)

Solution (Python):

n=int(input())
m=list(map(int,input().split()))
k=10**6+1
p=[0]*k
m.sort()
for i in range(1,n):
    if m[i]==m[i-1]:
        p[m[i]]=1
res=0
for i in range(n):
    if p[m[i]]==0:
        res+=1
    
    if i!=n-1 and m[i]!=m[i+1]:
        for j in range(m[i]*2,k,m[i]):
            p[j]=1
print(res)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
amax = max(a)
ans = 0
numlist = [0] * amax

for i in range(n):
    if numlist[a[i]-1] != 0:
        numlist[a[i]-1] = 2
        continue
    else:
        for j in range(1, amax // a[i] + 1):
            numlist[a[i] * j - 1] += 1
for i in range(n):
    if numlist[a[i]-1] == 1:
        ans += 1
        
print(ans)

Solution (Python):
from collections import Counter
N = int(input())
anslist = set([])
A = list(map(int, input().split()))
Amax = max(A)
for i in A:
    j = i*2
    while j <= Amax:
        anslist.add(j)
        j += i

anslist = list(anslist)
anslist.extend(A)
anslist = Counter(anslist)

A = Counter(A)
cnt=0
for  k,v in A.items():
    if v!=1:
        del anslist[k]
    else:
        cnt+=1

ans = Counter(anslist.values())
print(cnt-ans[2])

Solution (Python):
import collections 
n,cc = int(raw_input()), collections.Counter(map(int,raw_input().split()))
m,s = max(cc.keys()),{ai:True for ai in cc}
for a in cc:
	c = a if cc[a] > 1 else 2 * a
	while(c <= m):
		if a in s: s[c] = False
		c += a
count = 0
for v in s.values():
	if v: count +=1
print count

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
from collections import Counter
AA = Counter(A)
dp = [True]*(A[-1]+1)
ans = 0
for k,v in AA.items():
    if dp[k]==True and v == 1:
        ans += 1
    for i in range(A[-1]//k+1):
        dp[k*i] = False
print(ans)

Solution (Python):
import collections 
n,cc = int(raw_input()), collections.Counter(map(int,raw_input().split()))
m,s = max(cc.keys()),{ai:True for ai in cc}
for a in cc:
	c = a if cc[a] > 1 else 2 * a
	while(c <= m):
		if a in s: s[c] = False
		c += a
count = 0
for a in s:
	if s[a]: count +=1
print count

Solution (Python):
import numpy as np
n=int(input())
a=sorted(list(map(int,input().split())))

dp=np.array([0 for _ in range(max(a)+1)])
for i in range(n):
    ai=a[i]
    if(dp[ai]>=2):
        continue

    j=1
    while(ai*j<=a[-1]):
        dp[ai*j]+=1
        j+=1

print(sum(dp[ai]==1 for ai in a))

Solution (Python):
import collections
n = int(raw_input())
ais = map(int,raw_input().split())
cc = collections.Counter(ais)
s = {ai:True for ai in ais}
m = max(ais)
for a in cc:
	c = a if cc[a] > 1 else 2 * a
	while(c <= m):
		if a in s: s[c] = False
		c+= a
count = 0
for ai in s:
	if s[ai]:
		count +=1

print count

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

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

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

Solution (Python):

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)

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

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

A = set(A)
MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if (X[a] == 1) and (C[a] == 1)])
print(ans)

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

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

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

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

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

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

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

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

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

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