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 = sorted(list(map(int,input().split())))

ans = 0
for i in range(len(a)):
    c = 1
    for j in range(len(a)):
        if i == j:
            continue
        elif a[i]%a[j] == 0:
            c = 0
            break
    ans += c

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import math
    N = int(input())
    A_list = [int(item) for item in input().split()]
    A_list.sort()

    cnt = 0

    while len(A_list) > 0:
        # print(A_list)
        cnt += 1
        temp = A_list[0]
        # print(temp)
        del A_list[0]

        is_same = False
        for item in A_list[:]:
            if item == temp:
                is_same = True
            if item % temp == 0:
                A_list.remove(item)
        
        if is_same:
            cnt -= 1

    print(cnt)




if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    ans=0
    for i in range(N):
        for j in range(N):
            if i != j and A[i]%A[j]==0:
                break
            elif j==N-1:
                ans+=1

    print(ans)


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 in range(len(a)):
    l=0
    for k in range(len(a)):
        if k!=i:
            if a[i]%a[k]!=0:
                l=l+1
    if l==n-1:
        ans=ans+1
print(ans)

Submission status: Time Limit Exceeded

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

count = 0
#
# for i in range(N):
#
#     for j in range(i+1, N):
#         if A[i] % A[j] == 0:
#             break
#         if j == N - 1:
#             count += 1
# if len(A) >= 2 and A[-1] != A[-2]:
#     count += 1

import itertools

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.array([int(x) for x in input().split()])
count = 0
for i in a:
    a_i = i%a
    if np.count_nonzero(a_i == 0)==1:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
numbers = [int(i) for i in input().split()]
b = 0
numbers = numbers[0:a]
for i in range(0, len(numbers)):
    for j in range(0, len(numbers)):
        if numbers[i]%numbers[j] == 0 and i != j:
            break
    else:
        b += 1
print(b)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
"""AtCoder Beginner Contest 170: D - Not Divisible
https://atcoder.jp/contests/abc170/tasks/abc170_d
"""


def main():
    N = int(input())
    As = list(map(int, input().split()))

    ans = set()
    for i in range(N):
        is_divisible = False
        for j in range(N):
            if i != j and As[i] % As[j] == 0:
                is_divisible = True
        # print('i({}):{}, j({}):{}'.format(i, As[i], j, As[j]))
        if not is_divisible:
            ans.add(i + 1)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input().rstrip().split(' ')

a=[]
for i in s:
        a.append(int(i))
    
count=n
for i in range(n):
    flag=False
    for j in range(n):
        if(i==j):
            continue
        if(a[i]%a[j]==0):
            flag=True
    if(flag):
        count-=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

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
    D=make_divisors(A[i])
    if len(set(D)&set(A[0:i]))==0:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

counter = Counter(A)

count = 0
for a in A:

    if counter[a] > 1:
        count += 1
        continue

    i = 1
    while i*i <= a:
        if a % i == 0:
            if i in A_set and i != a:
                count += 1
                break
            if i != a // i:
                if a // i in A_set and a // i != a:
                    count += 1
                    break
        i += 1
    
print(len(A) - count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby

input()
a = []
r = 0
for k, g in groupby(sorted(map(int, input().split()))):
  try:
    next(x for x in a if k % x == 0)
  except StopIteration:
    a.append(k)
    if len(list(g)) == 1:
      r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

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

INDEX = []

for i in range(N):
  index = np.where(A%A[i]==0)[0]
  for j in range(index.shape[0]):
    if index[j]!=i:
      INDEX.append(index[j])


print(N - len(np.unique(np.array(INDEX).flatten())))

Submission status: Time Limit Exceeded

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

from collections import Counter

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

dic = Counter(a)

ans = 0

memo = {}

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        for i in range(1, int(ai**0.5)+1):
            if ai % i == 0:
                d = i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break
                if i != ai // i:
                    d = ai // i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(N):
    tmp = True
    var = A.count(A[i])
    if var == 1:
        for j in range(i):
            if A[i] % A[j] == 0:
                tmp = False
                break
    else: 
        tmp = False
    if tmp: ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

data.sort()

count = 0
for n, d in enumerate(data):
#     print('total: {}'.format(d))
    if data.count(d) >1:
        continue
    if n <1:
        count += 1
        continue
    for div in set(data[:n]):
        if d % div == 0:
            break
    else:
#         print('part: {}'.format(d))
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

import collections


def divisors(n):
    res = set()
    for i in range(1, n + 1):
        if i * i > n:
            return res
        d, m = divmod(n, i)
        if m == 0:
            res.add(i)
            res.add(d)
    return res


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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=sorted(lmp())
b=[0]*n
for i in range(n):
    if i>=1:
        if a[i]==a[i-1]:
            b[i-1]=1
    if b[i]==0:
        x=a[i]
        for k in range(i+1,n):
            if b[k]==0:
                if a[k]%x==0:
                    b[k]=1

print(b.count(0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
n_list = [int(x) for x in input().split()]
counter_1 = 0
for i in range(n):
  counter_2 = 0
  if counter_2 == 1:
    
    break
  else:
    for j in range(n):
      if i == j:
        continue
      else:
        if n_list[i] % n_list[j] == 0:
          counter_2 += 1
  if counter_2 == 0:
    counter_1 += 1
print(counter_1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
from collections import Counter
c = Counter(A)
sorted_key = sorted(c.keys(),reverse=True)
res = [0]*len(sorted_key)
ans = 0
#print(sorted_key)
for i,key in enumerate(sorted_key):
    if c[key]>1:
        ans += c[sorted_key[i]]
        continue
    for j in range(len(sorted_key)-1, i, -1):
        #print(i,key,j,sorted_key[j])
        if (key/sorted_key[j]>=1) and (key%sorted_key[j])==0:
            res[i] = 1
            ans += c[sorted_key[i]]
            #print('===========',)
            break


#print('res', res)
#print(c)
'''ans = 0
for i,v in enumerate(sorted_key):
    if res[i]:
        ans += c[sorted_key[i]]
    else:
        if c[v] >1:
            ans += c[sorted_key[i]]'''
print(n-ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a_list=sorted(a_list, reverse=True)
before_num=0
for i in range(N) :
  if before_num!=a_list[i] :
    flag=True
    for j in reversed(range(i+1,N)) :
      if a_list[i]%a_list[j]==0  :
          flag=False
          break
    if flag :
      count+=1
  before_num=a_list[i]


print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 
N= int(input())
A = list(map(int, input().split()))
A.sort()
A = np.array(A)
i=0
while i < len(A):
    if i+1 < len(A) and A[i] == A[i+1]:
        A = np.concatenate([A[:i],A[i+1:][A[i+1:] % A[i]!=0]])
    else:
        A = np.concatenate([A[:i+1],A[i+1:][A[i+1:] % A[i]!=0]])
        i += 1
print(len(A))

Submission status: Time Limit Exceeded

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

for i in range(n):
  if i==0:
    if n>1 and a[0]==a[1]:
      ans-=1
    continue
  for j in range(i):
    if a[i]==a[i-1]:
      ans-=1
      break
    elif i<n-1:
      if a[i]==a[i+1]:
        ans-=1
        break
    if a[j]>a[i]/2:
      break
    if a[i]%a[j]==0:
      ans-=1
      break
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:


N = int(input())


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


A.sort()

s=0
for i in range(N):
    if i!=N-1:
        if A[i]==A[i+1]:
            s+=1
            continue
    if i!=0:
        if A[i]==A[i-1]:
            s+=1
            continue
    for j in range(i):
            if A[i] % A[j] == 0:
                s += 1
                break
            if A[i]<2*A[j]:
                break

print(N-s)

Submission status: Time Limit Exceeded

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

aes = sorted(aes)

# print(aes)

ans = [1] * n
i = 0
while i < n:
  if ans[i] == 0:
    i += 1
    continue
  j = i + 1
  while j < n:
    if aes[i + 1] == aes[i]:
      ans[i] = 0
    if aes[j] % aes[i] == 0:
      ans[j] = 0
    j += 1
  i += 1

print(sum(ans))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(n):
    x = a[i]
    f = 1
    for j in range(n):
        if i == j:
            continue
        if x%a[j]==0:
            f = 0
            break   
    if f:
        cnt += 1
        
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

ans = [a[0]]
double = []

for i in range(1, n):
    flag = True
    for j in ans:
        if a[i] == j:
            double.append(j)
            flag = False
            break
        if a[i] % j == 0:
            flag = False
            break
    if flag:
        ans.append(a[i])

for k in double:
    if k in ans:
        ans.remove(k)
print(len(ans))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    for j in range(N):
        if i != j and A[i] % A[j] == 0:
            break
        if i != j and A[j] >= A[i]:
            cnt += 1
            break
        if j == N-1:
            cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
length = int(input())
intList  = input().split()
intList = [int(x) for x in intList]

resultSet = set()
for i in range(length):
    cnt = 0
    for j in range(length):
        if i != j:
            if intList[i] % intList[j] != 0:
                cnt += 1
            else:
                break

    if cnt == length - 1:
        resultSet.add(i)

print(len(resultSet))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
i=0
temp=0
while i<len(a):
  if i<=len(a)-2:
    if a[i]==a[i+1]:
      temp=temp+1
  j=i+1
  while j<len(a):
    if a[j]%a[i]==0:
      del a[j]
    else:
      j=j+1
  i=i+1
print(len(a)-temp)

Submission status: Time Limit Exceeded

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

counter = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i]/a[j] == a[i]//a[j]:
            break
    else:
        counter += 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
    for j,a in enumerate(A):
        if i==j:
            continue
        elif a <= A[i] and A[i] % a ==0:
            ans +=1
            break
print(n-ans)

Submission status: Time Limit Exceeded

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

A = sorted(A, reverse= True)

posi = 0
Ja = A[0]
Kakutougi= [0]*N

for i in range (1, N):
	if A[i] == Ja:
		Kakutougi[i] = posi
	else:
		Kakutougi[i] = i
		Ja = A[i]
		posi = i

counter = N

for i in range (0, N):
	for j in range (Kakutougi[i]+1, N):
		if A[i]%A[j]==0:
			counter-=1
			break

print(counter)

Submission status: Time Limit Exceeded

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

j = 0
ans = deque()
while j <= N - 1:
    stock = deque()
    for i in range(N):
        # iとjが同じとき
        if (i == j):
            continue

        if (A[j] % A[i] != 0):
            stock.append(A[i])

    if (len(stock) == len(A) - 1):
        ans.append(j)
    j += 1

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    ans = np.ones(N,dtype=int)
    for i in range(N-1):
        for j in range(i+1,N):
            if A[i] % A[j] == 0:
                ans[i] = 0
                break
    for i in range(N-1):
        for j in range(i+1,N):
            if A[N-1 - i] % A[N-1 -j] == 0:
                ans[N-1 - i] = 0
                break
    print(sum(ans))
resolve()

Submission status: Time Limit Exceeded

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

a = sorted(a)
#print(a)
count = 0
while len(a)>=1:
    aa = a.pop(0)
    if len(a)>=1 and a[0] == aa:
        while a[0] == aa:
            a.pop(0)
            if len(a) == 0:
                break
        continue
    #print("after popped aa: ",a)
    #print("aa: ",aa)
    count += 1
    i = 0
    num = 0
    a_len = len(a)
    while num < a_len:
        if a[i] % aa == 0:
            #print("remove: ",a[i])
            a.remove(a[i])
            #print("a -> ",a)
            num += 1
        else:
            i += 1
            num += 1
        #print("i, num == ",i, num)
print(count)

Submission status: Time Limit Exceeded

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


count = 0

for i in range(N):
    qualify = 1
    for j in range(0, N):
        if i == j:
            continue
        if (A[i] % A[j]) == 0:
            qualify = 0
            break

    count += qualify


print(count)

Submission status: Time Limit Exceeded

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

#S = input()
#N = int(input())
#n = [list(map(int,input().split())) for i in range(N)]
#n, y = map(int, input().split())


N = int(input())

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

r = 0
for i in range(len(A)):
    t = False
    for j in range(len(A)-1,-1, -1):
        if (i == j):
            continue
        if ( A[i] % A[j] == 0):
            t = True
            break
    if not t:
        r = r + 1




print(r)

Submission status: Time Limit Exceeded

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