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:
import numpy as np
N = int(input())
An = list(map(int, input().split()))
ok = [False] * N
a_An = np.array(An)
for i, a in enumerate(An):
    temp = a_An / a
    temp[i] = 0.1
    check = (temp % 1 == 0)
    ok = ok | check
print(np.count_nonzero(ok == 0))

Submission status: Time Limit Exceeded

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



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.5))
    J = min(idx+10,i)
    J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

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

count=N

if 1 in A:
  if A.count(1)>1:
    print(0)
  else:
    print(1)
  exit()

ma=max(A)
mi=min(A)
  
for i in range(N):
  n=A[i]
  B=A.copy()
  B.pop(i)
  for j in range(mi,ma+1):
    if n % j == 0:
      if j in B:#count
        #print(n,j)
        count-=1
        break
      if j != n // j and n//j<=ma and mi<=n//j:
        if n//j in B:#count
          #print(n,n//j,"//")
          count-=1
          break

print(count)

Submission status: Time Limit Exceeded

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

import sys
from math import gcd
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def divisors(n):
    m = 1
    divs = []
    while m * m <= n:
        if n % m == 0:
            divs.append(m)
            if n != m * m:
                divs.append(n // m)
        m += 1
    divs.sort()
    return divs


N, *A = map(int, read().split())
A = np.array(A)

cnt = 0
for i, a in enumerate(A):
    divs = divisors(a)[:-1]
    if len(set(divs) & set(A)) > 0:
        continue
    acc = (A == a)
    acc[i] = False
    if sum(acc) >= 1:
        continue
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors


exists = [False] * (10 ** 6 + 1)

#input = raw_input
n0 = int(input())
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()


for A in As:
    exists[A] = True

for A1, num in counter.items():
    if num >= 2:
        continue
    
    exist = False

    ds = make_divisors(A1)
    for d in ds:
        if exists[d]:
            if d != A1:
                exist = True

    if not exist:
        out += 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
list = []
for i in range(n):
    count = 0
    for j in range(n):
        if i == j:
            pass
        elif a[i] in list:
            break
        elif count == 0:
            if a[i] % a[j] == 0:
                count = 1
                list.append(a[i])
        else:
            break
    else:
        if count == 0:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

count=0
isDividable=0

for i in range(n):
  isDividable=0
  for j in range(n):
    if i != j and a[i] % a[j] == 0:
      isDividable=1
      break
  if isDividable==0:
    count=count+1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = input()
    a = list(map(int, input().split()))
    bt = [0] * len(a)
    for i in range(0, len(a)):
        flg = True
        for j in range(0, len(a)):
            if i == j or bt[i] == 1:
                continue
            if a[j] % a[i] == 0:
                bt[j] = 1
            if a[i] % a[j] == 0:
                bt[i] = 1
    print(len(bt) - sum(bt))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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

ans = 0
  
while True:
  d = A.pop(0)
  
  if d in A:
    ans -= 1
  
  A = list(reversed([ a for a in A[::-1] if a % d != 0]))
  ans += 1
  if A:
    True
  else:
    break
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
line = input()
line = line.rstrip().split(' ')
n = int(line[0])

line = input()
line = line.rstrip().split(' ')
a = []
for i in line:
    a.append(int(i))

answer = 0

for i in range(len(a)):
    dividable = False
    for j in range(len(a)):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            dividable = True
            break

    if dividable == False:
        answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
A.sort()
counter = collections.Counter(A)
counta = 0


for index, num in enumerate(A):
    for tmp_index in range(0, index):
        if num % A[tmp_index] == 0:
            break
    else:
        if counter[num] == 1:
            counta += 1

print(counta)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]


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 main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = 0
    num = 0
    for i in A:
        p = A.pop(num)
        yakusuu = make_divisors(i)

        c = 0
        for j in yakusuu:
            if j in A:
                c += 1
        #print(j,c)
        if c != 0:
            ans += 1
        A.insert(num, p)
        num += 1


    print(N - ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
def solve():
    n, *A = map(int, open(0).read().split())
    X = [0] * (max(A) + 1)
    for a in A:
        X[a] += 1
    c = 0
    for a in A:
        X[a] -= 1
        for i in range(1, int(sqrt(a))+1):
            q, r = divmod(a, i)
            if r == 0:
                if X[i] != 0 or X[q] != 0:
                    break
        else:
            c += 1
        X[a] += 1
    print(c)

solve()

Submission status: Time Limit Exceeded

Solution code:
input()
A = sorted(map(int, input().split()))
B = 0
while True:
    p = A[0]
    if A.count(p) == 1:
        B +=1
    A = [e for e in A if e % p !=0]
    if not A:
        break
print(B)

Submission status: Time Limit Exceeded

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

k = 0
b = 0
for l in range(n):
    if a[l] == 1:
        b = b + 1
        
if b == 0:
    for i in range(n):
        for j in range(n):
          if i != j:            
            if a[i] % a[j] == 0:
              break
          if j == n-1:
            k = k + 1          
    print(k)
elif b == 1:
    print('1')
else:
    print('0')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(int(i) for i in input().split())
a.sort()
a2=[]

for i in range(n):
  for k in range(i+1):
    a2.append(a[k])
  if i+2<=len(a):
    if a[i+1]==a[i]:
      a2.pop(-1)
  for j in range(i+1,len(a)):
    if a[j]%a[i]!=0:
      a2.append(a[j])
  a=a2
  a2=[]
  if len(a)<=i+1:
    break
       
print(len(a))

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 A[i] % A[j] == 0 and i != j:
      ans += 1
      break
print(n - ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
A = input().split(" ")

i = 0
j = 0
flag = 1
Ans = 0

for n_tmp in A:
  for n_tmp2 in A:
    if i != j:
      if int(n_tmp) % int(n_tmp2) == 0:
        flag = 0
    j += 1
  j = 0
  i += 1
  Ans += flag
  flag = 1

print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N = int(input())
A = list(map(int,(input().split())))
A.sort()
l = []
ans = 0
for i in range(N):
    tmp = A[i-1]
    if i != N-1:
        if A[i] != A[i+1]:
            now = A[i]
            for j in range(len(l)):
                if now % l[j] == 0:
                    flag = 0
                    break
                if now < l[j]*2:
                    flag = 1
                    break
            else:
                flag = 1
            if flag == 1:
                l.append(now)
                if i == 0 or now != tmp:
                    ans += 1
    else:
        now = A[i]
        for j in range(len(l)):
            if now % l[j] == 0:
                flag = 0
                break
            if now < l[j]*2:
                flag = 1
                break
        else:
            flag = 1
        if flag == 1:
            l.append(now)
            if i == 0 or now != tmp:
                ans += 1
print(ans)
#print(l)

Submission status: Time Limit Exceeded

Solution code:
# 幅優先探索（行きがけ）
import collections
import sys
import math
import copy


def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())


def main():
    N = I()
    AArry = LI()
    AArry.sort()
    AArry = collections.deque(AArry)
    count = 0
    while AArry:
        a = AArry.popleft()
        AArry2 = copy.copy(AArry)
        flag = 0
        for v in AArry2:
            if v % a == 0:
                if v == a:
                    flag = 1
                AArry.remove(v)
                count += 1
        if flag == 1:
            count += 1

    print(N-count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(0,N):
  flag = True
  for j in range(0,N):
    if i != j:
      if A[i] % A[j] == 0:
        flag = False
        break
  if(flag):
    l.append(A[i])

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(1,N):
  if Flag[i] ==1:
    for j in range(i):
      if New_List[i] == New_List[j]:
        Flag[i] = 0
        Flag[j] = 0
      if Flag[j] == 1:
        if New_List[i] % New_List[j] == 0:
          Flag[i] = 0
        else:
          pass
      elif Flag[j] == 0:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
while len(l) > 0:
    tmp = l[0]
    if len(l) >= 2 and l[0] == l[1]:
        cnt -= 1
    t = len(l)-1
    for i in range(len(l)):
        if l[t-i]%tmp == 0:
            l.pop(t-i)
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

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]

for i in range(0,n):
    if a.count(a[i]) == 1:
        l = sa & set(make_divisors(a[i]))
        if len(l) == 1:
            ans = ans + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
A.insert(0,0)
i,n=1,0
while i<N+1:
    if A[i]==A[i-1]:
        i+=1
        continue
    if i==N:
        n+=1
        break
    j=i
    while j<N+1:
        if i==j:
            j+=1
            continue
        if A[i]%A[j]==0:
            break
        if j==N:
            n+=1
        j+=1
    i+=1
print(n)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=list(map(int,input().split()))
  tf=[1]*n
  n=n-1
#r=[]
#print(n)
#print(a)
  notdiv=True
  firstyn=0
  for i in range(n,-1,-1):
  #print(i)
  #notdiv=True
    if tf[i] ==0:
      continue
    for j in range(i):
    #print(a[j])
      if tf[j] ==0:
        continue
      if a[i]%a[j] == 0:
        tf[i]=0
      #break
      if a[j]%a[i] == 0:
        tf[j]=0
      #break
#print(tf)
  print(sum(tf))
main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [int(x) for x in input().split()]
index=[]
index_d=range(N)
n=0

for i in range(N):
  for j in index:
    if i!=j and A[i]%A[j]==0:
      n+=1
      break
  for j in index_d:
    if i!=j and A[i]%A[j]==0:
      index.append(j)
      index.remove(j)
      n+=1
      break
print(N-n)

"""
10
33 18 45 28 8 19 89 86 2 4
5
"""

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = list(map(int, input().split()))
count = [0]*N
nums.sort()
for i in range(N):
  fNum = nums[i]
  for j in range(0,N):
    if (nums[j] > fNum):
      break
    if (count[i] == 1):
      break
    if (i == j):
      continue
    else:
      sNum = nums[j]
      if (fNum%sNum == 0):
      	count[i] += 1
answer = 0
for i in count:
  if (i == 0):
    answer += 1
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

count = 0
A = list(map(int, input().split()))
A.sort(reverse=True)
s = set([])

for i in range(n):
  for j in range(n):
    if i != n-j-1 and A[i] % A[n-j-1] == 0:
      s.add(i+1)
      break
      
print(n-len(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 
N = int(input())
numbers = [int(i) for i in input().split()]

c = Counter(numbers)

divisors = sorted(set(numbers))
target_numbers = sorted([k for k, v in c.items() if v == 1])

cnt = N - len(target_numbers)
for n in target_numbers:
    for d in divisors:
        if n == d:
            continue
        if n % d == 0:
            cnt += 1
            break
        if n /2 < d:
            break
            
print(N - cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

import collections


def sieve_of_divisors(end):
    if end <= 1:
        raise ValueError("The integer `end` must be greater than one")
    # is_prime = [True for _ in range(end)]
    # is_prime[0] = False
    # is_prime[1] = False
    divs = [{1, i} for i in range(end)]
    divs[0] = set()
    for i in range(2, end):
        for j in range(2 * i, end, i):
            # is_prime[j] = False
            divs[j].update(divs[i])
    return divs


def count_nondivisors(n, bs):
    ctr = collections.Counter(bs)
    m = max(bs)
    all_ds = sieve_of_divisors(m + 1)
    ds = {k: sum(ctr[k] for k in all_ds[k]) for k in ctr.keys()}
    num_div_elems_table = [ds[bs[i]] for i in range(n)]
    res = sum(num_div_elems_table[i] == 1 for i in range(n))
    return res


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    res = count_nondivisors(n, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np
from numba import jit, i8, void


def get_input() -> tuple:
    """
    標準入力の取得.

    Returns:
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))

    return N, A


@jit(nopython=True)
def main(A: np.ndarray) -> None:
    """
    求解処理

    Args:
        A (np.ndarray): 数列
    """
    # 求解処理
    result = 0
    for a in A:
        c = (a % A == 0)
        if np.sum(a % A == 0) == 1:
            result += 1

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, A = get_input()
    A = np.array(A)
    main(A)

Submission status: Time Limit Exceeded

Solution code:
#ABC170d

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

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

print(count)

Submission status: Time Limit Exceeded

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

for i in range (0,N):
  res=0
  for j in range(0,N):
    if(i!=j and list[i] % list[j]==0):
      res+=1
  if(res!=0):
    ans+=1

print(N-ans)

Submission status: Time Limit Exceeded

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

res = 0

for i, Ai in enumerate(listA):
    for j, Aj in enumerate(listA):
        if i == j:
            continue
        if Ai % Aj == 0:
            res += 1
            break

print(N - res)

Submission status: Time Limit Exceeded

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

cnt = 0
for Ai in A:
    if A.count(Ai) == 1:
        f = True
        for Aj in A:
            if Ai <= Aj:
                break

            if Ai % Aj == 0:
                f = False
                break
        cnt += f

print(cnt)

Submission status: Time Limit Exceeded

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


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

a.sort()

flg=0
for i in range(n):
    li = make_divisors(a[i])
    for j in range(n):
        if i == j:
            continue
        if a[j] > a[i]:
            break
        if a[j] in li:
            flg+=1
            break
        

print(n-flg)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = map(int, raw_input().split(' '))
ais = map(int, raw_input().split(' '))
cc = collections.Counter(ais)
ais.sort()
p = [True for _ in range(10 ** 6 + 1)]

count = 0
for ai in ais:
	if p[ai] is True:
		x = 2 * ai
	 	while(x < len(p)): 
	 		p[x] = False
	 		x += ai
for ai in ais:
	if p[ai] is True:
		if cc[ai] == 1:
			count +=1
print count

Submission status: Time Limit Exceeded

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


N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
    if not set(make_divisors(A[i])) & set(A[:i] + A[i + 1:]):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
M = int(input())
A=list(map(int,input().split()))
A.sort()
k=0
judge=0
ans=0
while True:
    if k>=len(A)-1:
        break
    for i in range(len(A)-1,k,-1):
        judge=0
        if A[i]%A[k]==0:
            if A[i]==A[k]:
                judge=1
            A.pop(i)
    k+=1
    ans=ans+judge

print(len(A)-ans)

Submission status: Time Limit Exceeded

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


def main():
    ans = 0
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        b = 0
        for j in range(n):
            if j == i:
                b += 1
            else:
                if a[i] % a[j] != 0:
                    b += 1
        if b == n:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
    return lower_divisors + upper_divisors[::-1]


def counter(a):
    d = {}
    for i in a:
        d[i] = d.get(i, 0) + 1
    return d


def resolve():
    import sys
    input = sys.stdin.readline
    _ = int(input())
    a = list(map(int, input().split()))
    c = counter(a)
    if 1 in c:
        if c[1] > 1:
            print(0)
        else:
            print(1)
        return
    ans = 0
    for i in (x for x, y in c.items() if y == 1):
        for j in make_divisors(i):
            if j in c 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()))

ans = 0
for i in range(n):
  for j in sorted(a):
    if a[i] % j == 0:
      if a[i] != j:
        ans += 1
        break
      else:
        if a.count(j) > 1:
          ans += 1
          break
    
print(n - ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np
nums.sort()
npnums = np.array(nums)

cnt = 0 #個数のカウント


for i,v in enumerate(nums):
    if np.count_nonzero(v % npnums[:i+2] == 0) > 1:
        cnt +=1
    else:
        continue
print(n-cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
As = np.asarray(list((map(int, input().split()))))
Bs = [1]*N
for index, i in enumerate(As):
    Bs += As%i != 0
print(list(Bs).count(N))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted(A,reverse=True)
count=0
for i in range(1,N):
  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
    if flag==False:
      count+=1
flag=False
for j in range(N-1,0,-1):
  if B[0]%B[j]==0:
    flag=True
    break
if flag==False:
  count+=1
print(count)

Submission status: Time Limit Exceeded

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

if (A.count(1) > 1):
    print(0)
    exit()
if (A.count(1) == 1):
    print(1)
    exit()

def divide(target, divider):
    if (divider & (divider - 1) == 0):
        return target & (divider - 1)
    else:
        return target % divider

A.sort()
indexList = [1] * N
for i in range(N - 1):
    if (indexList[i] == 0):
        continue
    else:
        adopter = -1
        if (A.count(A[i]) > 1):
            for k in range(A.count(A[i])):
                indexList[i + k] = 0
                adopter += 1
        else:
            adopter = 0
        for j in range(i + 1 + adopter, N):
            if (divide(A[j], A[i]) == 0):
                indexList[j] = 0

print(indexList.count(1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nli = [int(i) for i in input().split()]
count = 0
index = 0
for i in range(0, n):
    for j in range(0, n):
      if nli[i] < nli[j]:
          index += 1
      elif nli[i] >= nli[j] and nli[i] % nli[j] != 0:
          index += 1
    if index == n - 1:
        count += 1
    index = 0
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

if 1 in sa:
    if sa[1]>1:
        print(0)
    else:
        print(1)
    exit()

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1

    for i in range(2,min(int(ai**(1/2)+7),ai)):
        if ai%i==0:
            if i in sa or ai//i in sa:
                ans-=1
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

A_list.sort()
check = [1]*len(A_list)


for i in range(len(A_list)-1):
    
    for j in range(i+1, len(A_list)):
        if check[j] == 0:
            continue
        
        if A_list[j] == A_list[i]:
            check[i] = 0
            check[j] = 0
        
        if A_list[j] % A_list[i] == 0:
            check[j] = 0
        

print(check.count(1))

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
    return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = {}
    for x in a:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
    ans = 0
    for v in a:
        if dic[v] > 1:
            continue
        tmp = Divisor_Set(v)
        if v in tmp:
            tmp.remove(v)
        f = True
        for x in tmp:
            if x in dic or ((x > 1) and ((v//x) in dic)):
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

ans = set(A)
B = ans.copy()

while True:
    for ai, aj in product(B, A):
        if ai == aj:
            continue
        if ai % aj == 0:
            if ai in ans:
                ans.remove(ai)
                break
    if len(B) == len(ans):
        break
    B = list(ans)
    
s = len(ans)
for bi in B:
    if A.count(bi)!=1:
        s-=1
print(s)

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+9)

    zero =  A.count(1)
    if zero>1:
        print(0)
        return
    if zero==1:
        print(1)
        return

    for i in range(lenb):
        if Boo[i]:
            for j in range(i+1,lenb):
                if Boo[j] and s[B[j]-1]==False and B[j] % B[i] == 0:
                    Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and C[B[i]]==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    idx = bisect.bisect_left(A, pow(A[i],0.6))
    J = min(idx+1,i)
    J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Time Limit Exceeded

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

ans = []
for i in range(n):
    flg = True
    for j in range(n):
        if i != j:
            if A[i] % A[j] == 0:
                flg = False
                break
    if flg:
        ans.append(i + 1)
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = (list(map(int, input().split(' '))))
D = [0]*(10**6+1)
ans = 0
for i in A:
    D[i] += 1
for i in A:
    flg = True
    if D[i] > 1:
        continue
    for j in range(1,int(i**0.5)+2):
        if not i%j:
            if D[j] and i != j:
                flg = False
                break
            if j != i//j and D[i//j] and i//j != i: 
                    flg = False
                    break
    if flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit

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

count=N

if 1 in A:
  if A.count(1)>1:
    print(0)
  else:
    print(1)
  exit()

ma=max(A)
mi=min(A)
  
for i in range(N):
  n=A[i]
  B=A.copy()
  B.pop(i)
  for j in range(1,ma+1):
    if n % j == 0:
      if j in B:#count
        #print(n,j)
        count-=1
        break
      if j != n // j and n//j<=ma and mi<=n//j:
        if n//j in B:#count
          #print(n,n//j,"//")
          count-=1
          break

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
asor = sorted(a)
numlist = []
cnt = 0
while True:
    if asor == []:
        break
    if len(asor) ==1:
        cnt +=1
        break
    cnt +=1
    num = asor[0]
    numlist = []
    if asor[1] == num:
        cnt-=1
    for i in range (len(asor)):
        if asor[i]%num == 0:
            numlist.append(asor[i])
    asor = list(filter(lambda x: x not in numlist, asor))
print(cnt)

Submission status: Time Limit Exceeded

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

a.sort()

i=0
deli=False
while i<len(a):
  j = i+1
  while j<len(a):
    if a[j] == a[i]:
      deli=True
    if a[j] % a[i] == 0:
      a.pop(j)
      j-=1
    j+=1
    #print(a)
  if deli:
    a.pop(i)
    deli=False
    i-=1
  i+=1

print(len(a))