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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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): # root
		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): # much time
		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()} # 1~n
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): #j:aの個数
			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]
	#data = [0,0,0]
	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]
	#ans = data[:]
	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)

Submission status: Accepted

Solution code:
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): # root
		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): # much time
		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()} # 1~n
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): #j:aの個数
			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]
	#data = [0,0,0]
	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]
	#ans = data[:]
	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)

Submission status: Accepted

Solution code:
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 LF(): return [float(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

  # print(M[:100])
  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

'''

'''

n = int(input())
a = sorted(map(int, input().split()))
largest = a[-1]
#largest = arr[-1]
div = [1] * (largest+1)
count = 0
arr = []
# remove duplicates
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)

Submission status: Accepted

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

'''

'''

n = int(input())
a = sorted(map(int, input().split()))
largest = a[-1]
#largest = arr[-1]
div = [1] * (largest+1)
count = 0
arr = []
# remove duplicates
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)

Submission status: Accepted

Solution code:
# D - Not Divisible
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

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

m = 1000005

l = [0] * m


for a in a_list:
    # 0じゃなくなっていれば割り切れる値だということ
    if l[a] != 0:
        # 2以上なら割り切れることに変わりはないので2で固定
        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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#D
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
mx = a[-1]
dp = ["#"]*(mx+1)
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import numpy as np

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

As.sort()

# indexを数値と紐づけるために+1増やした数にする
check = np.zeros(10**6+1)

answer = 0

# 与えられた数列の小さいものから順にループ
for i in range(length):
    if check[As[i]] == 0:
        # 与えられた数値の倍数すべてに1を立てる
        # checkは0始まりのため、0と倍数要素に1が立つ
        check[::As[i]] = 1
        
        # checkリストが0の状態で数列の最後であればanswerへの加算は確定
        # また、同じ数字が複数ある場合はカウントさせない
        if  i == (length - 1) or  As[i] != As[i + 1]:
                answer = answer + 1

print(answer)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

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
    #print(nums)
    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:
                #print(cnt)
                check[cnt] = True
                cnt += nums[i]
        #print(ans)
    print(ans)

    
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:

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)


# fast-io region

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

Submission status: Accepted

Solution code:

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)


# fast-io region

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import Counter

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

div = set(A)
cnt = Counter(A)
M = max(A)
ng = [False] * (M + 1)
for a in A:
    n = a * 2
    while n <= M:
        ng[n] = True
        n += a
ans = 0
for a in A:
    if cnt[a] >= 2:
        continue
    if ng[a]:
        continue
    ans += 1

print(ans)

Submission status: Accepted

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

F=[0]*(M+1)

for i in range(N):
    a=A[i]
    b=a

    if F[b]<=1:
        while b<=M:
            F[b]+=1
            b+=a
    

T=0
for i in range(N):
    if F[A[i]]==1:
        T+=1

print(T)

Submission status: Accepted

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

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

bai = [False]*(10**6+1)
cnt = 0
A = list(set(A))
A.sort()
for a in A:
    if bai[a]:
        continue

    if num[a] == 1:
        cnt += 1

    for i in range(a, 10**6+1, a):
        bai[i] = True
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np


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

    max_dp = max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")


    for a in A:
        if dp[a] >= 2:
            continue
        dp[np.arange(a, max_dp, a)] += 2
        dp[a] -= 1

    print(np.sum(dp == 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline


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

    max_dp = max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")


    for a in A:
        if dp[a] >= 2:
            continue
        dp[np.arange(a, max_dp, a)] += 2
        dp[a] -= 1

    print(np.sum(dp == 1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]
B = [0] * m
for a in A:
  B[a - 1] += 1
  if B[a - 1] == 1:
    for j in range(a * 2, m + 1, a):
      B[j - 1] = 2
print(B.count(1))