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

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

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

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

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

ans=0
for i in range(N):
    if dic[A[i]]>1:
        continue
    f=False
    div=make_divisors(A[i])
    for d in div:
        if d in dic:
            f=True
            break
    if f:
        continue
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

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

a.sort()

if a[0] != 1:
    a = np.array(a)

    i = 0

    while i < len(a):
        b = a / a[i]

        a = a[(b != b.astype(int)) | (b == 1)]

        i += 1

    u, counts = np.unique(a, return_counts=True)

    print(sum(counts == 1))

elif (len(a) > 1) and (a[0] == a[1]):
    print(0)
else:
    print(1)

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:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:40:26 2020

@author: Kei
"""



N = int(input())

A = []*N
cnt_list = [0]*N
A = list(map(int,input().split()))

cnt = 1

for i in range(0,N):
    cnt = 1
#    print("Ai = "+str(A[i]))
    for j in range(0,N):
        if (i == j):
            continue
        if(A[i]%A[j] == 0):
#            print(A[i]%A[j])
            cnt = 0
            continue
#    print("cnt = "+str(cnt))
    if(cnt >= 1):
        cnt_list[i] = 1


print(cnt_list.count(1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
results = []

while(A):
  a = A.pop(0)
  if a in A:
    A = [i for i in A if i!=a]
  else:
    results.append(a)
  A = [i for i in A if i%a!=0]
print(len(results))

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[[0 for _ in range(n)] for _ in range(n)]

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

cnt=0
for i in range(n):
    if 1 not in l[i]:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().strip().split()))
a.sort(reverse=True)
s = a.copy()
for i in a:
  mod = True
  for j in s:
    if i % j == 0 and i != j:
      mod = False
      s.remove(i)
      break

import collections
c = collections.Counter(s)
result = 0
for i in c:
  if c[i] == 1:
    result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted(tuple(map(int, input().split())))
if n ==1:
    print(1)
    exit()
if A[0] == 1:
    if A[1] == 1:
        print(0)
    else:
        print(1)
else:
    ans = []
    tyo = [0]
    for i in range(n):
        flag = True
        if A[i] == tyo[-1]:
            continue
        for x in ans:
            if A[i]%x == 0:
                flag = False
                break
        if not flag:
            continue


        if i<n-1:
            if A[i+1] == A[i]:
                tyo.append(A[i])
                continue
        ans.append(A[i])
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [False]*n
a.sort()
z = 0
for i,v in enumerate(a):
    if b[i]:
        continue
    for j in range(i+1,n):
        if a[j] == v:
            b[i] = True
            b[j] = True
        elif a[j] % v == 0:
            b[j] = True
print(b.count(False))

Submission status: Time Limit Exceeded

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

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

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

    count = 0
    while AArry:
        a = AArry.pop(0)
        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 numpy as np
from collections import Counter

n = int(input())
arr = np.array(list(map(int, input().split())))

arr.sort()
c = Counter(arr)

cnt = 0

while cnt < arr.shape[0]:
    arr = np.concatenate([np.array([arr[cnt]]), arr[np.where(arr % arr[cnt] != 0)[0]]])
    arr.sort()
    cnt += 1

result = set(arr) - {x for x, y in c.items() if y >= 2}

print(len(result))

Submission status: Time Limit Exceeded

Solution code:
import copy
import logging
# logging.basicConfig(level=logging.INFO)

N = int(input().strip())
A = sorted([int(x) for x in input().strip().split(" ")])
B = [1 for b in range(N)]

logging.info(f"{A=}")
for i, a in enumerate(A):
    logging.info(f"{i=}, {a=}")
    for j in range(i+1, N):
        logging.info(f"{j=}")
        if B[j] == 0:
            continue
        if A[j] % a == 0:
            B[j] = 0
            if a == A[j]:
                B[i] = 0
    logging.info(B)
print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ls = list(map(int,input().split()))
y = lambda x ,z:x%z
k = 0
new = [0]*n
for i in range(n):
    new[i] = list(map(lambda x ,z=ls[i]:x%z,ls))
di = list(map(list, (zip(*new))))
for j in range(n):
    if di[j].count(0) == 1:
        k += 1
print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
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 * i <= 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:
n = int(input())
a_list = list(map(int, input().split()))

sorted_a_list = sorted(a_list)

cnt = 0
for i in range(n):
    for j in range(min(i+2, n)):
        if i == j:
            continue            
        a = sorted_a_list[i]
        b = sorted_a_list[j]
        if a % b == 0:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()
while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0]==1:
    if n==1 or a[1]>1:
        print(1)
    else:
        print(0)
    exit(0)
seen = []
same = set()
ans = 0
pre = -1
flg = False
for i in a:
    if i==pre:
        if flg:
            same.add(i)
        continue
    pre = i
    flg = True
    for j in seen:
        if j*2>i:
            break
        if i%j==0:
            flg = False
            break
    if flg:
        ans += 1
        seen.append(i)
print(ans-len(same))

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
An = list(map(int, input().split()))
ok = [False] * N
ng = set()
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(ok)
    # check = np.delete(check, np.where(check == i))
    # check = check[check != i]
    # if len(check) > 0:
    #     ng = ng | set(check)
ok = list(ok)
print(ok.count(0))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    flg = 0
    for j in range(N):
        if (not i==j) and p[i]%p[j] == 0:
            flg=1
            break
    if flg==0:
        cnt += 1
print(cnt)

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=sorted(list(map(int,input().split())), reverse=True)
cnt=0
for i in a:
    if a.count(i)==1:
        l=make_divisors(i)
        if len(set(a) & set(l))==1:
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

count=n

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

print(count)

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

while True:
    v = a[0]
    if v*2>a[-1]:
        for item in a:
            tmp.add(item)
    tmp.add(v)
    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():
#         item = tmp[i]
#         if num%item==0:
#             break
#     else:
#         tmp.append(num)
tmp = set(tmp) - s
print(len(tmp))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

    count = 0

    a.sort()

    x =  list(itertools.combinations(a,2))

    ansList = []
    
    for i in range(len(x)):
        if x[i][1] % x[i][0] == 0 and not(x[i][1] in ansList):
            count += a.count(x[i][1])
            ansList.append(x[i][1])

    print(n - count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans=0
#print(a%(np.array([a for _ in range(n)])).transpose())

for i in range(n):
  b=a[i]%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(map(int,input().split()))
flag=0
cnt=0
for i in range(n):
    for j in range(n):
        if(i==j):
            continue
        if(a[i]%a[j]==0):
            cnt=cnt+1
            break
print(n-cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
npA = np.array(A)
dupA = [x for x in set(A) if A.count(x) > 1]
count = 0
for a in A:
    if a not in dupA:
        ret = np.mod(a, npA[npA < a])
        if np.all(ret > 0):
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

N=int(sys.stdin.readline())
A=list(map(int, sys.stdin.readline().split()))

A.sort()
ans=0

B=[1]*N

#print(A)
for i in range(N):
    if B[i] == 1:
        for j in range(1,N-i):
            if B[j+i]==1:
                if A[j+i]%A[i]==0:
                    B[j+i]=0
                    if A[i]==A[j+i]:
                        B[i]=0
    #print(B)

print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
p = list(map(int, input().split()))
count = 0
flag = False

for i in range(n):
    for j in range(n):
        if p[i] % p[j] == 0 and i != j:
            flag = True
            break
    if(flag == False):
        count += 1
    flag = False

print(count)

Submission status: Time Limit Exceeded

Solution code:

import glob
import os

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = int( self.input_data())
        A = list(map(int, self.input_data().split()))

        A_sorted = sorted(A)

        index = 0
        remove_list = [0]* (N+1)

        for index in range(0, N-1):
            if remove_list[index] == 1:
                continue
            for i in range(index+1, len(A_sorted)):
                if A_sorted[i] % A_sorted[index] == 0:
                    remove_list[i] = 1
            if A_sorted[index] == A_sorted[index+1]:
                remove_list[index] = 1

        count = 0
        for i in remove_list:
            count += (1 - i)
        print(str(count-1))


solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Time Limit Exceeded

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

cnt=0
ans=[]
ans_=[]
for a in A:
    for ans_idx in range(len(ans)+1):
        if ans_idx == len(ans):
            ans.append(a)
            ans_.append(a)
            break
            
        ans_temp=ans[ans_idx]
        if a % ans_temp == 0:
            if a in ans_:
                ans_.remove(a)
            break
        
print(len(ans_))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
counter = [0 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        else:
            if counter[i] > 0:
                continue
            else:
                if a[i] % a[j] == 0:
                    counter[i] += 1
print(counter.count(0))

Submission status: Time Limit Exceeded

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

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


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

    # divisors.sort()
    return divisors



for i in range(n):
    num_li[ai[i]] += 1

ans = 0
    
for i in range(n):
    if num_li[ai[i]] > 1:
        continue
    #print(ai[i])
    flag = True
    div = make_divisors(ai[i])
    #print(div)
    for j in range(len(div)):
        if div[j] == ai[i]:
            continue
        #print(div[j],div)
        if num_li[div[j]] > 0:
            flag = False
            break
    if flag == True:
        ans += 1
    #exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
lena = len(a)
a.sort(reverse=True)

tmp = [0] * lena

for i in range(lena):
    for j in range(i + 1, lena):
        if not (a[i] % a[j]):
            tmp[i] += 1
            if a[i] == a[j]:
                tmp[j] += 1
            break

ans = 0
for one in tmp:
    if not one:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
A= np.array(list(map(int,input().split())))
new_A = A
value_count=0
for i in range(N):
    Ai=A[i]
    test_A=Ai%A
    if(np.sum(test_A==0)==1):
        value_count+=1
print(value_count)

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

    count = 0
    while AArry:
        a = AArry.pop(0)
        AArry2 = copy.copy(AArry)
        flag = 0
        for i, v in enumerate(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 sys

input = sys.stdin.readline


def main():
    N = int(input())
    arr = list(map(int, input().split(" ")))
    cnt = 0
    for i in range(N):
        if sum([1 if ((i != j) and (arr[i] % arr[j] == 0)) else 0 for j in range(N)]) == 0:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    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:
import bisect

N = int(input())
a = list(map(int, input().split()))
yaku = [[] for _ in range(N)]
for i in range(N):
    for j in range(1, int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            yaku[i].append(j)
            if j != a[i] // j:
                yaku[i].append(a[i]//j)
asort = sorted(a)
cnt = 0

for i in range(N):
    cntF = True
    for j in yaku[i]:
        tmp = bisect.bisect_left(asort, j)
        if a[i] % asort[tmp] == 0:
            if tmp == N - 1:
                continue
            if a[i] == asort[tmp]:
                if asort[tmp] != asort[tmp + 1]:
                    continue
            cntF = False
            break
    if cntF:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.5)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

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()));
    
b = max(a);
c = min(a);
result = 0;

for p in range(c,b+1):
    d = a.count(p);
                
    if d == 1:
        pp = make_divisors(p);
        qq = len(pp);
        rr = 0;
        for q in range(qq-1):
            if a.count(pp[q]) >= 1:
                rr = 1;
                break;
        if rr == 0:
            result += 1;
        
print(result);

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    ava = [1]*n
    for i in range(n):
        for j in range(i+1,n):
            if i==j:    continue
            if ava[i]:
                if not a[i]%a[j]:
                    ava[i] = 0
            if ava[j]:
                if not a[j]%a[i]:
                    ava[j] = 0
    print(ava.count(1))
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
    
    FLG = True
    for j in A[i+1:]:
        if num % j == 0:
            FLG = False
            break
    if FLG:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.array(A)
num = 0
for i in range(N):
    flag = True
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            flag = False
            break
    if flag == True:
        num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
import math


def make_divisors(n):
    s = math.sqrt(n)
    i = int(s+1)
    while i >= 1:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i -= 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
    for item in make_divisors(val):
        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:
import numpy as np
N = int(input())
A = np.array(sorted(list(map(int,input().split()))))

if 1 in A:
  A = np.delete(A,np.where((A%1==0) & ((A!=1) | (2<=len(np.where(A==1)[0])))))
if 2 in A:
  A = np.delete(A,np.where((A%2==0) & ((A!=2) | (2<=len(np.where(A==2)[0])))))

for a in A:
  A = np.delete(A,np.where((A%a==0) & ((A!=a) | (2<=len(np.where(A==a)[0])))))

print(len(A))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int, input().split()))
c=0
x=0
A=sorted(a)
for i in range(N):
    if A[i] in (A[i+1:]):
        c +=0
    else:
        for j in (range(i)):
            if(A[i]%A[j]==0):
                c +=1
        if(c==0):
            x +=1
    c=0
print(x)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd, sqrt, cos, radians, pi
from collections import defaultdict as d
from itertools import combinations as c

def f(n):
	i = 1
	s = set()
	while i <= sqrt(n):
		if (n % i == 0):
			if (n / i == i):
				s.add(i)
			else:
				s.add(i)
				s.add(n//i)
		i = i + 1
	return s

n = int(input())
arr = list(map(int, input().split()))
dd = d(int)
for i in arr:
	dd[i] += 1
l = set(arr)
ans = n
for v in arr:
	s = f(v)
	s.remove(v)
	h = set(list(s)+list(l))
	if len(h) < len(s) + len(l) or dd[v]>1:ans-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections
sys.setrecursionlimit(10**6)


def main(input, print):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        if i > 0 and a[i] == a[i-1]:
            continue
        if i + 1 < n and a[i] == a[i+1]:
            continue
        isDiv = False
        for j in range(i):
            if i != j and a[i] % a[j] == 0:
                isDiv = True
                break
        if not isDiv:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
B = [True]*N
for i in range(N):
    for j in range(i+1,N):
        if A[i]%A[j]==0:
            B[i] = False
            if A[i]==A[j]:
              B[j] = False
count = 0
for i in range(N):
    if B[i]:
        count+=1
print(count)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    a.sort()
    if a.count(1) == 1:
        print(1)
        exit()
    elif a.count(1) >= 2:
        print(0)
        exit()
    
    cnt = 0
    d = set()
    ans = 0
    
    for num in a:
        if len(d) == 0:
            d.add(num)
        else:
            b = True
            for p in d:
                if num in d:
                    b = False
                    if cnt == 0:
                        cnt += 1
                        ans -= 1
                    break
                else:
                    cnt = 0
                    if num%p == 0:
                        b = False
                        break
            if b:
                d.add(num)
    
    print(ans + len(d))

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 resolve():
    from collections import Counter
    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()))

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

A.sort()
ans=0

if A[0]!=A[1]:
    ans=1

if A[0]==1 and A[1]==1:
    print(0)
    exit()

elif A[0]==1 and A[1]!=1:
    print(1)
    exit()

for i in range(1,N):
    if A[i]==A[i-1] or ((i!=N-1) and (A[i]==A[i+1])):            
        continue
    j = 1
    while j*j <= A[i]:
        if A[i] % j == 0:
            lower=j
            upper=A[i]//j
        if lower in A[0:i] or upper in A[0:i]:
            break
        j += 1
        if j*j>A[i]:
            ans+=1

print(ans)