Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

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

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]
Ans = n
for i in range(len(a)):
    b = a[i]
    if a.count(b) >= 2:
        Ans = Ans - 1
    else:
        c = make_divisors(b)[:-1]
        for j in range(len(c)):
            if c[j] in a:
                Ans = Ans - 1
                break
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
a_list = list(map(int, input().split()))
flag_list = [1] * n
index_list = np.argsort(a_list)
min_no = 0
count = 0
for ind in index_list:
    if min_no == a_list[ind]:
        flag_list[index_list[count - 1]] = 0
    count += 1
    if flag_list[ind] == 0:
        continue
    for i in index_list[count:]:
        if flag_list[i] == 0:
            continue
        if a_list[i] % a_list[ind] == 0:
            flag_list[i] = 0
    min_no = a_list[ind]

print(sum(flag_list))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
ans=0
bb=[]
aa=np.array(a)
for i in range(n):
    b=[a[i]]*n
    bb.append(b)
bbb=np.array(bb)

ans=np.count_nonzero(aa%bbb==0 ,axis=0)
print(np.count_nonzero(ans==1))

Submission status: Time Limit Exceeded

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

a.sort()
b = []
c = 0
for i, v in enumerate(a):
    flag = True
    for j in b:          
        if v % j == 0:
            flag = False
            break
        elif v / 2 <= j:
            if a[i-1] == v:
                flag = False
            break
    if flag == True:
        b.append(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
     
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from time import time

def main():
    t = time()
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    ok = [1] * N

    A.sort()

    while len(A) != 0:
        head = A[0]
        if A.count(A[0]) >=2:
            while head in A: A.remove(head)
            continue
        ans += 1
        A.remove(head)
        A = [i for i in A if i % head != 0]


    print(ans)
    # tt=  time()
    # print(tt-t)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#ほかの数で割り切れない数が何個あるか
n=int(input())
l=list(map(int, input().split()))
import itertools
ch=list(range(0, n))
#とりあえず割り切れるかチェックしようぜ
fin= [0 for num in range(n)]
#print(fin)
for v in itertools.combinations(ch, 2):
  if l[v[0]]%l[v[1]]==0:
    fin[v[0]]+=1
  if l[v[1]]%l[v[0]]==0:
    fin[v[1]]+=1
print(fin.count(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
A = sorted(map(int, input().split()))
flags = {i: 0 for i in range(N)}

ans = []

for i in range(N):
    if flags[i]:
        continue

    x = A[i]
    for j in range(i+1, N):
        if flags[j]:
            continue
        y = A[j]
        if x == y:
            flags[i] = 1
            flags[j] = 1
        else:
            if y % x == 0:
                flags[j] = 1
#print(flags)
print(N-sum(flags.values()))

Submission status: Time Limit Exceeded

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

    ans = [0] * n
    for i in range(len(a) - 1):
        if ans[i] == 1:
            continue
        for j in range(i + 1, len(a)):
            if a[i] == a[j]:
                ans[i] = 1
                ans[j] = 1
            else:
                if a[j] % a[i] == 0:
                    ans[j] = 1
    print(n - sum(ans))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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
    if len(A)>=2:
        if A[0]==A[1]:
            check+=1
    A=henkan(A)
    if A==[]:
        print(cnt-check)
        exit()

Submission status: Time Limit Exceeded

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

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

count = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue

        if A[i] % A[j] == 0:
            break

    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

count = 0
import itertools

out = set()
for c in itertools.combinations(A, 2):
    big = max(c[0] ,c[1])
    small = min(c[0] ,c[1])
    if big % small == 0:
        out.add(big)
for a in A:
    if a not in out:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())
A = list(map(int,input().split()))
Count = 0
for i in A:
    List = map(lambda x: i % x,A)
    c = collections.Counter(List)
    if(c[0] == 1):
        Count += 1

print(str(Count))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def cc(v, pp):
	if v == pp[-1]:
		return False, -1
	#print(pp)		
	for p in pp:
		if v % p == 0:
			return False, 0
		#if v < 2*p:
		#	return True, 0
	return True, 0
			

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp)
		if tf:
			pp.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
l = int(input())
n = [int(i) for i in input().split()]

counter = 0

for i in range(l):
  for j in range(l):
    if i == j:
      pass
    elif n[i] % n[j] == 0:
      counter += 1
      break
    else:
      pass

print(l - counter)

Submission status: Time Limit Exceeded

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

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

l = [0]*1000001

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

from functools import lru_cache

@lru_cache(maxsize=None)
def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table

@lru_cache(maxsize=None)
def mySolve(n):
    flag = True
    da = divisor(a)
    for d in da:
        if d != a:
            if l[d] >= 1:
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    return flag

ans = 0
for a in A:
    if mySolve(a):
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        if i < n-1 and a[i] == a[i+1]:
            dic[a[i]] = 1
            continue
        flag = 1
        for e in dic:
            if a[i]%e == 0:
                flag = 0
                break
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, *A = map(int, read().split())
    A.sort()

    B = [True] * N
    for i in range(N):
        if not B[i]:
            continue
        if i < N - 1 and A[i + 1] == A[i]:
            B[i] = False
        for j in range(i + 1, N):
            if A[j] % A[i] == 0:
                B[j] = False

    print(B.count(True))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
l=list(map(int,input().split()))
l.sort(reverse=True)
count=0
for i in range(N):
    Frag=True
    if l.count(l[i])>=2:
        Frag = False
    for j in range(1,N-i):
        if l[i]%l[i+j]==0:
            Frag=False
            break
    if Frag==True:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def make_divisors(n):
    lower_divisors, upper_divisors = set(), set()
    tmp = 1
    while tmp * tmp <= n:
        if n % tmp == 0:
            lower_divisors.add(tmp)
            if tmp != n // tmp:
                upper_divisors.add(n // tmp)
        tmp += 1
    return lower_divisors | upper_divisors


n = int(input())
*A, = map(int, input().split())
A.sort()
setA = set(A)
cnt = 0
for i, a in enumerate(A):
    if bisect.bisect_right(A, a) - bisect.bisect_left(A, a) != 1:
        cnt += 1
        continue
    X = make_divisors(a)
    for x in X:
        if x != a and bisect.bisect_right(
                A, x, hi=i) - bisect.bisect_left(A, x, hi=i) != 0:
            cnt += 1
            break
print(n - cnt)

Submission status: Time Limit Exceeded

Solution code:
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
    a.sort()
    for i in range(n):
        v = a[i]
        if dic[v] > 1:
            continue
        lim = v//2 + 1
        f = True
        for j in range(i):
            if a[j] > lim:
                break
            if a[i] % a[j] == 0:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([ int(i) for i in input().strip().split(' ')])
B = [0] * N

for i in range(N):
    if B[i] != 0:
        continue
    for j in range(i+1, N):
        if A[i] == A[j]:
            B[i] = 1
            B[j] = 1
        elif A[j] % A[i] == 0:
            B[j] = 1
    if sum(B) == N:
        break

print(N - sum(B))

Submission status: Time Limit Exceeded

Solution code:
n =  int(input())
A = list(map(int,input().split()))
A.sort()
count = 0
if n == 1:
    pass
else:
    for i in range(len(A)):
        a = A[i]
        max_num =a//2+1
        end = False
        if i ==len(A)-1:
            if A[i]==A[i-1]:
                end = True
            for j in range(0, i):
                b = A[j]
                if end:
                    count = count +1
                    break
                elif max_num<b:
                    break
                elif a%b ==0:
                    count = count+1
                    break
        else:
            if A[i]==A[i-1] or A[i] ==A[i+1]:
                end = True
                if end == True and i==0:
                    count = count +1

            for j in range(0, i):
                b = A[j]
                if end:
                    count = count +1
                    break
                elif max_num<b:
                    break
                    
                elif a%b ==0:
                    count = count+1
                    break

print(n-count)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
import copy
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()))
ans = 0
for j in a:
    tmp = a.copy()
    tmp.remove(j)
    table_ = make_divisors(j)
    if not (set(tmp) & set(table_)):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

As.sort(reverse=True)
As = [A for A in As if As.count(A) == 1]

cnt = len(As)
for i in range(len(As)-1):
  for j in range(i+1,len(As)):
    if As[i] % As[j] == 0:
      cnt -= 1
      break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(n):
    f = True
    for j in range(n):
        if i == j:
            continue
        
        if A[i]%A[j] == 0:
            f = False
        
    if f:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#4問目
import math
N = int(input())
A = list(map(int, input().split()))
LCM_a = [0] * N
count = 0
for i in range(N):
    flag = True
    for j in range(N):
        if A[i] >= A[j] and i != j:
            if A[i] % A[j] == 0:
                flag = False
                break
    if flag == True:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))

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

def solve(n, a):
    counts = {}
    for item in a:
        if item not in counts:
            counts[item] = 0
        counts[item] += 1
    if 1 in counts:
        return 1 if counts[1] == 1 else 0
    items_in_a = set(a)
    result = 0
    for item in a:
        if counts[item] == 1:
            d = divisors(item)
            if len(items_in_a.intersection(d)) == 0:
                result += 1
    return result


if __name__ == "__main__":
    n = int_in()
    a = arr_in()
    out(solve(n, a))

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 = n
for i in range(len(cnt)):
    if cnt[i][1] != 1:
        ans -= cnt[i][1]
        continue
    for j in range(i):
        if cnt[i][0] % cnt[j][0] == 0:
            ans -= 1
            break
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
  count = 1
  del b[i]
  for j in range(n-1):
    if a[i] % b[j] == 0:
      count = 0
      break
  ans += count
  count = 1
  b = a.copy()
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int, input().split())))
k=n
cnt=0
fla=0
for i in range(n):
    k=len(a)
    fla=0
    for j in range(k-1,i,-1):
        if a[j]==a[i]:
            fla=1
        if a[j]%a[i]==0:
            a.remove(a[j])
            cnt+=1
    if fla==1:
        cnt+=1
print(n-cnt)

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 = []
        for i in range(1, num + 1):
            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
        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:
N = int(input())
A_list = list(map(int, input().split()))
#count = 0
ans=0
for i in range(N):
  count = 0
  for j in range(N):
    if((i!=j)and(A_list[i]%A_list[j]!=0)):
      count+=1
  #print(count)
  if(count == N-1):
    ans+=1
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = [int(x) for x in input().split()]
A.sort()
B = [True] * N
for i in range(N):
    if not B[i]: continue
    jr = bisect.bisect_right(A, A[i])
    if jr > i + 1:
        for jj in range(i, jr):
            B[jj] = False

    for a in range(2 * A[i], A[-1] + 1, A[i]):
        jl = bisect.bisect_left(A, a)
        jr = bisect.bisect_right(A, a)
        if A[jl] == a:
            for jj in range(jl, jr):
                B[jj] = False
print(B.count(True))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from math import sqrt
@lru_cache(maxsize=10**6)
def divisors(n):
    divisors = set()
    for i in range(1, int(sqrt(n))+1):
        q, r = divmod(n, i)
        if r == 0:
            divisors.add(i)
            divisors.add(q)
    return divisors

n, *A = map(int, open(0).read().split())
X = [0] * (max(A) + 1)
c = 0
for a in A:
    X[a] += 1
for a in A:
    X[a] -= 1
    c += all(X[b] == 0 for b in divisors(a))
    X[a] += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
flag_lst = [0]*N

for i in range(N):
    for j in range(N):
        if flag_lst[j] >= 2:
            pass
        else:
            if A[j] % A[i] == 0:
                flag_lst[j] += 1

res = 0
for flag in flag_lst:
    if flag == 1:
        res += 1

print(res)

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()))
cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

ret = 0

for val in a:
    is_ok = True
    if val in dup:
        continue
    divs = make_divisors(val)
    for item in divs:
        if item == val:
            continue
        elif item in cand:
            is_ok = False
            break
    if is_ok:
        ret += 1

print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

#f = open('./input_D.txt')

#N = int(f.readline())
#A = list(map(int, f.readline().split()))

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

A_array = np.array(A)
A_array = np.sort(A_array)
A_list = A_array.tolist()

cnt = 0

#while len(A_list)>1:
#    num = A_list.pop(0)
#    if num != A_list[0]:
#        cnt+=1
#    A_array = np.array(A_list)
##    len_mae = len(A_list)
#    A_amari = A_array%num
#    A_array = A_array[A_amari!=0]
#    A_list = A_array.tolist()
#
#if len(A_list) == 1:
#    cnt+=1
    
while len(A_array)>1:
    num = A_array[0]
#    A_array = A_array[1:]
    if num != A_array[1]:
        cnt+=1
#    A_array = np.array(A_list)
#    len_mae = len(A_list)
    A_amari = A_array%num
    A_array = A_array[A_amari!=0]
#    A_list = A_array.tolist()

if len(A_array) == 1:
    cnt+=1

print(cnt)

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()
    return divisors
N = int(input())
A = list(map(int, input().split()))
cm_b = {}
cm_a = {}
cm_b[-1] = set()
for i in range(N):
    cm_b[i] = cm_b[i-1] | set([A[i]])
cm_a[N] = set()
for i in range(N):
    cm_a[N-1-i] = cm_a[N-i] | set([A[N-1-i]])
cnt = 0
for i in range(N):
    s = set(make_divisors(A[i])) 
    if len(cm_a[i + 1] & s) == 0 and len(cm_b[i - 1] & s) == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

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

else:
    ans=0
    for i in d:
        p=1
        if d[i]>1:
            continue
        for j in range(2,int(i**0.5)+1):
            if i%j==0:
                if j in d or i//j in d:
                    p=0
                    break
        ans+=p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
setA=sorted(list(set(A)))
c=collections.Counter(A)
ANS=[]
d=c.most_common()
for i in d:
  if i[1]==1:
    ANS+=[i[0]]
ANS.sort()
ans=len(ANS)
for i in ANS:
  for k in setA:
    if i==k:
      break
    elif i%k==0:
      ans-=1
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

c = collections.Counter(a)

a.sort()

l = 0

while l < len(a) - 1:
    tmp = a[:l+1]
    r = l+1
    while r < len(a):
        if a[r] % a[l] != 0:
            tmp.append(a[r])
        r += 1
    a = tmp
    l += 1

tmp = []
for i in a:
    if c[i] > 1:
        pass
    else:
        tmp.append(i)
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    for i in range(n):
      count_temp = 0
      if not a[i] in a[:i]:
        for k in range(n):
          if i != k and a[i] % a[k] == 0:
              count_temp += 1
        if count_temp == 0:
          count += 1
    print(count)
  
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys
input = sys.stdin.buffer.readline

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

B = set(A)
A = list(B)
A.sort()
#print(A)
ans = 0

for i in reversed(range(len(B))):
    a = A[i]
    if L[a] != 1:
        continue
    jdg = 0
    index = bisect.bisect_right(A,a//2)
    #print(index,a)
    for k in range(index):
        if a % A[k] == 0:
            jdg += 1
            break
    if jdg == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n = int(input())
    a = np.array(list(map(int, input().split())))

    ans = 0
    tmp = np.array([0]*n)
    for i in range(n):
        tmp = np.array([a[i]]*n) % a
        if n - np.count_nonzero(tmp) == 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

# 昇順にする
g_data_list = list(map(int, input().split()))
data_list = sorted(g_data_list)

cnt = 0
for i in range(N):

	# 同じ数字
	if(data_list.count(data_list[i]) != 1):
		continue

	is_divide = False
	for j in range(i):
		# 割り切れる数がある
		if(data_list[i] % data_list[j] == 0):
			is_divide = True
			break
	if(not is_divide):
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a=sorted(a)
if 0 in a:
    ans=0
else:
    cnt=n
    for i in range(n):
        for j in range(n):
            if i==j:
                continue
            else:
                if a[i] % a[j] == 0:
                    cnt -= 1
                    break
    ans=cnt
print(ans)

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):
    Ai = A[i]
    hantei = True
    for j in range(max(i+1, N)):
        if i != j and Ai % A[j] == 0:
            hantei = False
            break
    if hantei:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf)
for i in li:
    isprime[i] = [True]
for i in range(len(li)):
    if i+1<len(li):
      if li[i] == li[i+1]:
        isprime[li[i]] = False
for i in li:
    #if not isprime[i]:
    #    continue
    for k in range(i+i, inf, i):
        isprime[k] = False
prime_list = []
for i in range(inf):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list =  list(map(int, input().split()))
N_list = [1 for x in range(N)]
A_list.sort()
for x in range(N):
    if N_list[x] ==1:
        for y in range(1,N-x):
            if A_list[x+y]%A_list[x] == 0:
                N_list[x+y] =0
            if A_list[x] == A_list[x+1]:
                N_list[x] =0
                N_list[x+1] =0
print(sum(N_list))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int, (input().split())))
A.sort()
cnt = np.zeros(10**6+10, dtype=np.int32)
for i in range(N):
    cnt[A[i]] += 1
for i in range(N-1):
    cnt[A[i]*2::A[i]] += 2
ans = np.count_nonzero(cnt==1)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
# print(a)
# print(n)
ans = [0 for _ in range(n)]


for i_out in range(n):
    for i_in in range(i_out+1, n):  #
        if a[i_out] == a[i_in]:
            ans[i_out] = 1
            ans[i_in] = 1

        if i_out == i_in:
            continue
        # print(i_out, i_in)
        if int(a[i_in] / a[i_out]) == a[i_in] / a[i_out]:
            ans[i_in] = 1
            # print('!')

# print(ans)
print(n - sum(ans))

Submission status: Time Limit Exceeded

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

remain = [1]*n
for i in range(n-1):
    if remain[i] == 0:
        continue
    for j in range(i+1, n):
        if remain[j] == 0:
            continue
        if a_l[i] == a_l[j]:
            remain[i] = 0
        if a_l[j]%a_l[i] == 0:
            remain[j] = 0

ans = [ i for i in range(n) if remain[i] == 1 ]
print(len(ans))

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()
forbidden = set([])
j = 0
count =0
while(j < len(ais)):
	
	if cc[ais[j]] == 1: 
		flag = True
		for d in range(1,int(ais[j] ** 0.5) +1):
			if ais[j] % d == 0:
				if (d in forbidden) or ((ais[j]/d) in forbidden) :
					flag = False
					break
		count +=1 if flag else 0
	forbidden.add(ais[j])
	j+=1

print count

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

A = sorted(A)

zyuhuku = [x for x in set(A) if A.count(x) > 1]

for i in range(len(A)):
  for j in range(i+1,len(A)):
    if A[j] != 0 and A[i] != 0:
      A[j] = 0 if A[j] % A[i] == 0 else A[j]
    
for z in zyuhuku:
  try:
    A.remove(z)
  except:
    pass

print(len([i for i in A if i > 0]))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
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():
    c = Counter(A)
    ret = 0
    set_A = set(A)
    for a in set_A:
        if 1 < c[a]:
            continue

        for d in make_divisors(a)[: -1]:
            if d in set_A:
                break
        else:
            ret += 1
    print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    solve()