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):
N = int(input())
A = list(map(int,input().split()))

from collections import Counter
C = dict(Counter(A))  

Ckey = list(C.keys())


B = sorted(Ckey)


out=0
table=[0]*(10**6)
for i in range(len(B)):
        if table[B[i]-1]==1:
            continue
        elif C[B[i]]==1:
            out+=1
        k=1
        while k*B[i]<=10**6:
            table[k*B[i]-1]=1
            k+=1

print(out)

Solution (Python):
import collections
n=int(input())
a=list(map(int,input().split()))
a=collections.Counter(a)
b,c=[],[]
for t in a:
  if a[t]==1:
    b.append(t)
  else:
    c.append(t)
if len(b) == 0:
  print(0)
  exit()
b.sort()
bm = b[-1]
ok = [True]*(bm+1)

if len(c)>0:
  c.sort()
  for t in c:
    if t>=bm: continue
    if ok[t] == False: continue
    i = 1
    while i*t<=bm:
      ok[i*t]=False
      i+=1
for t in b:
  if ok[t] == False: continue
  i = 2
  while i*t<=bm:
    ok[i*t]=False
    i+=1
ans = 0
for t in b:
  if ok[t]:
    ans+=1
print(ans)

Solution (Python):
import sys

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

if n==1:
    print(1)
    sys.exit()


A.sort()
A_max=A[-1]

dp=[False]*(A_max+1)
ans=0

temp=A[0]
while True:
    if temp>A_max:
        break
    dp[temp]=True
    temp+=A[0]

if A[0]!=A[1]:
    ans+=1


for i in range(1,n-1):
    if dp[A[i]]:
        continue

    temp=A[i]
    while True:
        if temp>A_max:
            break
        dp[temp]=True
        temp+=A[i]
    
    if A[i-1]!=A[i] and A[i]!=A[i+1]:
        ans+=1


if not dp[A[n-1]] and A[n-2]!=A[n-1]:
    ans+=1

print(ans)

Solution (Python):
import math

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A.sort()
  MAX = A[-1]
  dp = [True] * MAX
  c = [0] * MAX
  ans = 0

  for a in A:
    i = a - 1
    c[i] += 1

    if((not dp[i]) and c[i] > 1):
      continue

    e = a * 2    
    while e <= MAX:
      dp[e-1] = False
      e += a
      
  for v in A:
    i = v - 1
    if dp[i] and c[i] == 1:
      ans += 1

  print(ans)

if __name__ == "__main__":
  main()

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


maxA = max(a)
dp = [0]*(maxA+1)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in a:
    if dp[e] == 1:
        count += 1

print(count)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
M = max(a)
ok = [0]*(M+1)
a.sort()

for i in range(n):
    ok[a[i]] += 1
    if ok[a[i]] == 1:
        for g in range(a[i], M+1, a[i]):
            if g != a[i]:
                ok[g] += 2


print(ok.count(1))

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, = map(int, input().split())
maxA = max(A)

C = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    C[a] += 1

D = {a: 0 for a in range(1, maxA + 1)}
for a in A:
    if C[a] > 0:
        tmp = 2
        while a * tmp <= maxA:
            D[a * tmp] = 1
            tmp += 1
ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1
print(ans)

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))

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

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            memo[a * i] += 1

    ans = 0
    c = collections.Counter(A)
    for a in A:
        
        if memo[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from math import sqrt
from collections import Counter, deque
N = int(input())
As = list(mapint())
As.sort()
C = Counter(As)
S = set()

MAX = As[-1]
cnt = 0
for n in range(N):
    p = As[n]
    if p in S:
        continue
    i = 1
    while MAX>=p*i:
        S.add(p*i)
        i += 1
    if C[p]>=2:
        continue
    cnt += 1

print(cnt)

Solution (Python):
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))

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

    for a in aset:
        for i in range(2, 10 ** 6 + 1):
            if a * i > 10 ** 6:
                break
            memo[a * i] += 1

    ans = 0
    c = collections.Counter(A)
    for a in A:
        
        if memo[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = [0] + list(map(int, input().split()))
A.sort()
A_max = A[-1]
dp = [1] * (1 + A_max)
from bisect import bisect_left, bisect_right

for x in A[1:]:
    if dp[x] == 0:
        continue
    y = x * 2
    while y <= A_max:
        dp[y] = 0
        y += x
ans = []
for i in range(1, A_max+1):
    if dp[i] == 1:
        idx_l = bisect_left(A, i)
        idx_r = bisect_right(A, i)
        if idx_r - idx_l > 1:
            continue
        if A[idx_l] == i:
            ans.append(idx_l)
print(len(ans))

Solution (Python):
import math
num = int(input())
arr = input().split()
arr = sorted([int(i) for i in arr])

lis1 = [0]*(arr[-1]+1)

for num in arr:
  for j in range(0, len(lis1), num):
    lis1[j] += 1

cnt = 0
for num in arr:
  if lis1[num]==1: cnt+=1
    
print(cnt)

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

maxA = max(a)
dp = [0]*(maxA+1)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in a:
    if dp[e] == 1:
        count += 1

print(count)

Solution (Python):
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in range(len(a)-1):
    if a[i]==a[i+1]:
        dp[a[i]]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)

Solution (Python):
n = int(input())
a = map(int, input().split())
a = list(sorted(a))
big = a[n-1]
mark = [0]*(big+1)
for x in a:
    mark[x] += 1
    if mark[x] > 1:
        continue
    for j in range(x*2, big+1, x):
        mark[j] += 1

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

print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A.sort()
l = [0] * A[-1]
for i in range(N):
    l[A[i] - 1] += 1
for i in range(N):
    if l[A[i] - 1] > 1:
        l[A[i] - 1] = 0
    elif l[A[i] - 1] == 0:
        continue
    temp = A[i]
    while True:
        temp += A[i]
        if temp > A[-1]:
            break
        l[temp - 1] = 0
print(sum(l))

Solution (Python):
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;
        continue

    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 2
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))

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

A.sort()

isWari = [True] * (10**6+1)

before = 0

for i in range(len(A)):
    if(before == A[i]):
        continue
    index = A[i]
    for j in range(index*2,10**6+1,index):
        isWari[j] = False
    before = A[i]

count = 0

for i in range(len(A)):
    if(i!=0 and A[i-1] == A[i]):
        continue
    if(i!=len(A)-1 and A[i] == A[i+1]):
        continue
    
    if(isWari[A[i]]):
        count += 1

print(count)

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

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

for i in A:
    if l[i] <= 1:
        for j in range(0,10**6+1,i):
            l[j] += 1
count = 0
for i in A:
    if l[i] == 1:
        count += 1
print(count)

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

l = [0]*(10**6 +1)
for i in a:
    l[i]+=1
num = 0

for i in range(10**6+1):
    if l[i] == 1:
        num += 1
    if l[i] != 0:
        for j in range(2*i, 10**6+1, i):
            if l[j]:
                l[j] += 1
print(num)

Solution (Python):
N = int(input())
AS = [int(x) for x in input().split()]

AS.sort(reverse=True)
MAX_AS = AS[0]
table = [0] * (MAX_AS + 1)  

alreadyVisited = {}
for i in range(N):
    x = dx = AS[i]
    if alreadyVisited.get(x, False):
        table[x] = 0
        continue
    alreadyVisited[x] = True

    table[x] = 1
    while True:
        x += dx
        if x > MAX_AS:
            break
        table[x] = 0

print(sum(table))

Solution (Python):

n, *a = map(int, open(0).read().split())
a.sort()
m = a[-1]  
s = [0]*(m+1)  
ans = 0
for i in a:
    if s[i] <= 1:  
        for j in range(i, m+1, i):
            s[j] += 1  


for k in a:
    if s[k] == 1:
        ans += 1
print(ans)

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

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


b = sorted(list(A))
dp = [0]*(max(A)+1)

m_a = max(A)+1
for i in b:
    dp[i] += 1
    if dp[i]==1 :
        for j in range(i*2, m_a,i):
            dp[j] +=100

print(dp.count(1))

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

def main(n,a):
    maxa=10**6
    isprime=[True]*(maxa+1)
    sa=sorted(a)

    prevx=0
    for x in sa:
        if isprime[x]==False:
            continue
        if prevx==x:
            isprime[x]=False
            continue

        i=x*2
        while(i<=maxa):
            isprime[i]=False
            i+=x
        prevx=x
    
    count=0
    for x in sa:
        if isprime[x]==True:
            count+=1
    return count

if __name__=='__main__':
    n,a=readinput()
    ans=main(n,a)
    print(ans)

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


maxA = max(a)
dp = [0]*(maxA+1)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in a:
    if dp[e] == 1:
        count += 1

print(count)

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

a.sort()





max_a = max(a)
i_list = [0] * (max_a + 1)

for i in a:
    i_list[i] += 1
    if i_list[i] == 1:

        
        for j in range(2*i, max_a + 1, i):
            i_list[j] += 2

print(i_list.count(1))

Solution (Python):
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a.sort()
  a_max=a[-1]
  x=[True]*(a_max+1)
  a=a+[0]
  for i in range(n):
    ai=a[i]
    if x[ai]:
      l=a_max//ai-1
      aj=ai
      for _ in range(l):
        aj+=ai
        x[aj]=False
    if a[i]==a[i+1]:
      x[a[i]]=False
  ans=0
  x[0]=False
  for i in a:
    if x[i]:
      ans+=1
  print(ans)
if __name__=='__main__':
  main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
m = max(A)
U = [0]*(m+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,m+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,m+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Solution (Python):
import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

for i in range(N):
    ai = A[i]
    for j in range(2,A[-1]+1):
        if ai*j > A[-1]:
            break
        dp[ai*j] = False

ans = 0
finish = [True for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]] and finish[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
            finish[A[i]] = False

print(ans)

Solution (Python):


import sys










from collections import Counter              




















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def enum_duplicate_num(L):
        cnt = Counter(L)
        dup_num_set = set()
        buf = []
        for num in L:
            if cnt[num] > 1 and num not in dup_num_set:
                dup_num_set.add(num)
                buf.append(num)
            elif cnt[num] == 1:
                buf.append(num)
        return dup_num_set, buf


    def fill_mul_false(num, table):
        for ind in range(num*2, 10**6+1, num):
            table[ind] = False
    
    
    n = ii()
    command = lmi()
    dup_num_set, command = enum_duplicate_num(command)
    table = [False] * (10 ** 6 + 1)
    for num in command:
        table[num] = True
    for num in command:
        if table[num]:
            fill_mul_false(num, table)
    for num in dup_num_set:
        table[num] = False
    
    print(table.count(True))



if __name__ == "__main__":
    main()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
a.sort()
b = [0]*1000001

s = set()

for i in a:
    if b[i]:
        continue
    if i in s:
        b[i] = 1
    s.add(i)
    for j in range(2, 1000001):
        if i*j > 10 ** 6:
            break
        b[i*j] = 1

ans = 0
for i in a:
    if b[i] == 0:
        ans += 1

print(ans)

Solution (Python):
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans_list = [0] * (a_list[n - 1] + 1)
ans = 0

for a in a_list:
    if ans_list[a] >= 1:
        ans_list[a] += 1
        continue
    for j in range(2 * a, a_list[n - 1] + 1, a):
        ans_list[j] += 1
    ans_list[a] = 1

for a in a_list:
    if ans_list[a] == 1:
        ans += 1
print(ans)

Solution (Python):
import bisect as bc

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

dp = [True for _ in range(A[-1]+1)]

for i in range(N):
    ai = A[i]
    for j in range(2,A[-1]+1):
        if ai*j > A[-1]:
            break
        if dp[ai*j]:
            dp[ai*j] = False

ans = 0
finish = [True for _ in range(A[-1]+1)]
for i in range(N):
    if dp[A[i]] and finish[A[i]]:
        if bc.bisect_right(A,A[i]) - bc.bisect_left(A,A[i]) == 1:
            ans += 1
            finish[A[i]] = False

print(ans)

Solution (Python):
from collections import Counter

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

cnt = Counter(A) 

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


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

for a in A:
    if C[a] == 0:
        i = 1
        while True:
            if a*i > 10**6:
                break
            C[a*i] = 1
            i += 1
        if cnt[a] == 1:
            ans += 1

print(ans)

Solution (Python):
from collections import Counter

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
max_A = A[-1]
cnt = Counter(A)
admissible = [True] * (max_A + 1)
checked = [False] * (max_A + 1)
ans = 0
for a in A:
    if not admissible[a] or checked[a]: continue
    ans += 1
    i = 2
    while a * i <= max_A:
        admissible[a * i] = False
        i += 1
    checked[a] = True
    if cnt[a] > 1: ans -= 1
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,max(A)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,10**6+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Solution (Python):
def main():
    A_MX = 10 ** 6

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

    ctr = [0] * (A_MX + 1)
    for x in A:
        ctr[x] += 1

    B = [0] * (A_MX + 1)

    ans = 0
    for x in A:
        if B[x]: continue
        if ctr[x] == 1:
            ans += 1
        y = x
        while y <= A_MX:
            B[y] = 1
            y += x
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from collections import Counter
    n = int(input())
    A = sorted(list(map(int, input().split())))
    c = Counter(A)
    result = 0
    flag = [True] * (A[-1] + 1)
    for i in A:
        if flag[i]:
            result += 1
            for j in range(2*i, A[-1] + 1, i):
                flag[j] = False
    for k, v in c.items():
        if v > 1:
            if flag[k]:
                result -= v
    print(result)
main()

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
a_max = max(A)
table = [True for i in range(a_max+1)]
for a in A:
    i = 2
    k = a * 2
    while k <= a_max:
        table[k] = False
        k += a
count = 0
for i, a in enumerate(A):
    if i < N - 1 and A[i] == A[i+1]:
        table[a] = False
    if table[a]:
        count += 1
print(count)

Solution (Python):

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




MAX = 10**6+1000
l = [True] * MAX


count = 0
last = -1
mode = 0
for i in range(len(A)):
    e = A[i]
    if(last == e):
        count -= 1
        last = -1
    if(l[e]):
        count += 1
        for j in range(MAX):
            try:
                l[j*e] = False
            except IndexError:
                break
        last = e

    

print(count)

Solution (Python):
n=int(input())
A=list(map(int,input().split()))+[1000001]
A.sort()
m,ans=max(A)+1,0
li=[0 for _ in range(m)]
li[0]=1

for i in range(n):
  a=A[i]
  if not li[a]:
    if A[i+1] != a:
      ans += 1
    for i in range(a,m,a):
      li[i] = 1

print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a.sort()
p = [True for i in range(a[-1])]
ans = n
for k in range(n-1):
    if p[a[k]-1]:
        if a[k] != a[k+1]:
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break
        else:
            ans -= 1
            for i in range(1,a[-1]+1):
                if a[k]*i <= a[-1]:
                    p[a[k]*i-1] = False
                else:
                    break  
    else:
        ans -= 1    
k = n-1
if p[a[k]-1]:
    for i in range(1,a[-1]+1):
        if a[k]*i <= a[-1]:
            p[a[k]*i-1] = False
        else:
            break
else:
        ans -= 1   
print(ans)

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

def main():
    N = int(input().strip())
    l = [int(i) for i in input().strip().split()]
    ans = 0
    m = max(l)
    dp = [0] * (m+1)
 
    for n in l:
        for j in range(n, m + 1, n):
            dp[j] += 1
 
    for n in l:
        if dp[n] == 1:
            ans += 1
 
    return ans
 
if __name__ == "__main__":
    print(main())

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    ma = max(a)+1
    al = [True]*ma
    ans = 0
    pi = 0
    for i in a:
        if al[i]:
            ans += 1
            for j in range(i,ma,i):
                al[j] = False
            pi = i
        else:
            if i == pi:
                ans -= 1
                pi = 0

    print(ans)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    w = [0] * (10 ** 6 + 1)
    for a in A:
        w[a] += 1
    f = [False] * (10 ** 6 + 1)
    for a in A:
        if f[a]:
            w[a] = 0
            continue
        for b in range(a * 2, 10 ** 6 + 1, a):
            w[b] = 0
        f[a] = True
    print(sum(w))

if __name__ == '__main__':
    main()

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

a.sort()


import numpy as np
U=10**6 + 5
is_prime = np.zeros(U,np.bool)

is_prime[1::] = 1
M = int(U**.5)+1
for ai in a:
    if is_prime[ai]:
        is_prime[ai*2::ai] = 0
    

ans = 0

import collections
cnt = collections.Counter(a)
for ai in a:
    if is_prime[ai] and cnt[ai] == 1:
        ans += 1

print(ans)

"""
sa = set()
for ai in a:
    if ai in sa:
        sa.discard(ai)
        continue
    sa.add(ai)
"""

"""
p = list(range(10**6+10))

a = list(sa)
a.sort()

print(a)

import fractions
def lcm(a, b):
    return a * b // fractions.gcd(a, b)

ans = 1
l = 1
for i in range(n):
    if lcm(a[i], l) < a[i] * l:
        continue
    l = lcm(a[i], l)
    ans += 1
print(ans)

"""

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

A.sort()

maxnum = A[-1]
checklist = [True]*(maxnum+1)
before = 0

for a in A:
    if before == a:
        checklist[a] = False
        continue
    num = 2
    while num * a <= maxnum:
        checklist[a * num] = False
        num += 1
    before = a

ans = 0
for i in A:
    ans += checklist[i]
print(ans)

Solution (Python):
N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
M = max(A)
dp = [False] * (M+ 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (M// a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
A.sort()
ans = 0
max_A = max(A)
dp = [True]*(max_A+1)  
happend = set()
for a in A:
    if C[a] >= 2:
        if a in happend:
            continue
        else:
            
            x = a * 2
            while x <= max_A:
                dp[x] = False
                x += a
            happend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a * 2
        while x <= max_A:
            dp[x] = False
            x += a
print(ans)

Solution (Python):



n = int(input())
lis = list(map(int,input().split()))
lis.sort()
MAX = lis[-1]
lis2 = [0]*(MAX+1)


ans = 0

for num in lis:
    for i in range(num, MAX+1, num):
            lis2[i] += 1

for j in set(lis):
    if lis2[j] == 1:
        ans += 1
print(ans)

Solution (Python):
import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    A.sort()
    ans=0
    

    T=[True]*A[-1]
    

    for i,a in enumerate(A):
        if T[a-1]:
            j=2*a
            while j <= A[-1]:
                T[j-1]=False
                j+=a
            if not i+1==len(A):
                if A[i]==A[i+1]:
                    T[a-1]=False

    for a in A:
        if T[a-1]:
            ans+=1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

amax = max(A)
dp = [True] * (amax + 1)
count = [0] * (amax + 1)

for a in A:
    count[a] += 1
    b = 2 * a
    while b <= amax:
        dp[b] = False
        b += a

ans = 0
for a in A:
    if count[a] > 1:
        continue
    if dp[a]:
        ans += 1
print(ans)

Solution (Python):






from collections import deque,defaultdict











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0
for i in A:
   dic[i] += 1
A = list(set(A))

is_prime = [True] * (10**6+1)

for i in range(len(A)):
    
    
    
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False 

 
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        
        cnt += 1
print(cnt)

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

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

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

Solution (Python):
n = int(input())
arr = [int(x) for x in input().split()]
max_arr = max(arr)
mark = [0 for i in range(max_arr+1)]

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

count = 0
for i in range(n):
    if mark[arr[i]] == 1:
        count += 1
print(count)

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = A[-1]
divisible = [False] * (M + 1)
ans = 0
for i, a in enumerate(A):
    if not (i < N - 1 and A[i+1] == a) and not divisible[a]:
        ans += 1
    for b in range(a, M + 1, a):
        divisible[b] = True
print(ans)

Solution (Python):
from collections import Counter

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

flags = [True] * (A[-1] + 1)

for a in A:
    for mul in range(2, A[-1] // a + 1):
        flags[a * mul] = False
print(sum([flags[a] and c[a] == 1 for a in A]))

Solution (Python):
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
A.sort()
max_a = A[-1] + 1
count_a = Counter(A)
dp = [True for i in range(max_a)]
ans = 0

for a in A:
    if dp[a] and count_a[a] == 1:
        ans += 1

    for j in range(a*2, max_a, a):
        dp[j] = False

print(ans)

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

for i in sorted(a):
  t[i] += 1
  if t[i] == 1:
    for j in range(2*i,M,i):
      t[j] += 10
      
print(t.count(1))

Solution (Python):
from math import sqrt
from collections import Counter


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

    ans = 0
    p = [0] * (10**6 + 1)
    c = Counter(A)

    for a in c.keys():
        tmp = a * 2
        while tmp <= 10**6:
            p[tmp] = 1
            tmp += a

    for a in A:
        if p[a] == 0 and c[a] == 1:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	
	al = lin()
	al.sort()
	
	unique_al = list(set(al))
	unique_al.sort()
	
	al_counter = collections.Counter(al)
	ok=[v for v in al_counter.keys() if al_counter[v] == 1]
	d = {v:i for i,v in enumerate(ok)}
	max_v = 10**6+1
	for check in unique_al:
		for v in range(2*check, max_v, check):
			if v in d:
				ok[d[v]]=0
				
	return sum([v > 0 for v in ok ])
		
	
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):


from collections import defaultdict, Counter

def main():
    
    
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    
    dup_cnt = Counter(A)
    dup = set(x for x in dup_cnt if dup_cnt[x] > 1)
    A_set = set(A)
    A = list(A_set)
    A.sort()
    N = len(A)
    max_A = A[-1]
    prime = [True]*(max_A+1)
    ans = 0
    for x in A:
        if not prime[x]:
            continue
        else:
            for y in range(2*x, max_A+1, x):
                prime[y] = False
            if not x in dup:
                ans += 1
    print(ans)


if __name__ == "__main__":
    main()

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

A_freq = Counter(A)



A.sort()
maxi = A[-1]
note = [True for i in range(maxi+1)]
B=list(set(A))

for i in B:
  for j in range(2,maxi//i+1):
    note[j*i] = False




ans = 0
for i in B:
  if note[i] == True and A_freq[i]<=1:
    ans += 1
print(ans)

Solution (Python):
def main():
    from sys import stdin
    n = int(input())
    a = list(map(int, stdin.readline().split()))
    a.sort()
    amax = max(a)+1
    e = [True]*amax
    Alice = set()
    Bob = set()
    ans = 0
    
    for i in range(n):
        if e[a[i]] == True:
            Alice.add(a[i])
            for j in range(a[i], amax, a[i]):
                e[j] = False
        else:
            if a[i] in Alice:
                Bob.add(a[i])
    
    print(len(Alice - Bob))
if __name__ == "__main__":
    main()

Solution (Python):
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)

isprime = {a[i]:True for i in range(n)}

for i in range(n): 
    if not isprime[a[i]]: continue
    j = 2
    while a[i]*j < a[-1]+1:
        if isprime.get(a[i]*j) == True:
            isprime[a[i]*j] = False
        j += 1

ensem = list(c.values())
key = list(c.keys())
diff = len([i for i in range(len(c)) if ensem[i] != 1 and isprime[key[i]]])
print(list(isprime.values()).count(True)-diff)

Solution (Python):
from collections import defaultdict
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
count = 0
ap = defaultdict(int)
for i in range(1, n):
    if arr[i] == arr[i-1]:
        ap[arr[i]] = 1
        
for i in range(n):
    if not ap[arr[i]]:
        count += 1
    if i == 0 or arr[i] != arr[i-1]:
        for j in range(arr[i], 1000001, arr[i]):
            ap[j] = 1
print(count)