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 deque
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = deque(a)
b = [0]*(10**6 +1)
ans = 0
for _ in range(n):
  x = a.popleft()
  if b[x] == 0:
    ans += 1
    b[x] = 2
    tmp = 2 * x
    while tmp <= 10**6:
      b[tmp] = 1
      tmp += x
  elif b[x] == 2:
    ans -=1
    b[x] = 1
print(ans)

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    adic={}
    for i in range(n):
        if a[i] in adic:
            adic[a[i]]+=1
        else:
            adic[a[i]]=1
    ans=0
    a=list(set(a))
    a.sort()
    maxa=max(a)
    dp=[True for i in range(maxa+1)]
    for i in a:
        if dp[i] and adic[i]==1:ans+=1
        j=i+i
        while j<=maxa:
            dp[j]=False
            j+=i
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
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 elem in unique:
    if cnt[elem] == 0:
        ans+=1

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
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 elem in unique:
    if cnt[elem] == 0:
        ans+=1

print(ans)

Solution (Python):
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

d = defaultdict(int)
for i in a:
  d[i] += 1

a.sort()
mx = max(a)

chk = [False for i in range(mx+1)]
cnt = 0
for i in range(n):
  if d[a[i]] >= 2:
    for j in range(a[i],mx+1,a[i]):
      chk[j] = True
    continue
  if chk[a[i]] == False:
    cnt += 1
  for j in range(a[i],mx+1,a[i]):
    chk[j] = True
print (cnt)

Solution (Python):
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
A.sort()
lim = A[-1]+1
B = [0] * lim
U = list(set(A))
C = Counter(A)

for a in U:
    if C[a] > 1:
        B[a] = 1
    for i in range(a*2, lim, a):
        B[i] = 1

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

print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A.sort()
flag=[0]*N

ans=0
M=A[-1]
B=[0]*(M+1)
for i in A:
    B[i]+=1

for i in A:
    if B[i]==1:
        ans+=1
    for j in range(i,M+1,i):
        B[j]+=1
print(ans)

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

n = int(input())
a = [int(x) for x in input().split()]
a.sort()
max_a = a[-1]
is_True = [1]*(max_a + 1)
for i in a:
    if is_True[i]:
        for j in range(2*i, max_a + 1, i):
            is_True[j] = False
cnt = 0
from collections import Counter
c = Counter(a)
for i in a:
    if is_True[i] and c[i] == 1:
        cnt += 1
print(cnt)

Solution (Python):
n = int(input())
a_list = list(map(int,input().split()))
a_list = sorted(a_list)
flag  = [0]*n


ans = 0
m = max(a_list)
b_list = [0]*(m+1)
for i in a_list:
    b_list[i] += 1
for i in a_list:
    if b_list[i] == 1:
        ans += 1

    for j in range(i , m+1 ,i):
        b_list[j]+= 1
print(ans)

Solution (Python):
from sys import stdin

def main():
    from collections import defaultdict
    input = stdin.readline

    n = int(input())
    a = sorted(list(map(int, input().split())))
    p = defaultdict(int)
    for x in a:
        p[x] += 1
    q = a[-1] + 1
    f = [True] * (q)
    for k, v in p.items():
        if v > 1:
            f[k] = False
        for i in range(k + k, q, k):
            f[i] = False
    print(sum(1 for x in a if f[x]))
main()

Solution (Python):
from collections import Counter

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

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

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

print(cnt)

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    a[i + i::i] = (0 for _ in a[i + i::i])
print(a.count(1))

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Solution (Python):
import sys

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

def main():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A)
    B = [0]*(M+1)
    ans = 0
    A.sort()
    
    for i in A:
        B[i] += 1
    
    for i in A:
        if B[i] == 1:
            ans += 1
        for j in range(i, M+1, i):
            B[j] += 1
    
    print(ans)

main()

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))

Solution (Python):
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  for j in range(i + i, N, i):
    if a[i]:
      a[j] = 0
print(a.count(1))

Solution (Python):
N = int(input())
l = [0]*(10**6+1)
for a in map(int,input().split()) :
    l[a] += 1
ans = 0

for i in range(1, 10**6 + 1) :
    if l[i] == 1 :
        ans += 1
    if l[i] > 0 :
        for j in range(i , 10**6 + 1, i) :
            l[j] = 0

print(ans)

Solution (Python):
from sys import stdin

def main():
    from collections import defaultdict
    input = stdin.readline

    n = int(input())
    a = sorted(list(map(int, input().split())))
    p = defaultdict(int)
    for x in a:
        p[x] += 1
    f = [True] * (10 ** 6 + 1)
    for k, v in p.items():
        if v > 1:
            f[k] = False
        for i in range(k + k, 10 ** 6 + 1, k):
            f[i] = False
    print(sum(1 for x in a if f[x]))
main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (A[-1] + 2)
c = 0

for a in A:
    if B[a] != 0:
        B[a] = 2
    for i in range(a, A[-1] + 1, a):
        B[i] += 1
for a in A:
    if B[a] == 1:
        c += 1
print(c)

Solution (Python):
N = int(input())
leng = 10**6+1
memo = [0]*leng
li = []
for n in map(int, input().split()):
    x = 0
    li.append(n)
    if memo[n] >1:
        pass
    else:
        while x < leng:
            memo[x] +=1
            x += n
count = 0
for n in li:
    if memo[n] == 1:
        count+=1
print(count)

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

d = defaultdict(int)

for i in a:
	d[i]+=1

arr = []
remain = set()
for i in d:
	if d[i]!=1:
		remain.add(i)
arr = list(set(a))
arr.sort()

maxa = 10**6+1
ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

tyo = 0

for i in remain:
	if ans[i]==1:
		tyo+=1

print(ans.count(1)-tyo)

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

d = defaultdict(int)

for i in a:
	d[i]+=1

arr = []
remain = set()
for i in d:
	if d[i]!=1:
		remain.add(i)
arr = list(set(a))
arr.sort()

if len(arr)==0:
	print(0)
	exit()

maxa = 10**6+1
ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

tyo = 0

for i in remain:
	if ans[i]==1:
		tyo+=1

print(ans.count(1)-tyo)

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

M=[0]*1001000

def main():
  n=I()
  l=LI()
  l.sort()
  MAX=l[-1]

  for x in l:
    M[x]+=1
    if M[x]==2:
      continue

    for i in range(2,1001000):
      y=i*x
      if MAX<y:
        break

      M[y]+=1

  ans=0
  for x in l:
    if M[x]==1:
      ans+=1

  
  return ans


print(main())

Solution (Python):
N = input()
A = list(map(int, input().split()))
N = int(N)
MA = max(A)
s=0
LS = [0 for i in range(0,MA)]
for i in range(0,N):
  k=1
  while A[i]*k<=MA:
    LS[A[i]*k-1] +=1
    k +=1
for j in range(0,N):
  if LS[A[j]-1]==1:
    s+=1
print(s)

Solution (Python):
d=[0]*8**7
for j in[*open(0)][1].split():d[int(j)]+=1
i=0
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(d.count(1))

Solution (Python):
d=[0]*8**7
for i in[*open(0)][1].split():d[int(i)]+=1
i=r=0
while i<1e6:
 i+=1;r+=d[i]==1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(r)

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

'''

'''

n = int(input())
a = sorted(map(int, input().split()))
largest = a[-1]

div = [1] * (largest+1)
count = 0
arr = []

for i, v in enumerate(a):
    if i < (n-1) and a[i+1] == v:
        div[v] = 0
    else:
        arr.append(v)

for num in arr:
    if div[num]:
        count += 1

    for d in range(num, largest+1, num):
        div[d] = 0

print(count)

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

'''

'''

n = int(input())
a = sorted(map(int, input().split()))
largest = a[-1]

div = [1] * (largest+1)
count = 0
arr = []

for i, v in enumerate(a):
    if i < (n-1) and a[i+1] == v:
        div[v] = 0
    else:
        arr.append(v)

arr.sort()

for num in arr:
    if div[num]:
        count += 1

    for d in range(num, largest+1, num):
        div[d] = 0

print(count)

Solution (Python):

def main():
    N, *A = map(int, open(0).read().split())
    lim = max(A) + 1
    sieve = [0] * lim
    for a in A:
        sieve[a] += 1
        if sieve[a] > 1:
            continue
        for i in range(a * 2, lim, a):
            sieve[i] = 2
    print(sum(sieve[a] == 1 for a in A))


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = sorted(list(map(int,input().split())))
maxa = max(a)+1
dp = [0]*maxa

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

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

max_arr = max(arr)
dp = [0] * (max_arr + 1)

for i in arr:
    for j in range(i, max_arr + 1, i):
        dp[j] += 1

print([dp[i] for i in arr].count(1))

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

m = 1000005

l = [0] * m


for a in a_list:
    
    if l[a] != 0:
        
        l[a] = 2
        continue

    a_sub = a
    while a_sub < m:
        l[a_sub] += 1
        a_sub += a


ans = 0
for a in a_list:
    if l[a] == 1:
        ans += 1

print(ans)

Solution (Python):
n=int(input())
arr=list(map(int,input().strip().split()))
arr.sort()
maxi=arr[-1]
booll=[True]*(maxi+1)
r=0
for i in range(n-1):
    a=arr[i]
    if(booll[a]==True):
        for j in range(a,maxi+1,a):
            booll[j]=False
        if(a<arr[i+1]):
            r=r+1
if(booll[arr[n-1]]==True):
    r=r+1
print(r)

Solution (Python):
n=int(input())
arr=list(map(int,input().strip().split()))
arr.sort()
maxi=arr[-1]
booll=[True]*(maxi+1)
r=0
for i in range(n-1):
    a=arr[i]
    if(booll[a]==True):
        for j in range(a,maxi+1,a):
            booll[j]=False
        if(a<arr[i+1]):
            r=r+1
if(booll[arr[n-1]]==True):
    r=r+1
print(r)

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

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

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

d = [False]*(10**6+1)

count = 0

for i in range(1, 10**6+1):
    if not c[i]:
        continue
    if d[i]:
        continue
    if c[i] == 1:
        count += 1
    for j in range(i, 10**6+1, i):
        d[j] = True

print(count)

Solution (Python):
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, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13,
                                        17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    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):
        def f(x): return (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 sorted(ret)


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

A_array.sort()

set_A = set(A_array)


ans = 0

for i in range(N):
    if i != 0:
        if A_array[i] == A_array[i - 1]:
            continue
    if i != N - 1:
        if A_array[i] == A_array[i + 1]:
            continue

    a = A_array[i]
    for p in divisors(a)[:-1]:
        if p in set_A:
            break
    else:
        ans += 1

print(ans)

Solution (Python):

N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
flag=[False for i in range(10**6+1)]

re=[]
for i in range(N):
    if flag[A[i]]:
        re.append(A[i])
    flag[A[i]]=True

ans=0
for i in range(1,10**6+1):
    if flag[i]:
        ans+=1
        for j in range(i*2,10**6+1,i):
            flag[j]=False

for i in set(re):
    if flag[i]:
        ans-=1
print(ans)

Solution (Python):
from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    C = Counter(A)

    MAX = 1000005
    T = [0]*MAX

    ans = 0
    for a in C.keys():
        if T[a]:
            continue
        else:
            for i in range(2*a, MAX, a):
                T[i] = 1

    ans = 0
    for a, n in C.items():
        if n == 1 and T[a] == 0:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
mx = a[-1]
dp = ["
for i in a:
    if dp[i]==True: dp[i] = False
    elif dp[i]=="
        dp[i] = True
        mult = 2
        while i*mult<=mx:
            dp[i*mult] = False
            mult+=1
ans = 0
for i in a:
    if dp[i]==True:
        ans+=1
print(ans)

Solution (Python):
from collections import Counter

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

max_a = max(a)
ok = [False] * (max_a + 1)
sorted_a = sorted(a)

ans = 0
for i in range(n):
    if ok[sorted_a[i]]:
        continue
    else:
        if not(i < n - 1 and sorted_a[i] == sorted_a[i + 1]):
            ans += 1
        for j in range(1, max_a // sorted_a[i] + 1):
            ok[sorted_a[i] * j] = True
        
print(ans)

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

bool_ary = [0] * original_ary[-1]

for num in original_ary:
    bool_ary[num-1] += 1
    if bool_ary[num-1] == 1:
        for multiple in range(num * 2, original_ary[-1]+1, num):
            bool_ary[multiple-1] = 2

print(bool_ary.count(1))

Solution (Python):
import numpy as np

length = int(input())
As = list(map(int, input().split()))

As.sort()


check = np.zeros(10**6+1)

answer = 0


for i in range(length):
    if check[As[i]] == 0:
        
        
        check[::As[i]] = 1
        
        
        
        if  i == (length - 1) or  As[i] != As[i + 1]:
                answer = answer + 1

print(answer)

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

dp = {i: 0 for i in range(1, maxa+1)}

ans = 0
for i in range(n):
    if dp[a[i]] == 1:
        continue

    if i == n - 1 or a[i] != a[i+1]:
        ans += 1

    t = 1
    while a[i]*t <= maxa:
        dp[a[i]*t] = 1
        t += 1

print(ans)

Solution (Python):





import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    nums.sort()

    check = [False] * (10 ** 6 + 1)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = True
    
    ans = 0
    for i in range(n):
        if check[nums[i]] == False:
            ans += 1
        if i == 0 or (i > 0 and nums[i] != nums[i - 1]):
            cnt = nums[i] * 2
            while cnt < 10 ** 6 + 1:
                
                check[cnt] = True
                cnt += nums[i]
        
    print(ans)

    
    return

if __name__ == "__main__":
    main()

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)

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

n = int(input())
a = [int(x) for x in input().split()]
maxval = 10 ** 6
factor_cnt = [0] * (maxval+1)
factor_cnt[0] = 2
for i in range(n):
    if factor_cnt[a[i]] > 1:
        continue
    for k in range(a[i], maxval+1, a[i]):
        factor_cnt[k] += 1

result = sum(factor_cnt[v] <= 1 for v in a)
print(result)

Solution (Python):

N = int(input())
li = [True for _ in range(0, 10**6 + 1)]
A = list(map(int, input().split()))
A.sort()
used = {}
for i in range(N):
    if A[i] not in used.keys():
        used[A[i]] = 1
    else:
        used[A[i]] += 1
ans = 0
for k in used.keys():
    if used[k] > 1:
        for j in range(k, 10**6 + 1, k):
            li[j] = False
for i in range(N):
    if li[A[i]] and used[A[i]] == 1:
        ans += 1
    else:
        continue
    for j in range(A[i], 10**6 + 1, A[i]):
        li[j] = False
print(ans)

Solution (Python):
import numpy as np
N = int(input())
A = list(map(int,input().split()))

chofuku_dict = {}
chofuku = []

for a in A:
    if a not in chofuku_dict:
        chofuku_dict[a] = 1
    else:
        chofuku.append(a)
        
chofuku = set(chofuku)

A = list(set(A))
A.sort()

bl = np.array([0] + [1]*A[-1])

ans = 0
for a in A:
    if bl[a] == 0:
        continue
    if a not in chofuku:
        ans += 1
    bl[2*a::a] = 0
print(ans)

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
dp=[0 for j in range(A[len(A)-1]+1)]

for i in range(len(A)):
    num=A[i]
    while(num<len(dp)):
            dp[num]+=1
            num+=A[i]

count=0
for i in range(len(A)):
    if i!=0:
        if A[i]!=A[i-1]:
           if dp[A[i]]==1:
            count+=1
    else:
        if dp[A[i]]==1:
            count+=1

print(count)

Solution (Python):
M=10**6+1
_,*l=map(int,open(0).read().split())
a=[0]*M
for i in sorted(l):
  a[i]+=1
  if a[i]==1:
    for j in range(2*i,M,i): a[j]+=9
print(a.count(1))

Solution (Python):

import os
import sys
from io import BytesIO, IOBase


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    ans = 0
    k=max(arr)
    d = [0]*(k+1)
    for i in range(n):
        d[arr[i]]+=1
    for i in range(n):
        x=arr[i]
        if d[x]==1:
            ans+=1
        for j in range(x,k+1,x):
            d[j]+=1
    print(ans)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Solution (Python):

import os
import sys
from io import BytesIO, IOBase


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    ans = 0
    k=max(arr)
    d = [0]*(k+1)
    if arr[0] == 1:
        if n>1 and arr[1]==1:
            print(0)
            quit()
        else:
            print(1)
            quit()
    for i in range(n):
        d[arr[i]]+=1
    for i in range(n):
        x=arr[i]
        if d[x]==1:
            ans+=1
        for j in range(x,k+1,x):
            d[j]+=1
    print(ans)




BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    n = int(input())
    A = [int(i) for i in input().split()]

    max_dp = max(A) + 1
    dp = [0] * max_dp


    for a in A:
        if dp[a] >= 2:
            continue
        dp[a] += 1
        for i in range(a << 1, max_dp, a):
            dp[i] += 2
    print(dp.count(1))


if __name__ == '__main__':
    main()