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:
from  math import gcd
n = int(input())
a = sorted(list(map(int,input().split())))

l = []
l.append(a[0])
cou =[]
for i in range(1,n):
    b = a[i]
    for j in range(len(l)):
      if b==l[j]:
        cou.append(b)
      if b%l[j]==0:
          break
    else:
        l.append(b)
print(len(l)-len(set(cou)))

Submission status: Time Limit Exceeded

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

flg_l = [0 for i in range(n)]
ans = 0
for i,a in enumerate(A):
    for i2,a2 in enumerate(A):
        if i == i2:
            continue
        if a % a2 == 0:
            flg_l[i] = 1
            break
    if flg_l[i] == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n = int(input())
orga = list(map(int, input().split()))

if n==1:
    print(1)
    exit()
if len(set(orga)) == 1:
    print(0)
    exit()

import collections
c = collections.Counter(orga)
a=[]
for itm in c.items():
    num,cnt=itm
    if cnt==1:
        a.append(num)

aset=set(orga)

def m_div(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)
    divisors.remove(n)
    return divisors

ans=0
for num in a:
    divset=m_div(num)
    if len(divset & aset)==0:
        ans+=1

print(ans)

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

n = I()
l = LI()
c = 0
for a in range(n):
  for b in range(n):
    if a == b:
      continue
    if l[a] % l[b] == 0:
      break
  else:
    c += 1
  
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    A=sorted(list(map(int,input().split())))
    cnt=0
    temp=False

    for i in range(n):
        if A[i]!=0:
            val=A[i]
        if i+1<n and A[i+1]==val:
            cnt+=2
            if temp:
                cnt-=1
            temp=True
            continue
        else:
            temp=False
        for j in range(i+1,n):
            if A[j]!=0:
                if A[j]%val==0:
                    A[j]=0
                    cnt+=1
    print(n-cnt)

    
# 
resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

count = 0
for xi in x_list:
  if np.sum(xi%x_list==0) == 1:
      count += 1
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):
    hantei = True
    for j in range(n):
        if i == j: continue
        elif a[i] % a[j] == 0: 
            hantei = False
            break
    if hantei == True:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit, int32, int64
from numba.typed import Dict

@njit
def solve(B):
    A = Dict.empty(
        key_type=int64,
        value_type=int64)
    for b in B:
      A[b] = A.get(b, 0) + 1
    r = 0
    for a, v in A.items():
        if v > 1:
            continue
        if a > 1 and 1 in A:
            continue
        i = 2
        while i * i <= a:
            if a % i == 0:
                if i in A:
                    break
                if a // i in A:
                    break
            i += 1
        else:
            r += 1
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    return solve(A)

print(main())

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 A:
        if 1 < c[a]:
            continue
        divs = make_divisors(a)
        for d in divs[: -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()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

dic = Counter(a)

ans = 0

for ai in a:
    cnt = 0
    f = 1
    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

    ans += f

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import numpy as np
input = sys.stdin.readline

n=int(input())
C=list(map(int,input().split()))
A = np.array(sorted(C))
ans = 0
def mindrop(A):
    if len(A) ==1:
        global ans
        ans +=1

    elif len(A) !=1 and A[0] != A[1]:
        ans +=1

    B = A[A%A[0] !=0]
    return B

for i in range(20000):
    A = mindrop(A)
    if len(A) == 0:
        print(ans)
        sys.exit()

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)

# print(a)

tmp = [0] * lena

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

# print(tmp)
ans = 0
for one in tmp:
    if not one:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
input_line = list(map(int,input().split(' ')))

# ans_list = [0 for n in input_line]
ans = num

for i in range(num):
    for j in range(num):
        if(i!=j):
            if(input_line[i]%input_line[j]==0):
                ans-=1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def input():
    return sys.stdin.readline().strip()

def main():
    n = int(input())
    A = list(map(int, input().split()))
    count = 0
    ans = 0
    for i in A:
        for j in A:
            if i % j == 0:
                count += 1
                if count == 2:
                    count = 0
                    break
        if count == 1:
            ans += 1
        count = 0
    print(ans)
    


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]

from copy import copy

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))

result = 0

for i, a in enumerate(As):
    temp_list = copy(As)
    del temp_list[i]
    temp_set = set(temp_list)
    candidate = set(make_divisors(a))
    if len(candidate & temp_set) == 0:
        result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
a = list(map(int, input().split()))
a = np.sort(a)
count = 0
idxes = np.arange(len(a))
while len(idxes):
    idx = idxes[0]
    idxes = np.delete(idxes, 0)
    var = a[idx]
    amari = var % a
    if len(np.where(amari == 0)[0]) == 1:
        count += 1
    idxes = idxes[np.where(a[idxes] % var != 0)[0]]
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
check = [1 for _ in range(n)]
for i in range(n):
    if check[i] == 1:
        for j in range(n):
            if i != j:
                if arr[i] % arr[j] == 0:
                    check[i] = 0
                if arr[j] % arr[i] == 0:
                    check[j] = 0
print(check.count(1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
a = list(filter(lambda x: a.count(x) == 1, a))
# print(a)

res = []
for i in range(len(a)):
    if a[i] == 0:
        continue
    else:
        res.append(a[i])
    for j in range(i + 1, len(a)):
        if a[j] % a[i] == 0:
            a[j] = 0
print(len(res))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0
for i in range(n):
    t = a[i]
    f = True
    for j in range(n):
        if t>=a[j]:
            if i==j: continue
            if t%a[j]==0:
                f=False
                break
    if f: count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
flag_list = [False]*n
count = 0
for i in range(n):
    flag = True
    for j in range(i):
        if flag_list[j]:
            continue
        elif  (a[i]/a[j]).is_integer():
            flag = False
            flag_list[i] = True
            break
    if flag and i <= n-2 and a[i] == a[i+1]:
        flag = False
    if flag:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

n = int(input())

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

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

print(n-cnt)

Submission status: Time Limit Exceeded

Solution code:
input()
a = input().split()

L = 0
for n,i in enumerate(a):
    H = 0
    if "2" in a and i!="2" and int(i)%2 == 0:
        H=1
    elif "3" in a and i!="3" and int(i)%3 == 0:
        H=1
    elif "5" in a and i!="5" and int(i)%5 == 0:
        H=1
    else:
        for m,j in enumerate(a):
            if int(i) % int(j) == 0 and n != m:
                H = 1
                break
    if H == 0:
        L+=1
print(L)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = sorted(list(map(int, input().split())))
cnt = len(a_list)
for i in range(len(a_list)):
  val = a_list[i]
  ref_list = a_list[:i]
  if a_list.count(val) != 1:
      cnt -= 1
  else:
    for j in ref_list:
      if val % j != 0:
        continue
      else:
        cnt -= 1
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    A.sort()

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = set()
    ans = 0
    for i in range(1, N):
        a0 = A[i-1]

        for x in ax:
            if a0 % x == 0:
                break
        else:
            if a0 == A[i]:
                ax.add(a0)
                continue
            ax.add(a0)
            ans += 1

    a0 = A[-1]
    for x in ax:
        if a0 % x == 0:
            break
    else:
        ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N=int(input())
alist=list(map(int, input().split()))

alist.sort()
#print(alist)
if alist.count(alist[0])==1:
    ans=1
else:
    ans=0
for i in range(1,N):
    k=0
    a=alist[i]
    if alist.count(a)==1:
        for j in range(i):
            if a%alist[j]==0:
                k=1
                break
    else:
        continue
    if k==0:
        ans+=1
        #print('i=',i,'a=',a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()
    B = []
    sames = set()

    for a in A:
        isDividable = False
        for b in B:
            if a == b:
                sames.add(b)

            if a % b == 0:
                isDividable = True
                break

        if not isDividable:
            B.append(a)

    print(len(B) - len(sames))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# A_i/A_j False
num = int(input())
A = [int(x) for x in input().split()]
i = 0
result = 0
for i in range(num):
    devide = 0
    for j in range(num):
        if j == i:
            continue
        else:
            if (A[i]%A[j]==0):
                devide += 1
                break
    if (devide==0):
        result+=1
print(result)

Submission status: Time Limit Exceeded

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

for _ in range(N):
    x=A[0]
    A.pop(0)
    if not any(x%b==0 for b in A):
        i+=1
    A.append(x)

print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = set(i for i in range(n))
ans = [0]*n
warizai_index = set()

for i in range(n):
    for wari in warizai_index:
        if a[i]%a[wari] == 0 and i != wari:
            ans[i] = 1
            #b.remove(i)
            break
    if ans[i] == 1:
        continue
    
    #for j in b:
    for j in range(n):
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            #if i in b:
            #    b.remove(i)
            warizai_index.add(j)
            #b.remove(j)
            break

print(ans.count(0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = [0]*n
cnt = 0
a.sort()

while a:
    res = a.pop(0)
    cnt += 1
    
    i = 0
    flag = False
    while True:
        if i >= len(a): break
        if a[i]%res==0:
            if a[i] == res:
                flag = True
            a.pop(i)
            i -= 1
        i += 1
    if flag: cnt -= 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
Ain=list(map(int,input().split())) 
ans=0
A=set(Ain)
A=list(A)
A.sort()
A2=list(t for t in A)

for i in range(1,len(A)):
    for div in A2:
        if div<A[i] and A[i]%div==0:
            A2.remove(A[i])
            break
        elif div==A[i] and Ain.count(A[i])==1:
            ans+=1

if Ain.count(A[0])==1:
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

result = 0
n_list_a = set(sorted(n_list, reverse=True))

result = []
for i in n_list:
    d_flag = 0
    if n_list.count(i) > 1:
        d_flag = 1
    for j in n_list_a:
        if (i != j) and (i % j == 0):
            d_flag = 1
    if d_flag == 0:
        result.append(i)

print(len(result))

Submission status: Time Limit Exceeded

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

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

for i in range(n):
    if A[i]>0:
        j=2
        while A[i]*j<10**6+1:
            if table[A[i]*j]>0:
                table[A[i]*j]=-1
            j+=1

cnt=0
for x in table:
    if x==1:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
Alist=list(map(int,input().split()))
ans=0
for i in range(N):
    
    for j in range(N):
        if i==j:
            continue
        if Alist[i]%Alist[j]==int(0):
            #print(Alist[i])
            ans=ans+1
            break

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    D = Counter(A)

    B = []
    W = set()
    for k, v in D.items():
        if v == 1:
            B.append(k)
        else:
            W.add(k)

    res = 0
    for a in A:
        for i in range(1, int(pow(a, 0.5)) + 1):
            if a % i == 0:
                if i in W or a // i in W:
                    break
        else:
            res += 1
        W.add(a)
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import itertools
flatten_iter = itertools.chain.from_iterable
def factors(n):
    return list(set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0)))

def Intersection(lst1, lst2): 
    return set(lst1).intersection(lst2) 

n=int(input())
a=list(map(int,input().split()))
unique=list(set(a))
count=0
for x in a:
    if(a.count(x)==1):
        fac=factors(x)
        if(len(fac)>n):
            intersection=Intersection(fac,unique)
        else:
            intersection=Intersection(unique,fac)
        #print(intersection)
        if(len(intersection)==1):
            count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
 
## input
 
# n=int(input())
# A,B,C,D=map(int, input().split())
# string = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]

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


A.sort()
count = 0

for i in range(0,N):
    if A.count(A[i]) >= 2:
        continue
    elif i==0:
        count+=1
        continue
    else:
        for j in range(0,i):
            if A[i]%A[j]==0:
                break
            if j == i-1:
                count += 1
print(count)

Submission status: Time Limit Exceeded

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

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)

    def yakusu(num):
        i = 1
        ret = []
        while i*i <= num:
            if num%i != 0:
                i += 1
                continue
            ret.append(i)
            if i != num//i: ret.append(num//i)
            i += 1

        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(): 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 p in A.keys(): break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
a = [int(i) for i in input().split()]
aa = copy.deepcopy(a)
c=0
for ind_,i in enumerate(a):
  f=0
  for ind_2,j in enumerate(aa):
    if ind_==ind_2:
      continue
    if i<j:
      continue
    if i%j==0:
      f=1
      break
  if f==0:
    c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
c=0
for i in range(len(a)):
  for j in range(len(a)):
    d=0
    if i==n-1-j:
      continue
    elif a[i]%a[n-1-j]==0:
      d+=1
      break
  if d==0:
     c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
numbers = [int(i) for i in input().split()]
b = 0
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()))
a.sort()

res = 0
cnt = [False] * a[-1]
for i in range(n):
    j = 1
    while j * j <= a[i]:
        if a[i] % j == 0 and (cnt[j-1] or cnt[a[i]//j-1]):
            res += 1
            break
        j += 1
    if j * j > a[i] and i + 1 < n and a[i] == a[i+1]:
        res += 1
    cnt[a[i]-1] = True

print(n - res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L =tuple(map(int,input().split()))

Num = 0
for i in range(N):
    for j in range(N):
        if i != j and L[i] % L[j] == 0:break
        if j == N-1:Num += 1
        
print(Num)

Submission status: Time Limit Exceeded

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

ans = 0
for i, v in enumerate(A):
    flag = True    
    for j, w in enumerate(A):
        if j == i: continue
        if v % w == 0:
            flag = False
            break
    if flag: ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

b=[i for i in a]
b.sort()
r=[]
for i in range(len(a)):
    f=0
    for j in range(len(a)):
        if a[i]%a[j]==0 and i!=j:
            f=1
            break
    if f==0:
        r.append(i+1)
print(len(r))

Submission status: Time Limit Exceeded

Solution code:
import copy

a = input()
a = int(a)
b = input()
b = [int(i) for i in b.split()]
ans = 0
for i, j in enumerate(b):
  c = copy.deepcopy(b)
  del c[i]
  suc = True
  for k in c:
    if j % k == 0:
      suc = False
      break
  if suc == True:
    ans += 1
print(ans)