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:
def Not_Divisible():
    N = int(input())
    A = list(map(int, input().split()))

    return_count = 0
    for i in A:
        count = 0
        for j in A:
            if i % j != 0:
                count += 1
        if count == N - 1:
            return_count += 1

    return return_count

print(Not_Divisible())

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

A.sort()
basis = []

for a in A:
    for b in basis:
        if a % b == 0:
            break
    else:
        basis.append(a)

ans = 0
c = Counter(A)
for b in basis:
    if c[b] == 1:
        ans += 1

print(ans)
pass

Submission status: Time Limit Exceeded

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

cnt = 0
div_times = 0

for i in ints:
    for j in ints:
        if i % j == 0:
            div_times += 1
        if div_times == 2:
            break
    if div_times == 1:
        cnt += 1
    div_times = 0

print(cnt)

Submission status: Time Limit Exceeded

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

d = [0 for i in range(max(a)+1)]
for i in range(N):
    d[a[i]] += 1
ans = 0

for i in range(N):
    divisors = make_divisors(a[i])
    flag = 1
    d[a[i]] -= 1
    for d_temp in divisors:
        if d[d_temp] > 0:
            flag = 0
            break
    if flag == 1:
        ans += 1
    d[a[i]] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
 
mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000
 
d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))
 
N = int(input())
A = LI()
A.sort()
 
cc = collections.Counter(A)
# print(cc)
chosen = []
cnt = 0
for key in cc.keys():
    if cc[key] > 1:
        chosen.append(key)
        continue
    if len(chosen) == 0:
        cnt += 1
        chosen.append(key)
    else:
        for c in chosen:
            if key % c == 0:
                break
        else:
            chosen.append(key)
            cnt += 1
 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = sorted([int(i) for i in input().split()])
A = np.array(A)

ans = 0
while len(A) > 1:
    if A[0] != A[1]:
        ans += 1
    n = A[0]
    A = A[np.where(A % n != 0)[0]]
    
if len(A) == 1:
    print(ans+1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
x_f = False
for n in range(len(A)):
    for k in range(len(A)-1, n, -1):
        if A[k] % A[n] == 0:
            if A[k] == A[n]: x_f = True
            A.pop(k)
    else:
        if x_f:
            A.pop(n)
            x_f = False
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
alist=list(map(int, input().split()))
aarray=np.array(alist)
ans=0
for a in alist:
    aaa=np.array([a]*N)
    amari=aaa%aarray
    if list(amari).count(0)==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)
    hurui = [1] * len(A)
    prev = 0
    for i, a in enumerate(A):
        if a == prev:
            hurui[i-1] = 0
            hurui[i] = 0
            prev = a
            continue
        if i == len(A)-1:
            prev = a
            continue
        if hurui[i] == 0:
            prev = a
            continue
        for j, b in enumerate(A[i+1:]):
            if hurui[i+1+j]==0:
                prev = a
                continue
            if b % a == 0:
                hurui[i+1+j] = 0
            prev = a
    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import sqrt
n = int(input())
a = Counter(map(int, input().split()))
ans = n
for num, count in a.items():
    if count > 1:
        ans -= count
        continue
    if 1 in a and num != 1:
        ans -= count
        continue
    i = 2
    while i <= sqrt(num):
        if num % i == 0:
            if i in a or (num // i) in a:
                ans -= count
                break
        i += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)
    l = [False] * (10 ** 6 + 5)

    def yakusu(num):
        ret = []
        lim = int(num ** 0.5) + 5
        for i in range(1, lim):
            if i * i > num: break
            if num%i != 0: continue
            ret.append(i)
            if i != num//i: ret.append(num//i)
        return ret

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys():
        l[n] = True
        e[n] = yakusu(n)

    for n in A.keys():
        if A[n] >= 2: continue
        if len(e[n]) == 2:
            ans += 1
            continue
        for p in e[n]:
            if p in {1, n}: continue
            if l[p]: break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
A.sort()
#A = [i for i in range(2, N+2)]

def is_prime(n):
  if n == 1:
    return False
  for i in range(2, int(math.sqrt(n)) + 1):
    if n % i == 0:
      return False
  return True

D = []
E = []

for i, x in enumerate(A):
  Flag = True
  
  if i >= 1 and x == D[-1]:
    E.append(x)
    continue

  if i >= 1 and D[0] != 1 and is_prime(x):
    D.append(x)
    continue
    
  for j in D:
    if x%j == 0:
      Flag = False
      if x == j:
        E.append(x)
      break
    
  if Flag:
    D.append(x)

print(len(set(D)-set(E)))

Submission status: Time Limit Exceeded

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

    st = set(A)
    counter = Counter(A)

    ans = 0
    for i in range(N):
        if counter[A[i]] >= 2:
            continue
        divisors = calc_divisors(A[i])
        for divisor in divisors:
            if divisor == A[i]:
                continue
            if divisor in st:
                break
        else:
            ans += 1
    
    print(ans)

def calc_divisors(n):
    divisors = []
    for i in range(1,int(math.sqrt(n)+1)):
        if n % i == 0:
            divisors.append(i)
            if (i*i != n):
                divisors.append(n//i)

    return divisors

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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()))
a.sort()
flag = [True] * n
for i, num in enumerate(a):
    div = make_divisors(num)
    for d in div:
        if d == num:
            if a.count(d)>1:
                flag[i] = False
            continue
        if d in a:
            flag[i] = False
print(np.count_nonzero(flag))

Submission status: Time Limit Exceeded

Solution code:
n = (int)(input())
a=sorted(list(map(int, input().split(" "))))
ans = []
temp = 0
for i in range(n - 1):
  count = False
  for j in range(i + 1, n):
    if a[i] == -1:
      break
    else:
      if a[i] == a[j]:
        count = True
      if a[j] % a[i] == 0:
        a[j] = -1

  else:
    if i != len(a) - 1:
      ans.append(a[i])
    if count:
      temp += 1
if a[-1] != -1:
  temp -= 1
print(len(ans) - temp)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    nn = int(input())
    a = {}
    exists = set()
    for i,aa in enumerate(map(int, input().split())):
        if aa not in a:
            a[aa] = i
        else:
            exists.add(aa)
    ans = 0
    for n in a.keys():
        for div in range(1, int(n**0.5)+1):
            if n in exists:
                break
            if n % div == 0:
                dd = n // div
                if dd != 1 and div in a:
                    break
                if dd != n and dd in a:
                    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()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

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
m = [0] * MAX
t = set()
for i in range(n):
  m[a[i]] += 1
  if m[a[i]] == 1:
    t.add(a[i])
  elif m[a[i]] == 2:
    t.discard(a[i])
#print(m[:30])
mx = max(a)
ans = 0
tlen = len(t)
for idx in range(tlen):
  i = t.pop()
  #if m[i] != 1:
    #continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


def henkan(LIST):
    ANS=[LIST[i] for i in range(len(LIST)) if not LIST[i] % LIST[0] == 0]
    return ANS
cnt=0
check=0
for i in range(10**9):
    cnt+=1
    l=len(A)
    if l>=1:
        if l>=2:
            if A[0]==A[1]:
                check+=1
        A=henkan(A)
    elif l==0:
        print(cnt-check-1)
        exit()

Submission status: Time Limit Exceeded

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

for ai in range(N):
    cnt = 0
    for aj in range(N):
        if ai == aj:
            continue
        if A[ai] % A[aj] != 0:
            cnt += 1
        else:
            break
    if cnt == N-1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

a = sorted(a)
b = copy.deepcopy(a)

max_a = a[n-1]
min_a = a[0]

cnt = 0

for i in a:
  tmp = 0
  
  for j in b:
    if i == j and tmp == 1:
      cnt += 1
      break
    elif i == j and tmp == 0:
      tmp += 1
      continue
    elif i % j == 0:
      cnt += 1
      b.remove(i)
      break

print(n - cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = deque(sorted(a))
    ans = []
    S = True
    while len(A)>0:
        rem = []
        L = A.popleft()
        for i in A:
            if i == L:
                S = False
            if i%L == 0:
                rem.append(i)
        for r in rem:
            A.remove(r)
        if S:
            ans.append(L)
        S = True
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def divisor(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 set(divisors)


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 0

for i,num in enumerate(A):
    if i > 0 and A[i-1] == num:
        continue
    if not divisor(num) & set(A[i+1:]):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

l = [int(x) for x in input().split()]
l.sort()
mp = [1]*n

for i in range(n):
    for j in range(i+1,n):
        if(mp[j]==0):
            continue
        if(l[j]==l[i]):
            mp[i] = 0
            mp[j] = 0
            continue
        if(l[j]%l[i]==0):
            mp[j] = 0
            continue

print(sum(mp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)

    hurui = [1] * len(A)
    prev = 0
    for i, a in enumerate(A):
        if a == prev:
            hurui[i-1] = 0
            hurui[i] = 0
            prev = a
            continue
        if i == len(A)-1:
            prev = a
            continue
        if hurui[i] == 0:
            prev = a
            continue
        for j, b in enumerate(A[i+1:]):
            if hurui[i+1+j]==0:
                prev = a
                continue
            if b % a == 0:
                hurui[i+1+j] = 0
            prev = a
    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

ans = 0
count = 0

num_list.sort()

for index_1, num_1 in enumerate(num_list):
  for index_2, num_2 in enumerate(num_list):
    if index_1 != index_2:
      if num_1 % num_2 == 0:
        break
      else:
        count += 1
  
  if count == n - 1:
    ans += 1

  count = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
while len(A)>1:
    p = A[0]
    if A[0] != A[1]:
        A = [j for j in A if j % p !=0]
        ans += 1
    else:
        A = [j for j in A if j % p !=0]
if len(A)==1:
    print(ans+1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
p=[[] for i in range(n)]
ans=n

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(n):
    p[i]+=make_divisors(a[i])

#print(p)
#print(a)
dp=[0]*n
for i in range(len(a)):
    for j in range(n):
        if i!=j:
            if a[i] in p[j] and dp[j]!=1:
                dp[j]=1
                #print(a[i],p[j],dp)
print(dp.count(0))

Submission status: Time Limit Exceeded

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

print(l.count(0))

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):
  a = 0
  if i<N-1:
    if A[i] == A[i+1]:
      a = 1
  for j in range(i):
    if A[i] % A[j] == 0:
      a = 1
  if a == 0:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
len = len(A)
cnt = 0
for i in A:
  cnt += 1
  cnt2 = 0
  for j in A:
    cnt2 += 1
    if cnt != cnt2 and i%j == 0:
      len =len - 1
      break
print(len)

Submission status: Time Limit Exceeded

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

als = sorted(al)
m = als[-1]

from collections import Counter
c = Counter(als)

res = 0
kouho =[]
for i in range(n):
    j = als[i]
    if c[j] >1:
        kouho.append(j)
        pass
    else:
        for k in kouho:
            if j % k ==0:
                break
        else:
            res += 1
            kouho.append(j)
            continue
print(res)

Submission status: Time Limit Exceeded

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

A.sort()
A_set = set(A)
count = 0
last_num = 0
flag = True
now_num = 0
half_num = 0
count_flag = False

if A.count(1) == 1:
    print(1)
    exit()
for i in range(N):
    count_flag = True
    now_num = A[i]
    half_num = A[i]/2
    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:
        for j in range(0, i):
            if A[j] > half_num:
                break
            if now_num % A[j] == 0:
                count_flag = False
                break
        if count_flag:
            if not flag:
                flag = True
            count += 1
        last_num = A[i]
print(count)

Submission status: Time Limit Exceeded

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

if n == 1:
  print(1)
else:
  i = 0
  ans = 0
  for _ in range(n):
    count = 1
    for j in range(i):
      if a_list[i] % a_list[j] == 0:
        if i < n/2:
          del a_list[i]
          i -= 1
        count = 0
        break
    if count == 1:
      if i == len(a_list)-1:
        ans += 1
      elif a_list[i] != a_list[i+1]:
        ans += 1
    i += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bc
from collections import defaultdict
from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
q = set([i for i in range(N)])
 
for i in range(N):
    ai = A[i]
    itr = list(q)
    for j in itr:
        if j == i:
            continue
        if A[j] % ai == 0:
            q.remove(j)
 
print(len(q))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1


def factorList(n):
    # [素因数]=数を出力
    f = {}
    c = 0
    r = int(n**0.5)
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            f[i] = c
            c = 0
    if n != 1:
        f[n] = 1
    return f


def cmb(a, i, h, t):
    if i >= len(a):
        return h[t]
    for j in range(a[i][1]+1):
        d = cmb(a, i+1, h, t*pow(a[i][0], j))
        if d:
            return True
    return False


h = [False]*(10**6+1)
ans = 0
for n, c in a:
    if c == 1:
        fl = [[k, v] for k, v in factorList(n).items()]
        if not cmb(fl, 0, h, 1):
            ans += 1
    h[n] = True

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

for i in range(n):
    flag=True
    for j in range(n):
        if(((a[i]%a[j]) == 0) and (i != j)):
            flag=False
    if(flag == True):
        x += 1
print(x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int, input().split()))
a = 0
for i in li:
    li1 = list(li)
    li1.remove(i)
    if all(i % j != 0 for j in li1):
        a += 1
print(a)

Submission status: Time Limit Exceeded

Solution code:
import collections
N=int(input())
Ain=list(map(int,input().split())) 
ain=collections.Counter(Ain)
ansn=0
A=set(Ain)
A=list(A)
A.sort()
A2=list(t for t in A)


ans=[]
while len(A2)!=0:
    ans.append(A2[0])
    templist=[]
    for j in range(len(A2)):
        if A2[j]%A2[0]==0:
            templist.append(j)
    for s in reversed(templist):
        del A2[s]

for anss in ans:
    if ain[anss]==1:
        ansn+=1
print(ansn)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    # 約数
    N = ir()
    A = lr()
    A.sort()
    answer = 0
    bl = [0] * (10**6+1)

    def make_divisors(n):  # 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, a in enumerate(A):
        if i < N-1 and a == A[i+1]:
            bl[a] = 1
            continue
        divs = make_divisors(a)
        flag = True
        for x in divs:
            if bl[x] == 1:
                flag = False
                break
        bl[a] = 1
        if flag:
            answer += 1

    print(answer)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input(): return sys.stdin.readline()

n=int(input())
a=np.array(list(map(int,input().split())))
 
ans=0
#print(a%(np.array([a for _ in range(n)])).transpose())
 
for A in a:
  b=A%a==0
  #print(b)
  if np.count_nonzero(b)==1:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = [int(i) for i in input().split()]
A_set = set(A_list)


A_list.sort()
ans_list = []
remove_list = []

while len(A_list) != 0:
    flag = 0
    remove_list = []
    x = A_list.pop(0)
    count = 0 #削除する回数
    for a in A_list:
        if a == x:
            remove_list.append(a)
            flag = 1 #アペンドしないフラグ    
        else:
            pass
    
        if a % x == 0:
            remove_list.append(a)
        else:
            pass

    if flag == 1:
        pass
    else:
        ans_list.append(x)

    for rem in remove_list:
        while rem in A_list:
            A_list.remove(rem)


#print(ans_list)
print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()
from bisect import bisect_left
while True:
    v = a[0]
    if v*2>a[-1]:
        for item in a:
            tmp.add(item)
        break
    tmp.add(v)
#     na = []
#     ii = bisect_left(a, v*2)
#     for 
    a = [item for item in a if item%v!=0]
    if not a:
        break

# tmp = [a[0]]
# for i in range(1, n):
#     num = a[i]
# #     for i in range(len(tmp)-1, -1, -1):
#     for i in range(len(tmp)):
#         item = tmp[i]
#         if num%item==0:
#             break
#         if item*2>num:
#             tmp.append(num)
#             break
#     else:
#         tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

Submission status: Time Limit Exceeded

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

for a in A:
  count = 0
  for b in A:
    if a % b  == 0:
      count += 1
  if count == 1:
    count2 += 1
    
print(count2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
import copy
A_list_2 = copy.deepcopy(A_list)



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
  
  
count = 0
and_ = []
a =[]


for i in range(N):
  #約数
  A_list = copy.deepcopy(A_list_2)
  #print(A_list)
  a = make_divisors(A_list[i])
  #a.pop(len(a)-1)
  #約数とA_listの共通点
  A_list.pop(i)
  and_ = list(set(A_list) & set(a))
  #共通がなかったら(len==0)割り切れない
  if(len(and_)==0):
    count += 1
    #print(i,a,and_)
    
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i in range(N)])
#A = list(set(A))
A = sorted(A)#わるほう

kouho = list(A.copy())#わられるほう
target = list(set(A))
#print(A)

for i in range(1,len(kouho)):
    if (kouho[max(0,i-1)]==kouho[i]):
        if kouho[i] in target:
            target.remove(kouho[i])
            
kouho = sorted(list(target.copy()))

for i in range(len(A)):
    for j in range(0, len(target)):
        if target[j] <= A[i]:
            continue
        elif  target[j] in kouho:
            if target[j] % A[i] == 0:
                #print(target[j], A[i])
                kouho.remove(target[j])
    target = list(kouho.copy())
        
print(len(target))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = (list(map(int, input().split(' '))))
D = {}
ans = 0
for i in A:
    if i in D:
        D[i] += 1
    else:
        D[i] = 1
for i in A:
    flg = True
    if D[i] > 1:
        continue
    for j in range(1,int(pow(i,0.5))+2):
        if not i%j:
            if j in D and i != j:
                flg = False
                break
            if j != i//j and i//j in D and i//j != i:
                    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()))
A.sort()
B=[]
for i in range(N-1):
    if A[i]==A[i+1]:
        B.append(A[i])
L=len(A)
for i in range(L):
    if i<len(A):
        j=i+1
        while j<=len(A)-1:
            if A[j]%A[i]==0:
                A.remove(A[j])
            else:
                j+=1
C=set(A) & set(B)
print(len(A)-len(C))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

num = 0
t_2 = False
t_3 = False
t_5 = False
t_7 = False

for i in range(N):
    flag = True

    if t_2 == True:
        if A[i] % 2 == 0:
            flag = False
    if t_3 == True:
        if A[i] % 3 == 0:
            flag = False
    if t_5 == True:
        if A[i] % 5 == 0:
            flag = False
    if t_7 == True:
        if A[i] % 7 == 0:
            flag = False

    if flag == True:
        for j in range(N):
            if A[i] % A[j] == 0 and i != j:
                flag = False
                break

    if A[i] == 2:
        t_2 = True
    elif A[i] == 3:
        t_3 = True
    elif A[i] == 5:
        t_5 = True
    elif A[i] == 7:
        t_7 == True

    if flag == True:
        num += 1

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

cou = Counter(A) 

A = list(set(A))
A.sort()

C = [A[0]]
for i in range(1, len(A)):
    Flag = True
    for c in C:
        if A[i] % c == 0:
            Flag = False
            break
    if Flag == True:
        C.append(A[i])

ans = 0
for i in C:
    if cou[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve(Auniq, Ai):
  for x in Auniq:
    if Ai % x == 0:
      return False
  return True

def main():
  N = int(input())
  A = list(map(int, input().split()))
  Auniq = Counter(A)
  res = 0
  for k, v in zip(Auniq.keys(), Auniq.values()):
    if v == 1:
      Aless = list(filter(lambda x: x < k, Auniq.keys()))
      if len(Aless) == 0:
        res += 1
      else:
        res += solve(set(Aless), k)
  return res

print(main())

Submission status: Time Limit Exceeded

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

N=int(input().rstrip('\n'))
As=[int(x) for x in input().rstrip('\n').split()]
As2 = sorted(As)
res = 0
for i in range(N):
  if len(As2)>0:
    now = As2[0]
    As2=[x for x in As2 if x%now!=0]
    if As.count(now)==1:
      res += 1
  else:
    break
print(res)