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):
import math
n = int(input())
ai = [int(i) for i in input().split()]

ai.sort()

sqr_max_val = int(ai[n-1]**0.5)
max_val = ai[n-1]

ai_ex = [0]*(2*10**6)


for i in range(n):
    ai_ex[ai[i]-1] += 1

for i in range(n):
    if ai_ex[ai[i]-1] > 1:
        ai_ex[ai[i]-1] = 0
    """
    if ai[i] > sqr_max_val:
        break
    """
    tmp = ai[i]
    baisu = 2
    
    while tmp * baisu <=  max_val:
        ai_ex[tmp*baisu-1] = 0
        
        baisu += 1
"""
for i in range(100):
    if ai_ex[i] == 1:
        a = 1
        
"""
print(sum(ai_ex))

Solution (Python):
N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max
ans =0
for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        ans += 1
        for j in range(a*2-1,a_Max,a):
            B[j] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
        ans -= 1
print(ans)

Solution (Python):
import math
from collections import deque
from collections import defaultdict
import itertools as it


def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
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 -1*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 bitArr(n):
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): 
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	
	return ans

n = readInt()
a = readInts()
a.sort()

max_a = 10**6
ans = [0]*(max_a+1)

for i in a:
	ans[i]+=complex(1,1)
for i in set(a):
	if ans[i].imag>0:
		for j in range(i*2,len(ans),i):
			ans[j]+=2

count = 0
for i in ans:
	if i.imag>0 and i.real==1:
		count+=1

print(count)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
 
dp = [0]*(10**6)
count = [0]*(10**6)

for i in a:
  count[i-1] += 1
 
b = list(set(a))
for i in b:
  for j in range(i*2, 10**6+1, i):
    dp[j-1] = 1
    
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

Solution (Python):
n = int(input())
A = sorted(map(int, input().split()))
U = A[-1]

line = [1]*(U+1)
ans = set()
depricated = set()
for a in A:
    if a in ans:
        depricated.add(a)
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Solution (Python):
N=input()
A=list(map(int,input().split()))
M=max(A)+1
B=[True]*M
S=set()
x=0
for i in A:
  if i not in S:
    S.add(i)
    for j in range(i*2,M,i):
      B[j]=False
  else:
    B[i]=False
for i in A:
  if B[i]==True:
    x+=1
print(x)

Solution (Python):
N=input()
A=list(map(int,input().split()))
M=max(A)+1
B=[True]*M
S=set()
x=0
for i in A:
  if i not in S:
    S.add(i)
    for j in range(i*2,M,i):
      B[j]=False
  else:
    B[i]=False
for i in A:
  if B[i]==True:
    x+=1
print(x)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))
A.sort()
t=0
e=[True]*1000001
for i in range(n-1):
    a=A[i]
    if e[a]==False:
        continue
    b=a*2
    while b < 1000001:
        e[b]=False
        b+=a
    if A[i+1]==a:
        e[a]=False
for a in A:
    if e[a]:
        t+=1
print(t)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
AM=max(A)+1
B=[0]*AM
x=0
for i in A:
  for j in range(i,AM,i):
    B[j]+=1
for i in A:
  if B[i]==1:
    x+=1
print(x)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
AM=max(A)+1
B=[0]*AM
x=0
for i in A:
  for j in range(i,AM,i):
    B[j]+=1
for i in A:
  if B[i]==1:
    x+=1
print(x)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
memo = [0 for i in range(10**6 + 5)]
memo[0] = 2

for i in a:
    if memo[i] == 2:
        continue
    for j in range(0,len(memo),i):
        memo[j]+= 1

ans = 0
for i,v in enumerate(a):

    if memo[v] == 1:
        ans+=1

print(ans)

Solution (Python):



from collections import Counter

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    r = 0
    for a in A:
        if B[a] == 0:
            continue
        if B[a] == 1:
            r += 1
        for i in range(2, A[-1] // a + 1):
            B[a * i] = 0
    print(r)
    return

main()

Solution (Python):
import sys

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

if len(A) == 1:
    print(1)
    sys.exit(0)

box = [False] * (A[-1] + 1)
for a in A:
    box[a] = True

for idx, a in enumerate(A):
    if A[idx] == A[idx - 1]:
        box[a] = False
    for j in range(2, A[-1]//a + 1):
        box[a * j] = False

count = 0
for d in box:
    if d:
        count += 1
print(count)

Solution (Python):



from collections import Counter

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            B[a * i] = 0
    print(sum(B.values()))
    return

main()

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

dp = [False] * (A[-1] + 1)
for a in A:
    dp[a] = True

for idx, a in enumerate(A):
    if A[idx] == A[idx - 1]:
        if idx == 0:
            None
        else:
            dp[a] = False
    for j in range(2, A[-1]//a + 1):
        dp[a * j] = False

count = 0
for d in dp:
    if d:
        count += 1
print(count)

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if a[0] == a[-1]: 
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1: 
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct): 
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n): 
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct): 
      c.add(num(div))


  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i) 

print(ans)

Solution (Python):



import sys
from collections import Counter

i2s = lambda: sys.stdin.readline().rstrip()

def main():
    N = int(i2s())
    A = sorted(map(int, i2s().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            if B[a * i]:
                B[a * i] = 0
    print(sum(B.values()))
    return

main()

Solution (Python):



from collections import Counter

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            if B[a * i]:
                B[a * i] = 0
    print(sum(B.values()))
    return

main()

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Solution (Python):

import sys

def solve(N, A):
    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)

def solve_old(N, A):
    A = sorted(A)
    dp = [True for i in range(N)]  

    idx = 0
    while True:
        a = A[idx]
        for j, target in enumerate(A[i+1:]):
            if target % a == 0:
                dp[idx + j + 1] = False


    for i, a in enumerate(A):
        if dp[i] == False:
            continue

        elif A.count(a) > 1:  
            dp[i] = False
            continue

        for j, target in enumerate(A[i + 1:]):  
            if target % a == 0:
                dp[i + j + 1] = False
    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


def solve_old(N, A):
    A = sorted(A)
    dp = [True for i in range(N)] 

    for i, a in enumerate(A):
        if dp[i] == False:
            continue

        elif A.count(a) > 1: 
            dp[i] = False
            continue

        for j, target in enumerate(A[i + 1:]): 
            if target % a == 0:
                dp[i+j+1] = False
    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)


if __name__ == '__main__':
    main()

Solution (Python):



from collections import Counter

def main():
    N = input()
    A = sorted(map(int, input().split(' ')))
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, A[-1] // a + 1):
            B[a * i] = 0
    print(Counter(B.values())[1])
    return

main()

Solution (Python):



import sys
from collections import Counter

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = sorted(int(c) for c in i2s().split(' '))
    max_ = A[-1]
    B = Counter(A)
    for a in A:
        if B[a] == 0:
            continue
        if B[a] > 1:
            B[a] = 0
        for i in range(2, max_ // a + 1):
            if a * i in B:
                B[a * i] = 0
    res = 0
    for v in B.values():
        if v:
            res += 1
    print(res)
    return

main()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort()
e=[1]*(10**6+1)
from collections import Counter
d=Counter(a)
ans=0
for i in a:
  if d[i]==1 and e[i]==1:ans+=1
  if e[i]==1:
    for j in range(i,10**6+1,i):e[j]=0
print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest
import os
import math
import collections
import math


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    
    
    

    
    
    n = int(input())

    a_list = list(map(int, input().split()))
    
    a_list.sort()
    collections.Counter(a_list)

    dp = [0 for i in range(1000001)]
    ans = 0

    
    a_counter = collections.Counter(a_list)
    for a, cnt in a_counter.items():

        
        if dp[a] > 0:
            dp[a] += 1
            continue

        
        
        aa = range(a, 1000001, a)
        for aaaa in aa:
            dp[aaaa] += cnt

    ans = 0
    for a in a_counter.keys():
        if dp[a] == 1:
            ans += 1

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(test_input, output)

    
    def test_1original_1(self):
        test_input = """6
        2 7 21 1000000 1000000 1000000"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_1original_2(self):
        test_input = """93
951 299 994 913 105 760 468 12 613 158 61 536 877 688 548 81 398 916 378 556 871 268 814 220 18 455 913 677 239 697 590 520 261 885 734 749 473 384 641 76 612 28 86 144 205 772 201 999 88 940 699 873 938 44 285 272 342 219 648 254 314 421 988 617 755 921 820 257 565 376 454 965 513 253 350 834 47 275 866 450 102 159 790 814 364 406 851 236 298 288 999 238 283
"""
        output = """67"""
        self.assertIO(test_input, output)

    def test_1original_3(self):
        test_input = """90
617 279 402 110 487 288 34 58 989 681 964 387 955 376 821 155 291 282 266 252 189 190 94 765 158 264 631 69 604 366 605 241 560 990 86 683 784 260 373 101 780 54 71 620 173 692 101 344 978 784 520 416 778 973 222 260 847 733 933 837 441 696 363 684 19 405 997 56 42 654 431 7 803 974 910 326 110 846 987 789 569 381 362 1 387 583 279 779 737 349
"""
        output = """1"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))

n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    mark=[0]*(10**6+5)
    for x in l:
        if mark[x]>=1:   
            mark[x]=2
            continue
        mark[x]=1
        i=2
        while x*i<10**6+1:
            mark[x*i]=2
            i+=1
    ans=0
    for x in l:
        if mark[x]==1:ans+=1
    print(ans)

Solution (Python):
n = int(input())
A = sorted(map(int, input().split()))
U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
for a in A:
    if a in ans:
        depricated.add(a)
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Solution (Python):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
A = sorted(map(int, input().split()))
U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    if a in ans:
        depricated.add(a)
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

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

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
        continue
    if 2 < cnt[a]:
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

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

cnt=[0]*(a[-1]+1)

for x in a:
  
 for i in range(x,a[-1]+1,x):
  
  
  cnt[i]+=1
  
ans=0
for x in a:
 if cnt[x]==1:
  ans+=1
print(ans)

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

U = 10**6
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
        continue
    if 2 < cnt[a]:
        continue
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

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

U = A[-1]
line = [1]*(U+1)
ans = set()
depricated = set()
cnt = [0]*(U+1)
for a in A:
    cnt[a] += 1
    if cnt[a] == 2 and line[a]:
        depricated.add(a)
    if line[a]:
        ans.add(a)
        for p in range(2*a, U+1, a):
            line[p] = 0
print(len(ans-depricated))

Solution (Python):
n = int(input())

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

M = 1000005
cnt = [0]*M
for i in A:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    
    for j in range(i,M,i):
        cnt[j] += 1

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

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


M=max(ls)
A=[0]*(M+1)
for i in range(N):
  a=M//ls[i]
  for j in range(1,a+1):
    if A[ls[i]]>=2:
      break
    else:
      A[j*ls[i]]+=1
  continue  
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Solution (Python):
N = int(input())
A = sorted((map(int,input().split())))
a_Max = A[-1]
B = [0]*a_Max

for a in A:
    if B[a-1] == 0:
        B[a-1] = 1
        for j in range(2,a_Max+1):
            if a*j > a_Max:
                break
            B[a*j-1] = 2
    elif B[a-1] == 1:
        B[a-1] = 2
            
ans = 0
for b in B:
    if b == 1:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
s = ([0]*1000001)
a.sort()
for i in a:
    s[i] += 1
ans = 0
for j in range(1000001):
    if s[j] == 1:
        ans += 1
    if s[j] > 0:
        for k in range(j, 1000001, j):
            s[k] = 0
print(ans)

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

a=sorted(a)
m=max(a)
dp=[0]*(m+1)
d={}
cnt=0
for i in range(n):
    b=a[i]
    if b in d:
        d[b]+=1
        continue
    else:
        d[b]=1
    j=b
    while b<=m+b:
        if b>m:
            break
        dp[b]+=1
        b+=j
        


for i in a:
    if dp[i]==1 and d[i]==1:
        cnt+=1

print(cnt)

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

ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)

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

ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
print(ans)

Solution (Python):
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
temp = 0
for i in li:
    if i == temp:
        isprime[i] = False
    if not isprime[i]:
        continue
    for k in range(i*2, inf+1, i):
        isprime[k] = False
    temp = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

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


M=max(ls)
A=[0]*(M+1)
for i in range(N):
  a=M//ls[i]
  for j in range(1,a+1):
    A[j*ls[i]]+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
B = [True]*(A[-1]+1)
i = 0
for i in range(N):
  if i < N-1 and A[i] == A[i+1]:
    B[A[i]] = False
  if A[-1] < 2*A[i]:
    continue
  M = A[-1]//A[i]+1
  for j in range(2,M):
    B[j*A[i]] = False

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

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    A.sort(reverse=True)

    if A[-1] == 1:
        if N > 1 and A[-2] == 1:
            print(0)
        else:
            print(1)
        return

    MAX = 10 ** 6 + 10
    memo = [False for _ in range(MAX)]
    for i in range(N):
        memo[A[i]] = True
        for j in range(A[i] * 2, MAX, A[i]):
            memo[j] = False
        if i - 1 >= 0 and A[i] == A[i - 1]:
            memo[A[i]] = False

    print(sum(memo))


def main():
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	count = 0
	a_max = A[-1]
	dp = [1]*a_max
	for a in A:
		point = dp[a-1]
		if point == 1:
			dp[a-1] = 2
			count += 1
			for ai in range(a*2,a_max+1,a):
				dp[ai-1] = 0
		elif point == 2:
			count -= 1
			dp[a-1] = 0
	print(count)






if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
def D():
    N = int(input())
    A = list(map(int, input().split()))
    nums = Counter(A)
    if 1 in nums:
        if nums[1] > 1:
            print(0)
            return
        else:
            print(1)
            return
    n = max(A)
    dp = [True for i in range(n+1)]
    p = 2
    while (p <= n): 
        if (p in nums and dp[p] == True): 
            for i in range(p*2, n+1, p): 
                
                dp[i] = False
        p += 1
    ans = 0
    for num in nums:
        if nums[num] == 1 and dp[num]:
            
            ans += 1
    print(ans)

D()

Solution (Python):
N=int(input())

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


dp = [1]*max(A)
l = len(dp)

for a in A:
	if dp[a-1] == 1:
		dp[a-1] = 2
		for i in range(2*a, l+1, a):
			dp[i-1] = 0
	elif dp[a-1] == 2:
		dp[a-1] = 0

print(sum([1 for a in A if dp[a-1] != 0]))

Solution (Python):

n=int(input())
a=list(map(int,input().split()))
a.sort()
cnt=[0]*(a[-1]+1)
for x in a:
 for i in range(x,a[-1]+1,x):
  cnt[i]+=1
res=0
for x in a:
 if cnt[x]==1:
  res+=1
print(res)

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

b = [True for i in range(a[-1]+1)]

ans = 0

for i, j in enumerate(a):
    if b[j]:
        t = 1
        while j*t < len(b):
            b[j*t] = False
            t += 1
        
        if i == n-1:
            ans += 1
        elif j != a[i+1]:
            ans += 1
        
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
import collections
c = collections.Counter(a)
a = list(set(a))
n = len(a)
a = sorted(a)
B = [True]*(a[-1]+1)
ans = 0
for i in range(n):
    if B[a[i]]:
        if c[a[i]] == 1:
            ans += 1
    j = 2
    while a[i]*j <= a[-1]:
        B[a[i]*j] = False
        j += 1
print(ans)

Solution (Python):
n = int(input())
a = sorted(list(map(int, input().split())))
if n == 1:
    print(1)
    exit()  
check_list = [0] * (10**6 + 2)
ans = 0
for i in range(n):
    tmp = a[i]
    while tmp <= a[-1]:
        check_list[tmp] += 1
        tmp += a[i]
for aa in a:
    if check_list[aa] == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
import collections
sys.setrecursionlimit(10**6)

M = 10**6+5


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * M
    for i in range(n):
        if cnt[a[i]] != 0:
            cnt[a[i]] += 1
            continue

        for j in range(a[i], M, a[i]):
            cnt[j] += 1
    ans = 0
    for i in range(n):
        if cnt[a[i]] == 1:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)