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=sorted([int(i) for i in input().split()])
c=0
for i in range(n):
    for j in range(min(i+2,n)):
        if i==j:
            continue
        if a[i]%a[j]==0:
            break
    else:
        c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    ans = 0
    for i,x in enumerate(a):
        step = 1
        for j,y in enumerate(a):
            if j==i:    continue
            if x%y == 0:    break
            step+=1
        if step==n:
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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


def resolve():
    from collections import Counter
    n = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    s = set(a)
    ans = 0
    for i in a:
        if c[i] >= 2:
            continue
        for j in make_divisors(i):
            if j in s and j != i:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
  if A[i] == 0:
    continue
  else:
    if i == N - 1 or (i < N - 1 and A[i] != A[i+1]):
      ans += 1
    for j in range(i+1, N):
      if A[j] % A[i] == 0:
        A[j] = 0
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        if A[i] % A[j] == 0:
            break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = 0
divs = np.array([[0 for _ in range(n)] for _ in range(n)])
for i in range(n):
  for j in range(i+1, n):
    if a[i] % a[j] != 0:
      divs[i][j] = 1
    if a[j] % a[i] != 0:
      divs[j][i] = 1
  
  if sum(divs[i,:]) == n-1:
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    cnt = 0
    for i in range(N):
        if i > 0 and A[i] == A[i-1]:
            continue
        for j in range(i+1,N):
            if A[i] % A[j] == 0:
                break
        else:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort(reverse=True)
    cnt = 0
    for i in range(len(B)):
        if A.count(B[i])>1:
            continue
        Flag = True
        for j in range(i+1,len(B)):
            if B[i] % B[j] == 0:
                Flag = False
                break
        if Flag:
            cnt += 1
    
    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
count = 0
n = int(input())
a = list(map(int,input().split()))
for i in range(n):
  flag=True
  for j in range(n):
    if(j!=i and a[i]%a[j]==0):
      flag=False
      break
  if flag==True:
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(n):
    result = True
    for j in range(n):
        ai = alist[i]
        aj = alist[j]
        if i != j and ai%aj == 0:
#            print("{}[{}] {}[{}]".format(ai,i,aj,j))
            result = False
            break
    if result:
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
aa = tuple(reversed(sorted(map(int, input().split()))))
cnt = Counter(aa)

ans = 0
for i in range(n):
    if cnt[aa[i]] > 1:
        continue

    f = True
    for j in range(i + 1, n):
        if aa[i] % aa[j] == 0:
            f = False
            break
    if f:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def yakusu(n):
    ans = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            ans.append(i)
            if n // i != i:
                ans.append(n // i)
    
    return sorted(ans)


def main():
    N = int(input())

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

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

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

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        for b in B[i][:-1]:
            if is_in_A_flag[b] > 0:
                is_ans = False
                break
        
        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())

Submission status: Time Limit Exceeded

Solution code:
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)
    #約数の小さい順にソートしたい場合
    #divisors.sort()
    #約数の大きい順にソートしたい場合
    #divisors.sort(reverse=True)
    return divisors
n=int(input())
b=list(map(int,input().split()))
a=dict()
for i in b:
    if i not in a:
        a[i]=1
    else:
        a[i]+=1
ans=0
for i in b:
    for j in make_divisors(i):
        if j==i and a[j]>1:
            break
        if j in a and j!=i:
            break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    a_set = set(a)

    a_cnt = collections.Counter(a)

    # 約数を列挙　n=10^12までいける
    def make_divisors(n, a_set):
        if a_cnt[n] > 1:
            return True

        deleted_set = a_set - {n}
        # divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                # divisors.append(i)
                if i in deleted_set:
                    return True
                if i != n // i:
                    # divisors.append(n // i)
                    if n // i in deleted_set:
                        return True

        # divisors.sort()
        return False

    ans = 0
    for ai in a_set:
        if not make_divisors(ai, a_set):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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)

    # divisors.sort()
    return divisors


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  # type:int
    A_arr = list(map(int, _in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    A_div = []
    for A in A_arr:
        A_div.append(make_divisors(A))

    ans = 0
    for i, A_d in enumerate(A_div):
        for j, A in enumerate(A_arr):
            if i != j and A in A_d:
                break
        else:
            ans += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
cnt = defaultdict(int)
for i in range(n):
    cnt[a[i]] += 1
cnt = sorted(cnt.items(), key = lambda x: x[0])
ans = 0
for i in range(len(cnt)):
    if cnt[i][1] != 1:
        continue
    flag = True
    for j in range(i):
        if cnt[i][0] % cnt[j][0] == 0:
            flag = False
            break
    
    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def div(n):
    lower_div, upper_div = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_div.append(i)
            if i != n // i:
                upper_div.append(n // i)
        i += 1
    return lower_div + upper_div[::-1]

n = int(input())
A = list(map(int, input().split()))
s = set(A)
c = Counter(A)
cnt = 0
for a in A:
    if c[a] >= 2:
        continue
    else:
        d = set(div(a))
        if len(d - s) == len(d) - 1:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#D
N = int(input())
A = list(map(int, input().split()))
counter = 0
for i in range(N):
    can_divide = False
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            can_divide = True
            break
    if not can_divide:
        counter+= 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
x=[0 for i in range(max(A))]
#print(x)
for i in range(N):
  if(x[A[i]-1]==0):
    if(i<N-1):
      if(A[i+1]!=A[i]):
        ans+=1
    else:
      ans+=1
    j=1
    while(j*A[i]<=max(A)):
      x[j*A[i]-1]=1
      j+=1
print(ans)
#print(x)

Submission status: Time Limit Exceeded

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

A.sort()

count = 0

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

    if (i + 1 < N and a == A[i + 1]) or (i - 1 >= 0 and a == A[i - 1]):
        continue
    else:
        flag = False

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

            if b * 2 > a:
                break
            
            if a % b == 0:
                flag = True
                break
        
        if not flag:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
ans = 0
for i, x in enumerate(arr):
    flg = True
    for j, y in enumerate(arr):
        if i == j:
            continue
        if x % y == 0:
            flg = False
    if flg:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import Counter
def divisors(n, sort=False):
    """
    nの約数をO(√n)で列挙する
    """
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n//i)
    if sort:
        d.sort()
    return d
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)
ans = 0
for a in A:
    if cnt[a] >= 2:
        continue
    flg = True
    for d in divisors(a):
        if d == a:
            continue
        if d in div:
            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()))

ans = 0

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    elif A[i]%A[j] == 0:
      ans += 1
      break
      
print(N - ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))
count = 0
for i in range(n):
    flag = True
    for j in range(n):
        if i!=j and l[i] % l[j] == 0:
            flag = False
            break
    count += flag
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lst=list(map(int,input().split()))
cnt=0
temp=[]
for i in range(n):
  for j in range(n):
    if i==j or i in temp:
      continue
    else:
      if lst[i]%lst[j]==0:
        cnt+=1
        temp.append(i)
print(n-cnt)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def solve(A):
    ans = 0
    c = collections.Counter(A)
    # dupes = {k for k, v in c.items() if v > 1}
    dupes = set()
    for k, v in c.items():
        if v > 1:
            dupes.add(k)
    aset = set(A)
    for a in A:
        if a in dupes:
            continue
        for v in (set(make_divisors(a))):
            if a == v:
                continue
            if v in aset:
                break
        else:
            ans += 1
    print(ans)
    return


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(n):
    k = 1
    for j in range(n):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            k = 0
        else:
            pass

        if j == n - 1:
            if k == 1:
                p += 1

print(p)

Submission status: Time Limit Exceeded

Solution code:
b = int(input())
a = list(map(int,input().split()))
ans =0
for i in range(b):
	r=0
	for j in range(b):
		if i!=j and a[i]%a[j]==0 :
			r=1
			break
	if r==0:
		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()))

n=int(input())
a=sorted(lmp())
ans=n
for i in range(n-1,-1,-1):
    x=a[i]
    if a.count(x)>1:
        ans-=1
        continue
    for k in range(bisect.bisect_left(a,x//2+1)):
        if x%a[k]==0:
            ans-=1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
count=n
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        elif a[i]%a[j]==0:
            count-=1
            break
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
c = Counter(a)

se = set()

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)
    divisors.sort()
    return divisors

for i in a:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

count = 0

for i in range(0, len(num_list)):
    for j in range(0, len(num_list)):
        if j != i:
            if num_list[i] % num_list[j] == 0:
                count += 1
                break


print(n - count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ls = list(map(int,input().split()))
k = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if ls[i] >=2*ls[j] or ls[i] == ls[j]:
            p = ls[i]/ls[j]
            if p % 1 == 0:
                break
    else:
        k += 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

res = [0]*(1000001)
for i in a: res[i] += 1


def check(N,P):
    if N == 1:
        if P[1]==1: return True
        else: return False
    res = []
    for i in range(1,N):
        if i*i >= N: break
        if N%i == 0:
            res.append(i)
            res.append(N//i)
    if i*i == N: res.append(i)
    
    for i in res:
        if i!=N and P[i] >= 1: return False
        if i==N and P[i] >= 2: return False
    return True    

ans = 0
for N in a:
    if check(N,res): ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
C = []
ans = 0
for i in range(N):
    check = 0
    for j in C:
        if A[i] % j == 0:
            check = 1
            break
    #print(check,ans,A[i],C)
    if check == 0:
        C.append(A[i])
        if i < N-1:
            if A[i] != A[i+1]:
                ans += 1
        else:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dec(a):
    res = []
    for i in range(1,int(a**0.5+1)):
        if a%i==0:
            res.append(i)
            res.append(a//i)
    res = list(set(res))
    return res

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

d = {}
for i in range(N):
    if A[i] not in d:
        d[A[i]] = 1
    else:
        d[A[i]] += 1

ans = N
for i in range(N):
    dl = dec(A[i])
    for a in dl:
        if a in d:
            if a==A[i]:
                if d[a]>1:
                    ans -= 1
                    break
            else:
                ans -= 1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()
A = [int(s) for s in A]

count = 0

for i in range(N):
    flag = 0
    for j in range(N):
        if j == i:
            continue
        else:
            if A[i]%A[j] ==0:
                flag = 1
                break
    if flag == 1:
        count += 1

print(N-count)

Submission status: Time Limit Exceeded

Solution code:
import sys

X = int(input())
a = list(map(int, input().strip().split()))
tmp = []

for i in range(0, X):
  cnt = 0
  for j in range(0,X):
    if (a[i])%(a[j]) == 0:
      cnt = cnt +1
  tmp.append(cnt)
print(tmp.count(1))

Submission status: Time Limit Exceeded

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

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
for i in range(n):
    B[A[i]] += 1

for i in range(n):
    Y = []
    Z = []
    for j in range(1, int(A[i]**0.5)+1):
        if A[i] % j == 0:
            Y.append(j)
            if j != A[i]//j:
                Z.append(A[i]//j)
    Y = [A[i]] + Y + Z[::-1]
    # print(Y)
    ok = 1
    for j in range(len(Y)):
        if (Y[j] != A[i] and B[Y[j]] > 0) or (Y[j] == A[i] and B[Y[j]] > 1):
            ok = 0
            break
    # print(ok)
    ans += ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

ans = 0
for i in b:
	k = makediv(i)
	k.remove(i)
	mode = 1
	for l in k:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

if __name__ == '__main__':
    n = int(input().strip())
    a = list(map(int, input().strip().split()))
    ans = 0
    aa = np.argsort(a)

    for index in aa:
        counter = 0
        for i in range(n):
            if a[index] % a[i] == 0:
                counter += 1
        if counter == 1:
            ans += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math 
def factors(n):
    fact = []
    i = 1
    while i <= math.sqrt(n): 
        if (n % i == 0) : 
            if (n / i == i):
                fact.append(i) 
            else:
                fact.append(i)
                fact.append(n // i)
        i = i + 1
    return fact
n = int(input())
l = list(map(int, input().split()))
vis = [0] * 1000003
ans = 0
for i in l: vis[i] -= -1
for i in range(n):
    tmp = factors(l[i])
    cnt = 0
    for j in tmp:
        cnt += vis[j]
        if j == l[i]: cnt += -1
    if cnt == 0: ans -= -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def make_divisors(n):

    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n and i in c:
                return False

            tmp = n // i
            if i != tmp:
                if tmp != n and tmp in c:
                    return False
    return True


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

c = Counter(A)
ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 約数を取得
    if make_divisors(a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_div = [0 for _ in range(N)]
answer = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i] % A[j] == 0:
            A_div[i] += 1
        if A[j] % A[i] == 0:
            A_div[j] += 1

print(A_div.count(0))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

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

for i in range(n):
    for j in range(n):
        if a[i] < a[j]:
            ans += 1
            break
        if (i == j): continue
        if a[i] % a[j] == 0: break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    # 約数を列挙　n=10^12までいける
    def make_divisors(n, a_set, a_cnt):
        if a_cnt[n] > 1:
            return True

        deleted_set = a_set - {n}
        # divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                # divisors.append(i)
                if i in deleted_set:
                    return True
                if i != n // i:
                    # divisors.append(n // i)
                    if n // i in deleted_set:
                        return True

        # divisors.sort()
        return False

    n = ni()
    a = na()

    a_set = set(a)

    a_cnt = collections.Counter(a)

    ans = 0
    for ai in a_set:
        if not make_divisors(ai, a_set, a_cnt):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect, bisect_left
N = int(input())
A = sorted(list(map(int, input().split())))
ans = 0
i = 0
while i < N:
  j = 0
  isOK = True
  while A[j]*2 <= A[i] and isOK:
    if A[i]%A[j] == 0:
      isOK = False
      break
    j += 1
  if bisect(A, A[i])-bisect_left(A, A[i]) == 1 and isOK:
    ans += 1
  i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import Counter
    N=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))
    A.sort()

    A_set=set()
    
    A_counter=Counter(A)

    st=set()
    count=0
    for a in A:
        if a==0:
            continue
        flag=True
        for s in st:
            if a%s==0:
                flag=False
                break
        if flag:
            st.add(a)
            if A_counter[a]==1:
                count+=1
    
    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)
"""
全探索はだめです
dp[i] := iまでを選んだときの通り数
dp[i+1] := dp[i] + sum(dp*(if warikireru))
"""



def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

ans = 0
for i in b:
	k = makediv(i)
	k.remove(i)
	mode = 1
	for l in k:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A_array = list(map(int, input().split()))

A_array.sort()

use_array = [0] * A_array[-1]

ans = 0

for i in range(N):
    a = A_array[i]
    for j in range(1, int(math.sqrt(a)) + 1):
        if a % j == 0:
            if use_array[j - 1] == 1 or use_array[a // j - 1] == 1:
                break
    else:
        use_array[a - 1] = 1
        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
        ans += 1
    use_array[a - 1] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
A = sorted(A)
S = Counter(A)

prime = []

while len(A) > 1:
    prime.append(A[0])
    A = [j for j in A if j % A[0] != 0]

prime += A

ans = []
for i in range(len(prime)):
    if S[prime[i]] == 1:
        ans.append(prime[i])
print(len(ans))

Submission status: Time Limit Exceeded

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


sum = 0

for i in range(N):
    Ai = A[i]
    B = A.copy()
    B.pop(i)

    isthis = True


    for j in range(N-1):
        if Ai%B[j]==0:
            isthis = False
            break

    if isthis == True:
        sum += 1

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())
arr = np.array(list(map(int, input().split())))
ans=0

for i in range(N):
    if np.count_nonzero(arr[i] % arr == 0) == 1:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()

C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a in A:
    if C[a] >= 2:
        ans += 1
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)