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:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

if __name__ == "__main__":
    n, *a = map(int, open(0).read().split())
    b, c = set(a), Counter(a)
    P = Osa_k(10**6)
    cnt = 0
    for i in b:
        if c[i] > 1:continue
        for d in P.div(i):
            if d != i and d in b:break
        else:cnt += 1
    print(1 if n == 1 else cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

if __name__ == "__main__":
    n, *a = map(int, open(0).read().split())
    b, c = set(a), Counter(a)
    P = Osa_k(10**6)
    cnt = 0
    for i in b:
        for d in P.div(i):
            if d != i and d in b:break
        else:cnt += c[i] == 1
    print(1 if n == 1 else cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from operator  import mul
from functools import reduce
from collections import Counter
class Osa_k:
    def __init__(self, n_max):
        self.n_max = n_max
        self.min_factor = min_factor = list(range(n_max + 1))
        min_factor[2::2] = [2] * (n_max // 2)
        min_factor[3::6] = [3] * ((n_max + 3) // 6)
        for i in range(5, int(n_max ** .5) + 1, 2):
            if min_factor[i] == i:
                for j in range(i*i, n_max + 1, i):
                    if min_factor[j] == j:
                        min_factor[j] = i

    def __call__(self, n):
        if not 1 <= n <= self.n_max: raise ValueError("Invaild Value!")
        min_factor = self.min_factor
        n_twoes = (n & -n).bit_length() - 1
        res = [2] * n_twoes
        n >>= n_twoes
        resappend = res.append
        while n > 1:
            p = min_factor[n]
            resappend(p)
            n //= p
        return res

    def d(self, n):
        min_factor = self.min_factor
        t = []
        tappend = t.append
        while n > 1:
            if t and t[-1][0] == min_factor[n]:
                t[-1][1] += 1
            else:
                tappend([min_factor[n], 1])
            n //= min_factor[n]
        res = 1
        for _, i in t:
            res *= i + 1
        return res
    
    def div(self, n):
        factors = self.__call__(n)
        res = {1, n}
        for i in range(1, len(factors)):
            for j in combinations(factors, i):
                res |= {reduce(mul, j)}
        return res

n, *a = map(int, open(0).read().split())
b = set(a)
P = Osa_k(max(b))
cnt = 0
for i, j in Counter(a).items():
    cnt += j == 1 and all(d not in b for d in P.div(i) if d != i)
print(1 if n == 1 else cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

x = tuple(map(int, input().split()))


def hantei(length, list_1):
    count = 0
    for i in range(length):
        break_hantei = 0
        for j in range(length):
            if i != j and list_1[i] % list_1[j] == 0:
                break_hantei = 1
                break
        #if i != j:
        if break_hantei == 0:
            #print((list_1[i],list_1[j]))
            count += 1
    return count

#print(N)
#print(x)
print(hantei(N,x))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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


def hantei(length, list_1):
    count = 0
    for i in range(length):
        break_hantei = 0
        for j in range(length):
            if i != j and list_1[i] % list_1[j] == 0:
                break_hantei = 1
                break
        #if i != j:
        if break_hantei == 0:
            #print((list_1[i],list_1[j]))
            count += 1
    return count

print(hantei(N,x))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = list(map(int, input().split()))
count=N
for i in range(0,N):
    for j in range(0,N):
        if i!=j and A[i]%A[j]==0:
            count=count-1
            break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
double_count = [0]*(10**6+1)
dp = [False]*(max(A)+1)
for i in range(len(A)):
    cur = A[i]
    temp = 2
    double_count[cur] += 1
    if double_count[cur] <= 1:
        while cur*temp <= max(A):
            dp[cur*temp] = True
            temp += 1
for i in range(n):
    if double_count[A[i]] <= 1 and dp[A[i]] == False:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
double_count = [0]*(10**6+1)
dp = [False]*(max(A)+1)
for i in range(n):
    cur = A[i]
    temp = 2
    double_count[cur] += 1
    while cur*temp <= max(A):
        dp[cur*temp] = True
        temp += 1
for i in range(n):
    if double_count[A[i]] <= 1 and dp[A[i]] == False:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
from numba import jit

@jit
def solve():
    m = a[-1]+1
    ava = [0]*m
    for rep in a:
        ava[rep] += 1
        if ava[rep]==1:
            for item in range(2*rep,m,rep):
                ava[item] += 2

    print(ava.count(1))
    return

if __name__=='__main__':
    n = I()
    a = list(IL())
    a.sort()
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
dp = [0]*(10**6+1)
for i in range(len(A)):
    dp[A[i]] += 1
def p_factor(x):
    L = []
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            L.append(i)
            if x//i != x:
                if x//i != i:
                    L.append(x//i)
    return L
ans = 0
for i in range(len(A)):
    if dp[A[i]] > 1:
        ans += 1
    else:
        if A[i] != 1:
            T = p_factor(A[i])
            for j in range(len(T)):
                if dp[T[j]] >= 1:
                    ans += 1
                    break
        else:
            None
print(len(A)-ans)

Submission status: Time Limit Exceeded

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

max_A = max(A_list)
res = []
for i, a1 in enumerate(A_list):
    root_a1_int = int(a1 ** 0.5)
    can_div = False
    for ii, a2 in enumerate(A_list[:i+2]):
        if ii != i:
            # if root_a1_int > a2:
            if a1%a2 == 0:
                can_div = True
                break
    # print(a1, can_div)
    res.append(can_div)
print(N - sum(res))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())))
B=[0]*(1+max(A))
for i in A:
    B[i]+=1
    if B[i]==1:
        for j in range(2*i,max(A)+1,i):
            B[j]+=1
    else:
        continue
ans=0
for i in A:
  if B[i]==1: ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

nums.sort()

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

ans_list = []
temp = 0

for i in range(n):
    valid = True
    for div in ans_list:
        if nums[i] % div == 0:
            # 割り切れた
            valid = False
            break
        # if nums[i] < ans_list[j] * 2:
        #     break
    if valid:
        ans_list.append(nums[i])
        # ここで同じ数が2回以上出現する場合、 ans_listには入れるが（割る数のリストなので）最終的な個数からは除外しなければいけない
        if i < n-1 and nums[i] == nums[i+1]:
            temp += 1

    
ans = len(ans_list) - temp

print(ans)
# print(ans_list)

Submission status: Time Limit Exceeded

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

    a.sort()
    dic = {}
    zz = [False] * n
    for i in range(n):
        ai_v = dic.setdefault(a[i], 0)
        dic[a[i]] = ai_v + 1

    cnt = 0
    for i in range(n):
        ai = a[i]
        # 重複は無視
        if dic[ai] > 1:
            continue
        if i == 0:
            cnt += 1
            zz[0] = True
            continue

        divisible = False
        neglect_cnt = 0
        for j in range(i):
            if neglect_cnt > 0:
                neglect_cnt -= 1
                continue
            aj = a[j]
            ajcnt = dic[aj]
            if ajcnt > 1:
                # 重複分を無視
                neglect_cnt = ajcnt - 1
            elif not zz[j]:
                # 重複していない、かつ既に別の数値で除算可なら無視
                continue

            if ai < aj * 2:
                break
            if ai % aj == 0:
                divisible = True
                break
        if not divisible:
            zz[i] = True
            cnt += 1

    print(cnt)


main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())), reverse=1)
p=0

while A:
    a=A.pop()
    if A.count(a)==0:
    	p+=1
    A=[i for i in A if i%a!=0]
    #print(A)
print(p)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
m = arr[-1]
tf = [True] * (m+1)
cnt = 0
        
for i in range(n):
  ai = arr[i]
  if tf[ai] == True:
    cnt += 1
    for j in range(ai, m+1, ai):
      tf[j] = False
    if ai in arr[i+1:]:
      cnt -= 1
    

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
arr = [0]*(max(a)+1)

for i in a:
  arr[i]+=1
  tmp = i
  if arr[i]<=1:
      while (tmp+i)<=max(a):
        tmp += i
        if arr[tmp] !=0:
          arr[tmp] =2
        else:
          arr[tmp] +=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
arr = [0]*(max(a)+1)

for i in a:
  arr[i]+=1
  tmp = i
  while (tmp+i)<=max(a):
    tmp += i
    if arr[tmp] !=0:
      arr[tmp] =2
    else:
      arr[tmp] +=1

cnt = 0
for i in a:
  if arr[i] ==1:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
maximum = arr[-1]
tf = [True] * (maximum+1)
cnt = 0
        
for i in range(n):
  ai = arr[i]
  if tf[ai] == True:
    cnt += 1
    for j in range(maximum//ai):
      tf[(j+1)*ai] = False
    if ai in arr[i+1:]:
      cnt -= 1
    

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
count = [0]*(10 ** 6 + 1)
dp = [False] * (10 ** 6 + 1)

for a in A:
  count[a] += 1

ans = 0
for a in A:
  if dp[a]:
    continue
  if not dp[a] and count[a] == 1:
    ans += 1
  for j in range(2, 10 ** 6 + 1):
    if j * a >= 10 ** 6 + 1:
      break
    dp[j * a] = True

print(ans)

Submission status: Time Limit Exceeded

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

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

for e in A:
  if not dp[e]:
    continue
  if A.count(e) > 1:
    dp[e] = False
  j = 2
  while j * e <= max_A:
    dp[j * e] = False
    j += 1

ans = sum([dp[e] for e in A])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
cnt = 0
        
while len(arr):
  i = arr[0]
  tmp = []
  original = True
  for j in arr[1:]:
    if i == j:
      original = False
    if j % i != 0:
      tmp += [j]
  if original:
    cnt += 1
  arr = tmp
    

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
cnt = 0
        
while len(arr):
  i = arr[0]
  original = True
  for j in arr[1:]:
    if j % i == 0:
      arr.remove(j)
      if i == j:
        original = False
  if original:
    cnt += 1
  arr.remove(i)
    

print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(len(arr)):
  for j in range(len(arr)):
    if arr[i] % arr[j] == 0 and i != j:
      cnt -= 1
      break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
alist=[0]*n
a.sort()
for i in range(n-1):
  if a[i]==a[i+1]:
    alist[i]=1
  for j in range(i+1,n):
    if a[j]%a[i]==0 :
      alist[j]=1
cnt=0
for i in range(n):
  if alist[i]==0:
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
a_max = a_list[-1]

dup_set = set(x for x in set(a_list) if a_list.count(x) > 1)
divisible = [False] * (a_max + 1)

count = 0
i = 0
for a in a_list:
    if divisible[a]:
        continue
    if not a in dup_set:
        count += 1
    x = a
    while x <= a_max:
        divisible[x] = True
        x += a
print(count)

Submission status: Time Limit Exceeded

Solution code:
def get_divisors(n):
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return divisors

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

div_set = set(x for x in set(a_list) if a_list.count(x) > 1)

count = 0
i = 0
for a in a_list:
    j = 1
    divisible = False
    while j * j <= a:
        if a % j == 0:
            if j in div_set or a // j in div_set:
                divisible = True
                break
        j += 1
    if not divisible:
        count += 1
    div_set.add(a)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from copy import *
n=int(input())
a=sorted(list(map(int,input().split())))
l=Counter(a)
m=l.most_common()
f=[False for i in range(max(a)+1)]
ans=0
for i,j in m:
    t=deepcopy(i)
    if f[t]==False and j==1:
               
        ans+=1
        while t<=max(a):
            f[t]=True
            t+=i
    elif f[t]==False and j!=1:
        while t<=max(a):
            f[t]=True
            t+=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
f=[False for i in range(max(a)+1)]

ans=0
for i in range(n):
    t=a[i]
    if i!=n-1:
        if f[t]==False and t!=a[i+1]:       
            ans+=1
            while t<=max(a):
                f[t]=True
                t+=a[i]
        elif f[t]==False and t==a[i+1]:
            while t<=max(a):
                f[t]=True
                t+=a[i]
    if i==n-1:
        if f[t]==False:       
            ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
f=[False for i in range(max(a)+1)]

ans=0
for i in range(n):
    t=a[i]
    if i!=n-1:
        if f[t]==False and t!=a[i+1]:       
            ans+=1
    if i==n-1:
        if f[t]==False:       
            ans+=1
    while t<=max(a):
        f[t]=True
        t+=a[i]
print(ans)

Submission status: Time Limit Exceeded

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

import collections
d=collections.Counter(a_ls)

a_set=set(a_ls)
M=max(a_set)

ans=0

while len(a_set)>0:
	m=min(a_set)
	a_set=a_set-set(range(m,M+1,m))
	if d[m]==1:
		ans+=1



print(ans)


# 2darray [[0] * 4 for i in range(3)]
# import itertools

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_ls = list(map(int, input().split()))
a_ls.sort(reverse=True)
ans = 0
for i in range(n):
    not_divisible = True
    for j in range(i+1,n):
        if a_ls[i] % a_ls[j] == 0 or a_ls[i] == a_ls[j]:
            not_divisible = False
            break
    if i > 0 and a_ls[i-1] == a_ls[i]:
        not_divisible = False
    if not_divisible:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
a_list_min = sorted(a_list)
cnt = 0

#print(a_list_min)

for i in range(0, n):
    for j in range(i+1):
        if i != n-1 and a_list_min[i] == a_list_min[i+1]:
            break
        if j == i:
            cnt += 1
            break
        if a_list_min[i] % a_list_min[j] == 0:
            break
#                print(i,j)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

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

a.sort()
cnt = 0

while 0 != len(a):
    if len(a) == 1:
        cnt += 1
        break

    tmp = []
    if a[0] < a[1]:
        cnt += 1

    for i in range(len(a)):
        if a[i] % a[0] != 0:
            tmp.append(a[i])

    a = tmp[:]

print("{}".format(cnt))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

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

a.sort()
cnt = 0

while 0 != len(a):
    if len(a) == 1:
        cnt += 1
        break

    tmp = a[:]
    if a[0] < a[1]:
        cnt += 1

    for i in range(len(a)):
        if a[i] % a[0] == 0:
            tmp.remove(a[i])

    a = tmp[:]

print("{}".format(cnt))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

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

a.sort()
cnt = 0

while 0 != len(a):
    if len(a) == 1:
        cnt += 1
        break

    tmp = a[:]
    if a[0] < a[1]:
        cnt += 1

    for i in range(len(a)):
        if a[i] % a[0] == 0:
            tmp.remove(a[i])

    a = tmp[:]
    a.sort()

print("{}".format(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.sort(np.array(input().split() , dtype = int))

ans = []

for _ in range(N):
    if len(A) == 1 or (len(A) > 1 and A[0] != A[1]):
        ans.append(A[0])
    new_A = A[A % A[0] != 0]
    A = new_A
    if len(A) == 0:
        break

print(len(ans))

Submission status: Time Limit Exceeded

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

for i in range(n):
	count = 0
	for j in range(n):
		if i!=j:
			if a[i]%a[j] != 0:
				count += 1
			else:
				continue
	if count == n-1:
		ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

M=10**6+10
n=int(input())
a=sorted(lmp())
c=[0]*M
for j in a:
    if c[j]==0:
        k=2
        while j*k<M:
            c[j*k]=1
            k+=1
ans=0
s=Counter(a).most_common()
for x,y in s:
    if c[x]==0 and y==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
tmp_a = [0] * n
#print(a)
for i in range(n-1):
    if tmp_a[i] == 0:
        #print(a[i],tmp_a)
        for j in range(i+1,n):
            if a[i] == a[j]:
                tmp_a[i] = 1
                tmp_a[j] = 1
            if a[j]%a[i] == 0:
                tmp_a[j] = 1
print(n-sum(tmp_a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
tmp_a = [0] * n
for i in range(n):
    if tmp_a[i] == 0:
        for j in range(i+1,n):
            if a[i] == a[j]:
                tmp_a[i] = 1
                tmp_a[j] = 1
            if a[j]%a[i] == 0:
                tmp_a[j] = 1
print(n-sum(tmp_a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
tmp_a = [0] * n
for i in range(n):
    if tmp_a[i] == 0:
        for j in range(i+1,n):
            if a[j]%a[i] == 0:
                tmp_a[j] = 1
            if a[i]%a[j] == 0:
                tmp_a[i] = 1
print(n-sum(tmp_a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
tmp_a = [0] * n
for i in range(n):
    tmp = 0
    if tmp_a[i] == 0:
        for j in range(i+1,n):
            if a[j]%a[i] == 0:
                tmp_a[j] = 1
            if a[i]%a[j] == 0:
                tmp_a[i] = 1
                j = n
print(n-sum(tmp_a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
for i in range(n):
    tmp = 0
    for j in range(n):
        if a[i]%a[j] == 0 and i != j:
            tmp += 1
    if tmp > 0:
        ans += 1
print(n-ans)

Submission status: Time Limit Exceeded

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

A.sort()
count = 1
flag = True
renzoku = False

for a in range(1, N):
    for b in range(a):
        if A[a] == A[b]:
            if renzoku != True:
                count -= 1
            renzoku = True
            flag = False
            break
        else:
            renzoku = False
            
        if A[a] % A[b] == 0:
            flag = False
            break
            
    if flag :
        count += 1
    flag = True
print(count)

Submission status: Time Limit Exceeded

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

A.sort()
A_max = max(A)
A_list = [0] * (A_max + 1)

for a in A:
    if A_list[a] != 1:
        i = 2
        while a * i <= A_max:
            A_list[a * i] = 1
            i += 1
    if a > A_max / 2:
        break

ans = 0
for a in A:
    if A_list[a] == 0:
        if A.count(a) == 1:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

A.sort()
A_max = max(A)
A_list = [0] * (A_max + 1)

for a in A:
    if A_list[a] != 1:
        i = 2
        while a * i <= A_max:
            A_list[a * i] = 1
            i += 1

ans = 0
for a in A:
    if A_list[a] == 0:
        if A.count(a) == 1:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
A.sort()
A_list = defaultdict(int)
A_max = max(A)

for a in A:
    i = 2
    if A_list[a] != 1:
        while a * i <= A_max:
            A_list[a * i] = 1
            i += 1
    if A.count(a) > 1:
        A_list[a] = 1

ans = 0
for a in A:
    if A_list[a] == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

ans=0

a.sort()

while len(a)>0:
    k=a[0]
    kesu=[]
    tyouhuku=False
    for i in range(1,len(a)):
        if a[i]==k:
            tyouhuku=True
        if a[i]%k==0:
            kesu.append(a[i])
    
    for i in range(len(kesu)):
        a=[j for j in a if j !=kesu[i]]
    
    if not tyouhuku:
        a.pop(0)
        ans+=1



print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))[::-1]
ans=0
d={}
for i in a:
  if d.get(i):d[i]+=1
  else:d[i]=1
for i in range(n):
  if d[a[i]]!=1:continue
  for j in range(i+1,n):
    if a[i]%a[j]==0:break
  else:ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [1 for i in range(N)]
for i in range(N):
    if B[i] != 0:
        for j in range(i+1, N):
            if A[i] == A[j]:
                B[i] = 0
                B[j] = 0
            elif A[j] % A[i] == 0:
                B[j] = 0
print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
inf =  1100000
def main():
  N =  int(input())
  a = list(map(int, input().split()))
  a.sort()
  detect = [0] *inf
  for x in a:
    if detect[x] != 0:
      detect[x] = 2
    for i in range(x, inf, x):
      detect[i] += 1
  ans = 0
  for i in range(N):
    if detect[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
inf =  1000005
def main():
  N = int(input())
  a = list(map(int, input().split()))
  a.sort()
  flag = [True]*inf
  num = [0]*inf 
  for i in range(N):
    num[a[i]] += 1
    if flag[a[i]]:
      j = 2
      while (j*a[i] < inf):
        flag[j*a[i]] =  False
        j += 1
  ans = 0
  for i in range(N):
    if flag[a[i]] and num[a[i]] == 1:
      ans += 1
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if 1 in lst:
  count = 0
  for i in range(n):
    if lst[i] == 1:
      count += 1
    if count == 2:
      break
  if count == 1:
    print(1)
  else:
    print(0)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      if n > 100:
        if lst[i] >= lst[n - 1] ** 0.5:
          continue
      for j in range(lst[i] * 2, lst[n - 1] + 1, lst[i]):
        if j in lst:
          tf_lst[j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      if n >= 100:
        if lst[i] >= lst[n-1] ** 0.5:
          continue
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if tf_lst[lst[i] - 1] == 0:
        continue
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      if n > 10000:
        if lst[i] >= lst[n-1] ** 0.5:
          continue
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [1] * lst[n - 1]
  count = 0
  if n > 1:
    pre = 0
    for i in range(n):
      tf_lst[pre:lst[i] - 1] = [0] * (lst[i] - pre - 1)
      pre = lst[i]
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[lst[i] - 1] = 0
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          tf_lst[lst[i] * j - 1] = 0
    #print(tf_lst)
    for i in tf_lst:
      count += i
  else:
    count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
lst.sort()
#print(lst)
dic = {}
for i in range(n):
  dic[lst[i]] = i

if lst[0] == 1:
  if n > 1:
    if lst[0] == lst[1]:
      print(0)
    else:
      print(1)
  else:
    print(1)
else:
  tf_lst = [True] * n
  count = 0
  if n > 1:
    for i in range(n):
      if i <= n - 2:
        if lst[i] == lst[i + 1]:
          tf_lst[i] = False
      if i >= 1:
        if lst[i] == lst[i - 1]:
          tf_lst[i] = False
      for j in range(2, lst[n - 1] // lst[i] + 1):
        if lst[i] * j in lst:
          num = lst[i] * j
          index = dic[num]
          tf_lst[index] = False
  for i in tf_lst:
    if i:
      count += 1
  print(count)