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=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[True]*M
dep=[x for x in set(A) if A.count(x) >= 2]
for i in A:
    if cnt[i]==False:
        continue
    for j in range(2*i,M,i):
        #print(i,M,j)
        cnt[j]=False
ans=0
for i in set(A):
    if cnt[i] and i not in dep:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[True]*M
dep=[x for x in set(A) if A.count(x) >= 2]
for i in A:
    if cnt[i]==False:
        continue
    for j in range(2*i,M,i):
        #print(i,M,j)
        cnt[j]=False
ans=0
for i in A:
    if cnt[i] and i not in dep:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, ans = int(input()), 0
A = list(map(int, input().split()))
for i in A:
    count = 0
    for j in A:
        if not i%j: count+=1
    if count==1: ans+=count
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)


for i in range(n):
  #print(sort[i], l)
  if l[i:] == [False]*len(sort[i:]):
    break
  if l[i] == False:
    continue
  
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False

print(len([x for x in l if x]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)

for i in range(n):
  #print(sort[i], l)
  if l[i:] == [False]*len(sort[i:]):
    break
  if sort[i] == False:
    continue

  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False

print(len([x for x in l if x]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)

for i in range(n):
  #print(sort[i], l)
  if sort[i] == False:
    continue
  if l[i:] == [False]*len(sort[i:]):
    break
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False

print(len([x for x in l if x]))

Submission status: Time Limit Exceeded

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

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

ans = 0
appeared = set()
lib = Factorization()

for k, v in sorted(dic.items(), key=lambda x:x[0]):
	if v == 1:
		divisors = lib.get_divisors(k)
		is_exist = False
		
		for d in divisors:
			if d in appeared:
				is_exist = True
				break

		if is_exist == False:
			ans += 1

	appeared.add(k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
MAX=10**6+1
L = [0]*(10**6+1)
used = set()
first = True
for a in A:
    if L[a] ==2:
        continue
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] += 1
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    for i in range(0,MAX,a):
        L[i] += 1
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
MAX=10**6+1
L = [0]*(10**6+1)
used = set()
first = True
for a in A:
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] += 1
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    for i in range(0,MAX,a):
        L[i] += 1
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    tmp = [0] * (max(a) + 1)
    # set_a = list(set(a))
    # set_a.sort()
    a.sort()
    for aa in a:
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    tmp = [0] * (max(a) + 1)
    set_a = list(set(a))
    set_a.sort()

    for aa in set_a:
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    tmp = [0] * (max(a) + 1)
    set_a = list(set(a))
    set_a.sort()

    for i, aa in enumerate(set_a):
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    import collections
    cnt = collections.Counter(a)
    tmp = [0] * (max(a) + 1)
    set_a = list(set(a))
    set_a.sort()

    for i, aa in enumerate(set_a):
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
L = np.zeros((10**6+10,))
used = set()
first = True
for a in A:
    if a in used and first:
        first = False
        L[::a] += 1
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * M
ans = 0
for i in A:
    for j in range(0, M, i):
        cnt[j] += 1
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = 5
ARR = [24, 11, 8, 3, 16]


N = 4
ARR = [5, 5, 5, 5]


N = 10
ARR = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

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

def calculate(n, arr):

    prr = [0 for i in range(2000005)]

    for i in range(n):
        start = arr[i]
        #
        # if prr[start] > 0:
        #     prr[start] = 2
        #     continue

        for j in range(start, 2000005, start):
            prr[j] = prr[j] + 1


    result = 0
    for i in range(n):
        start = arr[i]
        if prr[start] == 1:
            result += 1


    print(result)

calculate(N, ARR)

Submission status: Time Limit Exceeded

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

def find_next_true(ind, bools, N):
    for i in range(ind+1, N):
        if bools[i]:
            return i
    return N

def Main(N, A):
    A.sort()
    bools = [True]*N
    i = 0
    j = 0
    while i < N:
        j = find_next_true(i, bools, N)
        while j < N:
            div, mod = divmod(A[j], A[i])
            if mod == 0:
                bools[j] = False
                if div == 1:
                    bools[i] = False
            j = find_next_true(j, bools, N)
        i = find_next_true(i, bools, N)
    return bools.count(True)

print(Main(N, A))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
a = sorted(a)
w = 0
while True:
    h = 1
    cn = 0
    while True:
        if w + h == len(a):
            '''
            print(a)
            '''
            if cn == 1:
                del a[w]
                w -= 1
            break
        if a[w] == a[w+h]:
            cn =1
        if a[w+h] % a[w] == 0:
            '''
            print(h)
            '''
            del a[w+h]
        else:
            '''
            print(a[w+h], h, w, a)
            '''
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
*a, = map(int, input().split())
dp = [False] * n

for i in range(n):
    for j in range(n):
        if (i != j) and (a[i] % a[j] == 0):
            break
    else:
        dp[i] = True

print(dp.count(True))

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
a= list(map(int,input().split()))
a= [i for i in a if a.count(i)==1]
a.sort()
b=a.copy()
for i in range(1,len(a)):
    for j in range(i):
        if a[i]%a[j]== 0:
            b.remove(a[i])
            break
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

M = max(ok)

for i in ok:
    for j in range(2,M+1):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

M = max(ok)

for i in ok:
    for j in range(2,M+1):
        mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    M = 1000005
    dp = [0]*(max(a)+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],max(a)+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [0]*(max(a)+1)
    for i in range(n):
        if dp[a[i]] != 0:
            dp[a[i]] = 2
            continue
        for j in range(a[i],max(a)+1,a[i]):
            dp[j]+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [0]*(max(a)+1)
    for i in range(n):
        if dp[a[i]]>1:
            continue
        dp[a[i]]+=1
        j = 2
        while True:
            b = a[i]*j
            if b>max(a):
                break
            dp[b]+=1
            j+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = sorted(list(map(int,input().split())))
    dp = [0]*(max(a)+1)
    for i in range(n):
        j = 2
        dp[a[i]]+=1
        while True:
            b = a[i]*j
            if b>max(a):
                break
            dp[b]+=1
            j+=1
    cnt = 0
    for i in range(n):
        if dp[a[i]] == 1:
            cnt+=1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
from functools import lru_cache
import copy

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


# a.sort()

if 1 in a:
  # if a[0] == 1:
  # if len(a) > 1 and a[1] == 1:
  #   print(0)
  # else:
  #   print(1)

  # if collections.Counter(a)[1]==1:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)

  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

a = [k for k, v in collections.Counter(a).items() if v == 1]


def func(f, i):
  global p, valid
  dprint('f', '=', f)

  for k, v in f.items():
    if v == 0:
      continue
    f_ = copy.deepcopy(f)
    f_[k] = v - 1
    func(f_, i + 1)

  com = []
  for k, v in f.items():
    com += [k] * v
  com = tuple(com)
  dprint('com', '=', com)
  if com == ():
    return
  if com in p and i != 0:
    dprint('vF')
    valid = False


ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  func(dict(collections.Counter(f)), 0)
  # for r in range(1, len(f)+1):
  #   dprint('r', '=', r)
  #   for com in itertools.combinations(f, r=r):
  #     dprint(com)
  #     if com == f:
  #       continue
  #     # if p[bisect.bisect_left(p, com)] == com:
  #     if com in p:
  #       valid = False
  #       break
  # if not valid:
  #   break
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

# TLE

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	Acnt = Counter(A)
	if 1 in Acnt:
		print(1 if Acnt[1] == 1 else 0)
		return
	ans = 0
	for i, num in enumerate(A):
		div = 2
		flag = True
		if Acnt[num] > 1:
			continue
		while div*div <= num:
			if num % div == 0:
				other = num//div
				if div in Acnt or other in Acnt:
					flag = False
					break
			div += 1
		if flag:
			ans += 1
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	Aset = set(A)
	Acnt = Counter(A)
	if 1 in Aset:
		print(1 if Acnt[1] == 1 else 0)
		return
	ans = 0
	for i, num in enumerate(A):
		div = 2
		flag = True
		if Acnt[num] > 1:
			continue
		while div*div <= num:
			if num % div == 0:
				other = num//div
				if div in Aset or other in Aset:
					flag = False
					break
			div += 1
		if flag:
			ans += 1
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math

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

a.sort()

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

is_prime[0] = False

for i in set(a):
    for j in range(2 * i, max(a)+1, i):
        is_prime[j] = False

result = 0
c = Counter(a)

for e in set(a):
        if is_prime[e] and c[e] == 1:
    #        print('e = {}'.format(e))
             result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in arr:
    if tmp[i] >= 2:
        continue
    flg = True
    for k in range(1,int(i**0.5)+1):
        if i % k == 0:
            if tmp[k] != 0 and i != k:
                flg = False
                break
            if k != i // k:
                if tmp[i // k] != 0 and i // k != i:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    target = arr[i]
    if tmp[target] >= 2:
        continue
    flg = True
    for k in range(1,int(target**0.5)+1):
        if target % k == 0:
            if tmp[k] != 0 and target != k:
                flg = False
                break
            if k != target // k:
                if tmp[target // k] != 0 and target // k != target:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    if tmp[arr[i]] >= 2:
        continue
    flg = True
    for k in range(1,int(arr[i]**0.5)+1):
        if arr[i] % k == 0:
            if tmp[k] != 0 and arr[i] != k:
                flg = False
                break
            if k != arr[i] // k:
                if tmp[arr[i] // k] != 0 and arr[i] // k != arr[i]:
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

    A_set = set(A)
    A_dict = Counter(A)

    for key, count in A_dict.items():
        if count > 1:
            A_set.discard(key)

        k = key * 2
        while k <= max(A):
            A_set.discard(k)
            k += key

    print(len(A_set))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(N):
    flg = True
    for k in make_divisors(arr[i]):
        if k == arr[i]:
            if tmp[k] >= 2:
                flg = False
                break
        elif tmp[k] != 0:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors
N = int(input())
arr = list(map(int, input().split()))
tmp = [0]*(max(arr)+1)
for i in arr:
    tmp[i] += 1
ans = 0
for i in range(len(arr)):
    flg = True
    for k in make_divisors(arr[i]):
        if k == arr[i]:
            if tmp[k] >= 2:
                flg = False
                break
        elif tmp[k] != 0:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = max(a)
che,re = [1 for i in range(b)],[]
for i in a:
    if i in re:
        che[i-1] = 0
    else:
        re.append(i)
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
ans = 0
for i in re:
    if che[i-1] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

D = [0]*(max(A)+1)
for i in A:
    # ダブってる値は2以上に
    D[i] += 1

U = []
for i in range(max(A)+1):
    # ダブってる値は2以上に
    if D[i] == 1:
        U.append(i)

A = list(set(A))

T = [0]*(max(A)+1)
for i in A:
    # iの2以上の倍数の値は1に
    for j in range(2*i, max(A)+1, i):
        T[j] = 1

# Tが0かつDが1の数を数える
ans = 0
for i in U:
    if T[i] == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp
n = int(input())
a = list(map(int, input().split()))
han = list(map(lambda x:x*(-1), a))
hp.heapify(han)
b = hp.heappop(han)*(-1)
che,re = [1 for i in range(b)],[]
for i in a:
    if i in re:
        che[i-1] = 0
    else:
        re.append(i)
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
ans = 0
for i in re:
    if che[i-1] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

T = [0]*(max(A)+1)
D = [0]*(max(A)+1)
for i in A:
    # iの2以上の倍数の値は1に
    for j in range(2*i, max(A)+1, i):
        T[j] = 1
    # ダブってる値は2以上に
    D[i] += 1

# Tが0かつDが1の数を数える
ans = 0
for i in A:
    if T[i] == 0 and D[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

T = [0]*(max(A)+1)
D = [0]*(max(A)+1)
for i in A:
    # iの2以上の倍数の値は1に
    for j in range(2*i, max(A)+1, i):
        T[j] += 1
    # ダブってる値は2以上に
    D[i] += 1

# Tが0かつDが1の数を数える
ans = 0
for i in A:
    if T[i] == 0 and D[i] == 1:
        ans += 1

print(ans)