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 main():
    from builtins import int, map, list, print, len
    from collections import deque
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = (lambda: (sys.stdin.readline()).rstrip())
    input_list = (lambda: input().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N = input_number()
    A = input_number_list()
    A.sort()
    A = deque(A)
    bool_ls = [True for i in range(len(A))]
    for i in range(len(A)):
        if not bool_ls[i]:
            if A[i] == A[i - 1]:
                bool_ls[i - 1] = False
            continue
        for j in range(i + 1, len(A)):
            if A[j] % A[i] == 0:
                bool_ls[j] = False

    print(bool_ls.count(True))
    # print(bool_ls)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in A:
        y[i] += 1

    ans = 0
    for i in A:
        for j in range(1,int(math.sqrt(i)) + 1):
            if j == i and y[i] <= 1: continue
            if j == 1:
                if y[1]: break
                if y[i] > 1 : break
            else:
                if i % j == 0 and (y[j] or y[i//j]):
                    break
        else:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    AList = list(map(int, input().split()))

    answer = 0

    for i in range(N):

        for j in range(N):

            if((i != j) and AList[i] % AList[j] == 0):
                break

        else:
            answer = answer + 1

    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
list = list(map(int, input().split()))
num = 0
for i in range(n):
    check = []
    for j in range(n):
        if i == j :
            continue
        b = list[i] % list[j]
        if not b == 0 :
            continue
        else:
            check.append(b)
    if not 0 in check :
        num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
A = sorted(A)
cnt = [0] * (10**6 + 1)
for a in A: cnt[a] += 1
checked = [True] * N
ans = 0
for i, a in enumerate(A):
    if not checked[i]: continue
    flag = True
    for j in range(i+1, N):
        if A[j] % a == 0:
            checked[j] = False
            if A[j] == a: flag = False
    if flag: ans += 1 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
for j in a:
    a = list(filter(lambda x: x%j >0,a)) + [j]*(a.count(j)==1)
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
# from numba import jit

def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    seen = Counter()
    
    
    for x in L:
        seen[x]+=1
    
    def loop():
        ans=0
        for x in L:
            if seen[x]>1 or x!=1 and 1 in seen:
                continue
        
            tmp=2
            while tmp**2<=x:
                if x%tmp==0 and (tmp in seen or x/tmp in seen):
                    break
                tmp+=1
            else:
                ans+=1
        return ans
    print(loop())
# print(ans)
    
if '__main__' == __name__:
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
a = list(map(int, input().split()))
k = [0] * n
cnt = 0
for i in range(n):
    for j in range(i):
        if i == j:
            continue
        if k[i] == 0 and a[i] % a[j] == 0:
            cnt += 1
            k[i] = 1
        if k[j] == 0 and a[j] % a[i] == 0:
            cnt += 1
            k[j] = 1
print(n - cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = []
for i in range(1000):
    t.append([])
for i in range(n):
    j = a[i]//1024
    t[j].append(a[i])
#print(t)
p = n
for i in range(len(t[0])):
    for j in range(len(t[0])):
        if(i != j):
            if(t[0][i] % t[0][j] == 0):
                p -= 1
                #print(t[0][i],t[0][j])
                break
for i in range(1,1000):
    for j in range(len(t[i])):
        x = 0
        for k in range(len(t[i])):
            if(j != k):
                if(t[i][j] ==  t[i][k]):
                    p -= 1
                    #print(t[i][j],t[i][k],-1)
                    x = 1
                    break
        if(x == 0):
            for k in range((i+2)//2):
                for l in range(len(t[k])):
                    if(t[i][j] % t[k][l] == 0):
                        p -= 1
                        #print(t[i][j],t[k][l])
                        x = 1
                        break
                if(x == 1):
                    break

print(p)

Submission status: Time Limit Exceeded

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


B = sorted(A)
#print(A)
C = []
last = -1
for i in range(N):
    if(last != B[i]):
        C.append(B[i])
        last = B[i]
    else:
        if(len(C)>0):
            del C[-1]



l = []
for e in C:
    status = True
    for p in l:
        if(e % p == 0):
            status = False
    if(status):
        l.append(e)
print(len(l))

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    al = [0]*(max(a)+1)
    for i in a:
        na = i
        if al[i] > 0:
            al[na] += 1
            continue
        while na <= max(a):
            al[na] += 1
            na += i

    ans = 0
    for i in a:
        if al[i] == 1:
            ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from queue import deque
readline = sys.stdin.buffer.readline
from collections import Counter
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():
    N = gete(int)
    A = list(geta(int))

    tbl = [0 for _ in range(10**6 + 1)]

    for a in A:
        for i in range(a, 10**6 + 1, a):
            tbl[i] += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import math
import collections
import bisect
#import sympy


def divisor(n):
    i = 1
    lower_divisors, upper_divisors = [], []
    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()

ans = 0
ans = N
Set = set()
for i in range(N):
    divs = divisor(A[i])
    # print(divs)
    if i != 0:
        Set.add(A[i - 1])
    if i < N - 1:
        if A[i] == A[i + 1]:
            ans -= 1
            continue

    for d in divs:
        if i != 0:
            if d in Set:
                ans -= 1
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().rstrip().split()]
done=[False for i in range(n)]
if n%2==0:
  for i in range(n//2):
    if done[i]==True:
      continue
    for j in range(i+1,n):
      if done[j]==True:
        continue
      if a[i]%a[j]==0:
        done[i]=True

      if a[j]%a[i]==0:
        done[j]=True

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

      if a[j]%a[i]==0:
        done[j]=True
else:
  for i in range(n//2):
    if done[i]==True:
      continue
    for j in range(i+1,n):
      if done[j]==True:
        continue
      if a[i]%a[j]==0:
        done[i]=True

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

      if a[j]%a[i]==0:
        done[j]=True
    
  
print(done.count(False))

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 = sorted(list(set(A)))

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

for i in range(len(A)):
    if target == []:
        break
    maxN = int(max(target)/A[i])
    for n in range(2,maxN+1):
        if A[i]*n in kouho:
            kouho.remove(A[i]*n)
            #print(A[i]*n)
    target = list(kouho.copy())
        
print(len(target))

Submission status: Time Limit Exceeded

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

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

A.sort()
ans = 0

div_set = set([])


def div(x):
    for i in range(1, int(sqrt(x)) + 1):
        if x % i == 0:
            if i in div_set or (x // i) in div_set:
                div_set.add(x)
                return False
    div_set.add(x)
    return True


for i in range(n - 1):
    if A[i] in div_set:
        continue
    elif A[i] == A[i + 1]:
        div_set.add(A[i])
        continue
    elif div(A[i]):
        ans += 1

if div(A[n - 1]):
    ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


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

    # divisors.sort()
    return divisors


N = int(input())
A = list(map(int, input().split()))
setA = set(A)
countA = Counter(A)
if countA[1] == 1:
    print(1)
    exit()

minA = min(A)

count = 0
for num in A:
    if countA[num] >= 2:
        continue
    divisors = make_divisors(minA, num)
    # print(num, divisors)
    if any((e in setA) for e in divisors):
        continue
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

for i in range(N):
    B = [b for b in B if b % A[i] != 0 or b == A[i]]

C = Counter(B)
B_filtered = [val for val in C if C[val] == 1]

print(len(B_filtered))

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    mylist.sort(reverse = True)
    mylist = tuple(mylist)

    if mylist[n-1] in mylist[:n-1]:
        result = 0
    else:
        result = 1
    for i in range(n-1):
        temp = mylist[i]
        if mylist.count(temp) <= 1:
            divide = True
            for j in range(i+1,n):
                if temp % mylist[j] == 0:
                    divide = False
                    break
            if divide:
                result += 1
    print(result)

main()

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
c = collections.Counter(A)
cnt = 0
for i in range(len(A)):
    if i == len(A) - 1:
        if c[A[i]] == 1:
            cnt += 1
    else:
        if c[A[i]] > 1:
            continue
        divide_flag = 0
        for j in range(i+1, len(A)):
            if A[i] % A[j] == 0:
                divide_flag = 1
                break
        if divide_flag == 0:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import Counter

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

def make_divisors(n, d):
    lower_divisors , upper_divisors = [], []
    i = 2
    while i*i <= n:
        if n % i == 0:
            if d[i] > 0:
              return True
            if i != n // i and d[n//i] > 0:
                return True
        i += 1
    return False

a=int(input())
b=[int(x) for x in input().split()]
b=sorted(b)
d=Counter(b)
c=0
if d[1] > 1:
  print(0)
elif d[1] > 0:
  print(1)
else:
  for i in range(0, a):
    if d[b[i]] > 1:
      c+=1
    elif not is_prime(b[i]):
      if make_divisors(b[i], d):
        c+=1
  print(a-c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
A = sorted(A)
checked = [True] * N
ans = 0
for i, a in enumerate(A):
    if not checked[i]: continue
    flag = True
    for j in range(i+1, N):
        if A[j] % a == 0:
            checked[j] = False
            if A[j] == a: flag = False
    if flag: ans += 1 
print(ans)

Submission status: Time Limit Exceeded

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

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

from copy import deepcopy
b = deepcopy(a)

for i in range(n):
    for j in range(n):
        if a[j]%a[i]==0:
            if not j==i:
                if a[j] in b:
                    b.remove(a[j])

print(len(b))

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
    b = []
    for i in range(n):
      flag = True
      for x in b:
        if a[i] % x == 0:
          flag = False
          break
      if flag:
        for k in range(n):
          if i != k and a[i] % a[k] == 0:
            flag = False
            break
      if flag:
        count += 1
        b.append(a[i])
    print(count)
  
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ns = list(map(int, input().split()))
ans = 0
from collections import Counter
c = Counter(ns)
dubbles = set([key for key, value in c.items() if value >= 2])
ns = sorted([i for i in ns if i not in dubbles])
n = len(ns)

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

for i in range(n):
    flag = True
    for j in make_divisors(ns[i]):
        if j in dubbles:
            flag = False
            break
    if flag:
        ans += 1
        dubbles.add(ns[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import time
import random


s = time.time()
def make_divisors_exist(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if exists[i]:
                if i != n:
                    return True
            #divisors.append(i)
            i2 = n // i
            if i != i2: # choufuku
                if exists[i2]:
                    if i2 != n:
                        return True
                #divisors.append(i2)

    # divisors.sort()
    #return divisors
    return False



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

out = 0

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

max_A = max(As)
exists = [False] * (max_A + 1)

timeover = False
for A in As:
    exists[A] = True

s = time.time()
random.shuffle(As)
for A1 in As:
    num = counter[A1]
    e = time.time()
    tdiff = e-s

    if tdiff >= 1.888:
        #print(tdiff)
        break

    if num >= 2:
        continue
    
    exist = make_divisors_exist(A1)

    if not exist:
        out += 1

print(out)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = list(map(int,input().split()))
flag=False
ans=0
for i,a in enumerate(A):
    flag=False
    for j,b in enumerate(A):
        if a%b==0 and i!=j:
            flag=True
    if flag==False:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
l=len(A)
ans=0
for i in range(l):
  if i>0 and A[i-1]==A[i]:
    continue
  flag=0
  for j in range(l):
    if i==j:
      continue
    if A[j] > A[i]:
      break
    if A[i]%A[j]==0:
      flag=1
      break
  if flag==0:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

l=[0]*N
n=0
for x in A:
    for i in range(N):
        if x%A[i]!=0:
            l[n]+=1
    n+=1

print(l.count(N-1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

nums = set()
used = set()
done = set()
ans = 0
for a in A:
    if a in used and a not in done:
        ans -= 1
        done.add(a)
    if make_divisors(a):
        if a not in used:
            ans += 1
            used.add(a)
    nums.add(a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


#nの約数列挙
def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  # sortされていない


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

a.sort()
a_max = a[-1]
div = [0]*(a_max+1)
c = Counter(a)
#print(c)
count = 0
already = []
for i in range(n):
    if c[a[i]] != 1:
        div[a[i]] = 1
        continue
    div_a = divisor(a[i])
    for j in div_a:
        if div[j] == 1:
            break
    else:
        count += 1
        div[a[i]] = 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
count=0
a.sort()
ans=0
while ans+count<N:
    if len(a)==1:
        ans+=1
        break
    b=[]
    p=a[0]
    flag=0
    if a[1]==a[0]:
        flag=1
        count+=1
    for i in range(1,len(a)):
        if a[i]%a[0]==0:
            count+=1
        else:
            b.append(a[i])
    if flag==0:
        ans+=1
    a=b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
import numpy as np
A.sort()
A = np.array(A)
x = []
while len(A) > 1:
    if A[0] != A[1]:
        x.append(A[0])
    A = A[A%A[0]!=0]
if len(A) == 1:
    x.append(A[0])
print(len(x))

Submission status: Time Limit Exceeded

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


a.sort()
a.append(10**6 + 1 )
count = 0
for i in range(n):
    flag = 0
    for j in range(i):
        if a[i]%a[j] == 0:
            flag += 1 
            break
    if flag == 0:
        if i == n or a[i] != a[i+1]:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))

for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x

ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

check = 0

for inum, i in enumerate(nlist[:]):
    for jnum, j in enumerate(nlist[:]):
        if inum != jnum:
            if i % j == 0:
                check += 1
                break


print(len(nlist) - check)

Submission status: Time Limit Exceeded

Solution code:
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input())):
n=int(raw_input())
l=[int(x) for x in raw_input().split()]
v=set()
l.sort(reverse=True)
d={}
ans=0
for i in range(n):
	if l[i] in d:
		d[l[i]]+=1
	else:
		d[l[i]]=1
if 1 in d:
	if d[1]>1:
		print(0)
	else:
		print(1)
	exit()

for i in range(n):
	c=0
	for j in range(n-1,-1,-1):
		if l[i]<l[j]:
			break
		if  i==j:
			continue
		if l[i]%l[j]==0:
			c=1
			#print(l[j],l[i])
			break
	if c==0:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

a.sort()
#print(a)

for i in range(n):
    flag = True
    for j in range(n):
        #print(i,j)
        
        if i == j:
            continue
        if a[i] < a[j]:
            break

        tmp = a[i]%a[j]
        #print(tmp)
        
        if tmp == 0:
            flag = False
            break
    if flag == True:
        count += 1
    
    flag = True

print(count)

Submission status: Time Limit Exceeded

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

for _ in range(N):
  for i in range(N):
    if _==i:
      if _==N-1 and i==N-1:
        break
      i=i+1
    if A[_]%A[i]==0:
      s=s+1
      break
  
print(N-s)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A_list = [int(i) for i in input().split()]
A_set = set(A_list)
A_list.sort()
A_list = deque(A_list)


ans_list = []
remove_list = []

while len(A_list) != 0:
    flag = 0
    remove_list = []
    x = A_list.popleft()
    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:
N = int(input())
A = list(map(int, input().split()))
count=0

for x in range(N):
    for y in range(N):
        if A[x]%A[y]==0 and x!=y:
            break
    else:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_l = list(map(int, input().split()))
 
a_l.sort()
result_list=[]
while len(a_l)>1:
  a = a_l.pop(0)
#  print(f'a:{a}')
  if a != a_l[0]:
    result_list.append(a)
  tmp = []
  for _ in a_l:
    if _ % a != 0:
#      print(f'_:{_}')
      tmp.append(_)
  a_l = tmp
#print(result_list)
print(len(result_list)+ len(a_l))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import bisect

N = int(input())
cnt_A = Counter(map(int, input().split()))
keys = sorted(cnt_A.keys())
max_keys = max(keys)
flags = {key: True for key in keys}

for key in keys:
    if flags[key] is False:
        continue

    factor = 2
    while key * factor <= max_keys:
        idx = bisect.bisect(keys, key * factor)
        if keys[max(0, idx - 1)] == key * factor:
            del cnt_A[key * factor]
            flags[key * factor] = False
        factor += 1

print(sum([val if val == 1 else 0 for val in cnt_A.values()]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_str = []
a_str = input().split()
list = []
for i in a_str :
    a = int(i)
    list.append(a)
num = 0
for i in range(n):
    check = []
    for j in range(n):
        if i == j :
            continue
        b = list[i] % list[j]
        if not b == 0 :
            continue
        else:
            check.append(b)
    if not 0 in check :
        num += 1
print(num)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().strip().split()))
arr.append(0)
arr.sort()
arr.append(0)
count=0
s=set()
for i in range(1,n+1):
    if(arr[i]==arr[i-1] or arr[i]==arr[i+1]):
        s.add(arr[i])
    else:
        if(len(s)):
            crr=list(s)
            flag=0
            for j in range(len(s)):
                if(arr[i]%crr[j]==0):
                    flag=1
                    break
            if(flag==0):
                count=count+1
            s.add(arr[i])
        else:
            s.add(arr[i])
            count=count+1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nige = 0
re = 0

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

for i in l:
    for j in range(len(l)):
        if(i % l[j] == 0):
            nige += 1
    if(nige - 1 == 0):
        re += 1
    nige = 0
        
print(re)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
x=list(set(l))
x.sort()
ans=0
s=set()
for y in x: 
    if c[y]<2:
      memo=0
      for j in range(1,int(y**0.5)+1):
        if y%j == 0 :
          if y//j in s or j in s:
            memo-=1
            break
      if memo==0:
        ans+=1     
    s.add(y)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

c = 0
for i in range(n):
  c2 = 0
  for j in range(n):
    if a[i] % a[j] != 0:
      c2 += 1
  if c2 == n-1:
    c += 1
      
print(c)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

def test_func(now_A, div_list, div_len, reduce_flag, ans_num):
    for j in range(div_len):
        if now_A % div_list[j] == 0:
            if now_A == div_list[j]:
                ans_num -= reduce_flag     
            reduce_flag = 0
            break
    else:
        div_list.append(now_A)
        div_len += 1
        ans_num += 1
        reduce_flag = 1
    return div_list, div_len, reduce_flag, ans_num

A_list.sort()
div_list = [A_list[0]]
div_len = 1
ans_num = 1
reduce_flag = 1
for i in range(1, N):
    now_A = A_list[i]
    div_list, div_len, reduce_flag, ans_num = test_func(now_A, div_list, div_len, reduce_flag, ans_num)

print(ans_num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
import collections
import bisect
#import sympy


def divisor(n):
    i = 1
    lower_divisors, upper_divisors = [], []
    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()

ans = 0
ans = N
Set = set()
for i in range(N):
    divs = divisor(A[i])
    # print(divs)
    if i != 0:
        Set.add(A[i - 1])
    if i < N - 1:
        if A[i] == A[i + 1]:
            ans -= 1
            continue

    for d in divs:
        if i != 0:
            if d in Set:
                ans -= 1
                break
print(ans)

Submission status: Time Limit Exceeded

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


A.sort(reverse = True)
B = []

for n0 in A:
    
    for i in range(len(A)):
        i += 1
        if n0 <= A[-i]:
            break
        if n0 % A[-i] == 0:
            B.append(n0)
            break
for i in B:
    A.remove(i)
ans = 0
for num in A:
    if A.count(num) == 1:
        ans += 1

print(ans)