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: Time Limit Exceeded

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

total = 0
for i in range(N):
    chk = -1
    for j in range(N):
        if i != j:
            if int(A[i]) % int(A[j]) == 0:
                chk = 1
                break
    else:
        continue

    if chk == 1:
        total += 1
print(N - total)

Submission status: Time Limit Exceeded

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

total = 0
for i in range(N):
    chk = -1
    for j in range(N):
        if i != j:
            if int(A[i]) % int(A[j]) == 0:
                chk = 1
                break
    if chk == 1:
        total += 1
print(N - total)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True]*(a[n-1]+1)
for val in set(a):
    temp=2
    while val*temp<=a[n-1]:
        dp[val*temp]=False
        temp+=1
ans = 0
for val in a:
    if dp[val] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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


def solve(N, A):
    A = sorted(A)
    dp = [True for i in range(N)]  # Trueのものは、割り切れない（カウント対象）

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

        elif A.count(a) > 1:  # 同じ値が複数入っていたら、その値はカウント対象外
            dp[i] = False
            continue

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

    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True]*(a[n-1]+1)
for val in a:
    temp=2
    while val*temp<=a[n-1]:
        dp[val*temp]=False
        temp+=1
ans = 0
for val in a:
    if dp[val] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
c=0
for i in range(n):
    if i>0 and a[i-1]==a[i]:
        continue
    for j in range(n):
        if i==j:
            continue
        else:
            if a[j]>a[i]:
                c+=1
                break
            if a[i]%a[j]==0:
                break
    else:
        c+=1
print(c)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
c=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        else:
            if a[j]>a[i]:
                c+=1
                break
            if a[i]%a[j]==0:
                break
    else:
        c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()
dp = [True] * (10 ** 6 + 1)  # 自分以外約数ないならTrue
visited = [False] * (10 ** 6 + 1)
for a in A:
    if visited[a]:
        dp[a] = False
        continue
    visited[a] = True
    i = 2
    while a * i <= 10 ** 6:
        dp[a * i] = False
        i += 1
ans = 0
for a in A:
    ans += dp[a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
c=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        else:
            if a[j]>a[i]:
                continue
            if a[i]%a[j]==0:
                break
    else:
        c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
dp = [True] * (10 ** 6 + 1)  # 自分以外約数ないならTrue
visited = [False] * (10 ** 6 + 1)
for a in A:
    if visited[a]:
        dp[a] = False
        continue
    visited[a] = True
    i = 2
    while a * i <= 10 ** 6:
        dp[a * i] = False
        i += 1
ans = 0
for a in A:
    ans += dp[a]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
c=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        else:
            if a[i]%a[j]==0:
                break
    else:
        c+=1
print(c)

Submission status: Time Limit Exceeded

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

dp = [0]*(10**6)
count = [0]*(10**6)
for i in a:
  count[i-1] += 1
  m = 2
  while i*m <= 10**6:
    dp[i*m-1] = 1
    m += 1
ans = 0
for i in a:
  if count[i-1] == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

Submission status: Time Limit Exceeded

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

dp = [0]*(10**6)

for i in a:
  m = 2
  while i*m <= 10**6:
    dp[i*m-1] = 1
    m += 1
ans = 0
for i in a:
  if a.count(i) == 1 and dp[i-1] == 0:
    ans +=1
    
print(ans)

Submission status: Time Limit Exceeded

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

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

if a[0] == a[-1]: # n=1 やサンプル２のような時
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

if a[0] == 1: #１だけは素因数分解するときにバグるので別で処理
  if a[0] == a[1]:
    print(0)
  else:
    print(1)
  exit()
  
def divisorize(fct): # 約数のリストつくるやつ
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def factorize(n): #素因数分解
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
 
 
def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set()
  fct = factorize(i)
  for div in divisorize(fct): # 約数の集合を作る
      c.add(num(div))

# 積集合をとり、それが空でかつ同じ数字が並んでない時に答えを加算
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i) #今まで見た数の集合を更新

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input=sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  B=sorted(A,reverse=True)
  count=0
  for i in range(1,N,1):
    if B[i-1]!=B[i]:
      flag=False
      for j in range(N-1,i,-1):
        if B[i]%B[j]==0:
          flag=True
          break
        else:
          continue
      if flag==False:
        count+=1
      else:
        continue
    else:
      continue
  flag=False
  for j in range(N-1,0,-1):
    if B[0]%B[j]==0:
      flag=True
      break
    else:
      continue
  if flag==False:
    count+=1
  print(count)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

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

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

for i in a:
	for j in range(i*2,len(ans),i):
		ans[j]+=2

print(ans.count(1))

Submission status: Time Limit Exceeded

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

lst = sorted(lst)
bol = [True]*n
s=0
for i in range(n-1):
  if bol[i] == True:
    if lst[i] != lst[i+1]:
      s += 1
    
    for j in range(i+1,n):
      if bol[j] == True and lst[j] % lst[i] == 0:
        bol[j] = False

if bol[n-1] == True:
  s += 1
  
print(s)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


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

    ans = 0
    l = [0] * (max(A) + 1)

    for i in range(N):
        for j in range(A[i], max(A) + 1, A[i]):
            l[j] += 1

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))

for x in s:
    t = x * 2
    #print(t)
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    #print(x)
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
s = list(set(a))

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

for x in s:
    t = x
    while t <= 10**6:
        P[t] += 1
        t += x

ans = 0

for x in a:
    #print(P[x])
    if P[x] == 1 and c[x] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


def solve(N, A):
    A = sorted(A)
    dp = [True for i in range(N)] # Trueのものは、割り切れない（カウント対象）

    for i, a in enumerate(A):
        if dp[i] == False:
            continue
        elif A.count(a) > 1: # 同じ値が複数入っていたら、その値はカウント対象外
            dp[i] = False
        for j, target in enumerate(A[i + 1:]): # 探索対象の倍数を、リストから除外していく
            if target % a == 0:
                dp[i+j+1] = False
    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def solve(N, A):
    A = sorted(A)
    dp = [True for i in range(N)] # Trueのものは、割り切れない（カウント対象）

    for i, a in enumerate(A):
        if A.count(a) > 1: # 同じ値が複数入っていたら、その値はカウント対象外
            dp[i] = False
        for j, target in enumerate(A[i + 1:]): # 探索対象の倍数を、リストから除外していく
            if target % a == 0:
                dp[i+j+1] = False
    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
import decimal


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

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

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

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

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

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


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

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

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

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

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

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


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


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


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

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

    print(sum(memo))


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = list(map(int, input().split()))
count = 0
for i, ai in enumerate(a):
    for j, aj in enumerate(a):
        if i != j and ai % aj == 0:
            break
    else:
        count = count + 1

print(count)

Submission status: Time Limit Exceeded

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

A = sorted(A)

seed = []

while A:    
    wareta = set()
    warenai = []

    q = A.pop(0)
    for a in A:
        if a % q == 0:
            wareta.add(a)
        else:
            warenai.append(a)

    if q not in wareta:
        seed.append(q) 

    A = warenai[:]

print(len(seed))

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import floor,ceil,sqrt
# import bisect
# from collections import deque

# from types import GeneratorType
# def bootstrap(func, stack=[]):
#     def wrapped_function(*args, **kwargs):
#         if stack:
#             return func(*args, **kwargs)
#         else:
#             call = func(*args, **kwargs)
#             while True:
#                 if type(call) is GeneratorType:
#                     stack.append(call)
#                     call = next(call)
#                 else:
#                     stack.pop()
#                     if not stack:
#                         break
#                     call = stack[-1].send(call)
#             return call
#     return wrapped_function

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7


n = int(ri())
a  = Ri()
dic = {}
for i in a:
    dic[i] = dic.get(i,0)+1

ans = 0
a  = [i for i in set(a)]
flag = [False]*len(a)
a.sort()
for i in range(len(a)):
    if not flag[i]:
        ans+=1
        for j in range(i+1,len(a)):
            if a[j]%a[i] == 0:
                flag[j] =True

for i in range(len(a)):
    if flag[i] == False :
        if  dic[a[i]] > 1:
            ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def divisors(n):
    S, T = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            S.append(i)
            T.append(n // i)
        i += 1
    T.reverse()
    return S + T if S[-1] != T[0] else S + T[1:]

from collections import Counter
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    ans = 0
    for i in range(n):
        a = A[i]
        if C[a] >= 2:
            continue
        flag = True
        for d in divisors(a):
            if d == a:
                continue
            if d in C:
                flag = False
        ans += flag

    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    if B[i]:
        for j in range(i, N):
            if B[j] and j != i:
                if A[j] == A[i]:
                    B[i] = False
                    B[j] = False
                elif A[j] % A[i] == 0:
                    B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

b = [True for i in range(n)]

for i, j in enumerate(a):
    if i < n-1 and b[i]:
        for k in range(i+1, n):
            if b[k] and a[k] % j == 0:
                b[k] = False
        if a[i] == a[i+1]:
            b[i] = False

print(b.count(True))

Submission status: Time Limit Exceeded

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

a.sort()
l = a[-1]
dp = [ 1 if i in a else 0 for i in range(l+1)]

for i in range(n):
    tmp = a[i]
    if dp[tmp] == 0:
        continue
    g = l//tmp
    for k in range(2,g+1):
        dp[tmp*k] = 0

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

print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from collections import Counter
from math import sqrt

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
a_s.sort()
_max = max(a_s)
ct = Counter(a_s)
cnt = 0
ls = [0] * (10**6+1)
for a in a_s:
    if ls[a] == 1:
        cnt += 1
        continue
    elif ct[a] > 1:
        cnt += 1
    for i in range(a, _max+1):
        if ls[i] == 1:
            continue
        if i % a == 0:
            ls[i] = 1

print(n - cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


n = int(input())
A = list(map(int, input().split()))
A.sort()
undivisible = set(range(1, 10**6+1))


def update(num):
    for div in list(undivisible):
        if div % num == 0:
            undivisible.discard(div)


counter = Counter(A)
ans = 0
for a, count in counter.items():
    if count == 1 and a in undivisible:
        ans += 1
        
    update(a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from collections import Counter
import numpy as np

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
a_s.sort()
ct = Counter(a_s)
cnt = 0
res = np.zeros(10**6+1)
for a in a_s:
    if res[a] == 1:
        cnt += 1
    elif ct[a] > 1:
        cnt += 1
    res[::a] = 1

print(n - cnt)

Submission status: Time Limit Exceeded

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

amax = max(a)+10
dp = [1] * (amax)

a.sort()

for ai in a:
    if dp[ai] == 1:
        for j in range(2*ai, amax, ai):
            dp[j] = 0
cnt = 0

dup = [x for x in set(a) if a.count(x) > 1]
for ai in a:
    if dp[ai] and not ai in dup:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

a.sort()
l = a[-1]
dp = [ 1 if i in a else 0 for i in range(l+1)]

for i in range(n):
    tmp = a[i]
    g = l//tmp
    for k in range(2,g+1):
        dp[tmp*k] = 0

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

print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from collections import Counter

n = int(input())
a_s = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_s)
a_s.sort()
_max = max(a_s)
que = [(i, i) for i in a_s]
cur = 0
res = set()
while cur <= _max:
    cur, base = heapq.heappop(que)
    if cur != base:
        if cur in a_s:
            res.add(cur)
    else:
        if ct[cur] > 1:
            res.add(cur)
    heapq.heappush(que, (cur + base, base))

print(len(set(a_s)) - len(res))

Submission status: Time Limit Exceeded

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

amax = max(a)+10
dp = [1] * (amax) 

a.sort()

for i in range(len(a)):
    if dp[a[i]] :
        for j in range(2*a[i],amax,a[i]):
            dp[j] = 0
cnt = 0

dup = [x for x in set(a) if a.count(x) > 1]
for ai in a:
    if dp[ai] and not ai in dup:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))

count = 0
for i in range(n):
    is_divisible = False
    for j in range(n):
        divisible_num = []
        if a[i] % a[j] == 0 and i != j:
            divisible_num.append(a[j])
            is_divisible = True
        if len(divisible_num) >= 1:
            continue
    if is_divisible:
        continue
    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = list(map(int, input().split()))
ban = set()
D = set()
for a in A:
  if a in D:
    ban.add(a)
  else:
    D.add(a)
D = deque(sorted(list(D)))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Time Limit Exceeded

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

amax = max(a)+10
dp = [1] * (amax) 

a.sort()

for i in range(len(a)):
    if dp[a[i]] :
        for j in range(2*a[i],amax,a[i]):
            dp[j] = 0
        if a[i] in a[i+1:]:
            dp[a[i]] = 0
cnt = 0

for ai in a:
    if dp[ai]:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import Counter
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = list(map(int, input().split()))
d = Counter()
d.update(A)
ban = {k for k, i in d.items() if i >= 2}
D = deque(sorted(list(set(A))))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
  a = A[i]
  X = list(A)
  X.pop(i)
  k = 1
  for j in range(n-1):
    if a % X[j] == 0:
      k = 0
      break
  ans += k
  
print(ans)

Submission status: Time Limit Exceeded

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

amax = 10**6 + 1
dp = [1] * (amax) 

a.sort()

for i in range(len(a)):
    if dp[a[i]] :
        for j in range(2*a[i],amax,a[i]):
            dp[j] = 0
        if a[i] in a[i+1:]:
            dp[a[i]] = 0
cnt = 0

for ai in a:
    if dp[ai]:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import Counter
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = list(map(int, input().split()))
ban = {k for k, i in Counter(A).items() if i >= 2}
D = deque(sorted(list(set(A))))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
  a = A[i]
  X = list(A)
  X.pop(i)
  if all(a % X[j] != 0 for j in range(len(X))):
    ans += 1
  else:
    pass
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    if B[i]:
        for j in range(i, N):
            if B[j] and j != i:
                if A[j] == A[i]:
                    B[i] = False
                    B[j] = False
                elif A[j] % A[i] == 0:
                    B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
collect = collections.Counter(A)
A = sorted(list(set(A)))
count = 0

dp = [True] * max(A)

for a in A:
    for i in range(a, max(A)+1, a):
        if i != a:
            dp[i-1] = False

for a in A:
    if dp[a-1] and collect[a] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted((map(int,input().split())))
B = [True]*N

for i in range(N):
    for j in range(i,N):
        if B[j] and j != i:
            if A[j]==A[i]:
                B[i] = False
                B[j] = False
            elif A[j]%A[i]==0:
                B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

A = sorted(A)

seed = []

while A:    
    wareta = []
    warenai = []

    q = A.pop(0)
    for a in A:
        if a % q == 0:
            wareta.append(a)
        else:
            warenai.append(a)

    if q not in wareta:
        seed.append(q) 

    A = warenai[:]

print(len(seed))