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



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = sorted(LI())

    m = max(a)
    t = [False] * (m + 1)
    r = 0
    for i in range(n):
        ai = a[i]
        if t[ai]:
            continue
        for j in range(ai, m+1, ai):
            t[j] = True
        if i < n-1 and a[i+1] == ai:
            continue
        r += 1

    return r


print(main())

Submission status: Accepted

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
lista.sort()
listtf=[]
s=0
for i in range(lista[n-1]):
    listtf+=[True]
for i in range(n):
    
    if(listtf[lista[i]-1]):
        if(i<n-1 and lista[i]==lista[i+1]):
            s-=1
        s+=1
        t=1
        while(t*lista[i]<=lista[n-1]):
            listtf[lista[i]*t-1]=False
            t+=1
print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        c[i] += 1

ans = 0
for ai in a:
    if c[ai] == 1:
        ans += c[ai]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
arr=[1]*(max(inp)+1)
inp.sort()
d=Counter([])
for i in range(len(arr)):
    if c[i]>=1 and arr[i]==1:
        if d[i]==0:
            d[i]+=1
        else:
            continue
        k=2
        while k*i<len(arr):
            arr[k*i]=0
            k+=1
ans=0
for item in d.keys():
    if c[item]==1:
        ans+=1
print (ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    A_max = A[-1]
    g = []
    table = [True]*(A_max+1)
    for i,a in enumerate(A):
        if table[a]:
            temp = a
            while A_max >= temp:
                table[temp] = False
                temp+=a
            if i==n-1 or a!=A[i+1]:
                g.append(a)
    print(len(g))
main()

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
maxA = max(A)
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
D = {a: 0 for a in A}
for a in A:
    if C[a] > 1:
        D[a] = 1
    for b in range(2 * a, maxA + 1, a):
        D[b] = 1
print(sum([D[a] == 0 for a in A]))

Submission status: Accepted

Solution code:
import collections


if __name__ == "__main__":
    N = int(input())
    A = [int(x) for x in input().split(" ")]
    counter = collections.Counter(A)

    duplicates = [key for key, val in counter.items() if val >= 2]
    A = [key for key in counter]

    A.sort()
    max_a = A[-1]
    multiples = set()
    ans = []

    for a in A:
        if a not in multiples:
            ans.append(a)
            for i in range(1, 10 ** 9):
                if a * i > max_a:
                    break
                multiples.add(a * i)

    print(len(set(ans) - set(duplicates)))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
ct = Counter(a)
st = set()
ans = 0
x = max(a)
for i in range(n):
    if a[i] in st:
        continue
    if ct[a[i]]>1:
        st.add(a[i])
    for j in range(2,x//a[i]+1):
        st.add(a[i]*j)
for i in range(n):
    if not a[i] in st:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().rstrip().split()]
a.sort()
ma=max(a)
dp=[0]*ma
for i in a:
  dp[i-1]+=1

l=[0]*ma
ans=0
for i in a:
  j=i
  if l[i-1]==0 and dp[i-1]==1:
    ans+=1
  while(j<=ma):
    l[j-1]+=1
    if j+i<=ma:
      j+=i
    else:
      break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.array(A)

A.sort()

d = {}

for a in A:
    d.setdefault(a,0)
    d[a] += 1

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

for a in A:
    if sieve[a] == False:
        continue
    if d[a] > 1:
        sieve[a] = False
    for i in range(a + a, A[-1] + 1, a):
        sieve[i] = False

print(sum(1 for a in A if sieve[a]))

Submission status: Accepted

Solution code:
from numba import njit


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


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

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

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

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

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

A = np.array(A)

A.sort()

d = {}

for a in A:
    d.setdefault(a,0)
    d[a] += 1



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

for a in A:
    if d[a] > 1:
        sieve[a] = False
    for i in range(a + a, A[-1] + 1, a):
        sieve[i] = False

print(sum(1 for a in A if sieve[a]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
l = max(A)+1
li = [0]*(l)
A.sort()

for a in A:
  if li[a] == 0:
    li[a] = 1
    for i in range(a*2, l, a):
      li[i] = 2
  elif li[a] == 1:
    li[a] = 2
print(li.count(1))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
b = [0] * (10 ** 6 + 1)
c = [False] * (10 ** 6 + 1)
for i in a:
    b[i] += 1
ans = 0
for i in range(1, 10 ** 6 + 1):
    if not b[i]:
        continue
    if b[i] == 1 and not c[i]:
        ans += 1
    for j in range(1, 10 ** 6 + 1):
        if i * j > 10 ** 6:
            break
        c[i * j] = True
print(ans)

Submission status: Accepted

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

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

m = 10**6+10
d = [False] * (m+1)
ans = 0
for i in range(n):
    same = (i > 0 and a[i] == a[i-1]) or (i < (n-1) and a[i] == a[i+1])
    x = a[i]
    if not d[x] and not same: ans += 1
    
    if (i > 0 and a[i] == a[i-1]): continue
    for j in range(x, m+1, x):
        d[j] = True
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

A.sort()
Sum = 0

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

for i in range(N):

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

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

Submission status: Accepted

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

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

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

print(len(ans))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split(' '))))
# print(A)
a_max = A[-1]
dp = [True]*(a_max+1)
ans = 0
for i in range(N-1):
    p = A[i]
    if dp[p] == True:
        # print(math.sqrt(p))
        for q in range(a_max//p+1):
            # print(p*q)
            dp[p*q] = False
        if A[i] != A[i+1]:
            ans += 1
if dp[A[-1]]:
    ans += 1
print(ans)

Submission status: Accepted

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

a.sort()

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

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

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

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

import itertools

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

A.sort()

# [それより小さい数の倍数として出てきたか,同じ数が出てきたか]
check = [[False,False] for i in range(10**6+1)]
ans = 0
for a in A:
    if check[a][1]:
        check[a][0] = True
    if check[a][0]:
        continue
    for j in range(2*a,10**6+1,a):
        check[j][0] = True
    check[a][1] = True
 
for a in A:
    if not check[a][0]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

c=Counter(a)

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

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

  return is_p

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

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

print(cnt)

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import collections

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

    return

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

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

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

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

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

ans = 0

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

Submission status: Accepted

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


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

a_li = set(a_li)

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

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

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

Submission status: Accepted

Solution code:
from numba import njit


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


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

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

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

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

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC170

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter


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

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

ans = 0

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

d = set()
answer = 0

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

print(answer)

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

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

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

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

Submission status: Accepted

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

M=1000050

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
from math import sqrt
from time import time


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

    np_a_keys = set(np_a.keys())

    div_list = set()
    key_max = max(np_a_keys)

    c = 0

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

    r = np_a_keys - div_list

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

    print(len(r))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math

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

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

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

Submission status: Accepted

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

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

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

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



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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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



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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from numba import njit

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

print count