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:
# -*- coding: utf-8 -*-
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


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

flg=0
for i in range(n):
    li = make_divisors(a[i])
    for j in range(n):
        if i == j:
            continue
        if a[j] > a[i]:
            continue
        if a[j] in li:
            flg+=1
            break
        

print(n-flg)

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]

def binary_search(li, k):
    if not li:
        return False
    
    l = 0
    r = len(li) - 1
    
    while True:
        c = (l+r) // 2
        if li[c] == k:
            return True
        elif li[c] < k:
            l = c + 1
        else:
            r = c - 1
        if l > r:
            break
    return False


n = int(input())
a = sorted([int(i) for i in input().split()])
times = 0

for i in range(len(a)):
    divs = make_divisors(a[i])
    for j in divs:
        if binary_search(a[:i], j):
            times += 1
            break
        elif i < len(a) - 1:
            if binary_search(a[i+1:], j):
                times += 1
                break
            
print(n-times)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, deque
n = int(input())
a = list(map(int, input().split()))
a.sort()

na = a[::]
ans = 0
while na:
    st = 0
    if len(na)>1 and na[0] == na[1]:
        st = 1
    else:
        st = 0
        ans += 1
    nna = []
    for i in range(st, len(na)):
        if na[i] % na[0] > 0:
            nna.append(na[i])
    na = nna
print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    Nmax = 10**6+1

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

    prime = [0]*Nmax
    for i in range(N):
        if prime[A[i]] == 0:
            prime[A[i]] = 1
        else:
            prime[A[i]] = -1

    for a in A:
        if prime[a] != 0:
            for q in range(a*2, Nmax, a):
                prime[q] = 0

    res = 0
    for a in prime:
        if a == 1:
            res += 1

    print(res)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

ans = 0
count = 0

for index_1, num_1 in enumerate(num_list):
  for index_2, num_2 in enumerate(num_list):
    if index_1 != index_2:
      if num_1 % num_2 != 0:
        count += 1
  
  if count == n - 1:
    ans += 1

  count = 0

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

l = 0

double = []

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

print(len(a) - len(double))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+9)

    zero =  A.count(1)
    if zero>1:
        print(0)
        return
    if zero==1:
        print(1)
        return

    for i in range(lenb):
        for j in range(i+1,lenb):
            if Boo[j] and s[B[j]-1]==False and B[j] % B[i] == 0:
                Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and A.count(B[i])==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

count = 0


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]


for i, v in enumerate(A):
    tmp = A.pop(i)
    if len((set(make_divisors(v)) & set(A))) == 0:
        count = count + 1
    A.insert(i, tmp)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
@jit(cache=True)
def kkk(al):
	k=0
	for i in range(n):
		f=0
		for j in range(n):
			if i!=j and al[i]%al[j]==0:
				f=1
				break
		if f==0:
			k=k+1
	return(k)
        
n=int(input())
a=input()
a0=a.split()
al=list()
for i in range(n):
    al.append(int(a0[i]))

print(kkk(al))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
asor = sorted(a)
numlist = []
cnt = 0
while True:
    if asor == []:
        break
    if len(asor) ==1:
        cnt +=1
        break
    cnt +=1
    num = asor[0]
    numlist = []
    if asor[1] == num:
        cnt-=1
    for i in range (1,len(asor)):
        if asor[i]%num == 0:
            numlist.append(asor[i])
    for nums in numlist:
        asor.pop(asor.index(nums))
    asor.pop(0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
INF = 10**9+7
N = int(input())
L = list(map(int,input().split()))

L = np.array(L)
count = 0

while True:
    m = np.min(L)
    if m == INF:
        break
    else:
        # only one + 1
        if np.count_nonzero(L == m) == 1:
            count += 1

        L = np.where(L == m,INF,L)
        L = np.where(np.mod(L,m) == 0,INF,L)

print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split(" ")))
g=0
for i in range(n):
  for j in range(n):
    if A.count(A[i])>=2:
      g=g+1
      break
    if i!=j:
      if A[i]%A[j]==0:
        g=g+1
        break
print(n-g)

Submission status: Time Limit Exceeded

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

for i in range(N):
  ans = True
  for j in range(N):
    if i == j:
      continue
    ans = ans and A[i] % A[j] != 0
  if ans:
    cnt += 1
      
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    a = list_a.pop(0)
    list_a.append(a)
print(len(list_input) - anti_ans)

Submission status: Time Limit Exceeded

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

a.sort()
b = []
k = 0
for i in range(n):
    if i < n - 1:
        if a[i] == a[i + 1]:
            b.append(a[i])
            continue
    for j in range(len(b)):
        if a[i] % b[j] == 0:
            break
    else:
        k += 1
        b.append(a[i])
print(k)

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 in range(n):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
n= int(input())
a = sorted(map(int, input().split()))
for j,i in enumerate(a):
  d = deque()
  for l,k in enumerate(a):
    if j != l and k%i==0 and i != k:
      d.append(k)
  for t in d:
    a.remove(t)
c = len(a)
d = defaultdict(int)
for i in a:
  d[i]+=1
for k, v in d.items():
  if v >= 2:
    c-= v
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#! env/bin/local python3


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

    # divisors.sort()
    return divisors


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

a_divisors = {ac: set(divisors_f(ac)) for ac in a}
counter = 0
for key, value in a_divisors.items():
    a.remove(key)

    if len(set(a) & value) > 0:
        counter += 1
    a.append(key)

print(len(set(a)) - counter)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
r=0
import numpy as np
while len(a)>0:
  if len(a)==1:
    a.pop(0)
    r+=1
  else:
    for jj in np.arange(1,len(a)):
      a0=a[0]
      if a[0]%a[jj]==0:
        while a[0]==a0:
          a.pop(0)
          if len(a)<=0:
            break
        break
      if jj==len(a)-1:
        a.pop(0)
        r+=1
    #print(a0,r)
print(r)

Submission status: Time Limit Exceeded

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

a.sort()
b = [a[0]]
c = []

for i in range(1,len(a)):
    if not a[i] in b:
        b.append(a[i])
        for j in range(len(b)-1):
            if a[i] % b[j] == 0:
                b.pop(-1)
                break
    elif a[i] in c:
        continue
    else:
        c.append(a[i])
        

print(len(b)-len(c))

Submission status: Time Limit Exceeded

Solution code:
def solve(Auniq, Ai):
  for x in Auniq:
    if Ai % x == 0:
      return False
  return True

def main():
  N = int(input())
  A = list(map(int, input().split()))
  res = 0
  for i, Ai in enumerate(A):
    res += solve(set(A[:i] + A[(i+1):]), Ai)
  return res

print(main())

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  not_divisible_count = N
  A = [int(x) for x in input().split(" ")]
  set_A = set(A)

  for i, a_t in enumerate(A):
    for j, a in enumerate(A):
      if i != j and a_t%a == 0:
        not_divisible_count -= 1
        break
  

  print(not_divisible_count)
if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
b=a.copy()
i=0
while(i<n):
    j=i+1
    while(j<n):
        if(a[j]%a[i]==0):
            a.remove(a[j])
            n-=1
            j-=1
        j+=1
    i+=1
count=0
for x in a:
    if(b.count(x)==1):
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
an = np.array([int(a) for a in input().split()], dtype=np.int64)
res = 0
validate = np.ones(n, dtype="bool")
for i in range(n):
    # an_slice = np.copy(an)
    validate[:] = True
    validate[i] = False
    an_slice = an[validate]
    # an_slice = np.delete(an_slice,i)
    # diveded = np.array([an[i] % a for a in an_slice])
    diveded = an[i] % an_slice
    if diveded[diveded != 0].size == an_slice.size:
        res+=1

print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0

out = set()
for i in range(N):
    for j in range(i+1, N):
        if A[i] % A[j] == 0:
            out.add(A[i])
            break

for a in A:
    if a not in out:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    a2=set(a)
    a2=list(sorted(a2))
    def c1(num1):
        return a.count(num1)
    for i in range(len(a2)):
        num=0
        if c1(a2[i])==1:
            for j in range(i):
                if a2[i]%a2[j]==0:
                    num=1
                    break
                if a2[i]/2+1<a2[j]:
                    break
            if num==0:
                ans+=1
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def sol():
    N = int(input())
    A = list(map(int, input().split()))
    P = set(A)
    cnt = Counter(A)

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

    ans = 0
    for a in P:
        if cnt[a] > 1:
            continue
        for d in divisors(a):
            if d != a and d in P:
                break
        else:
            ans += 1

    print(ans)

sol()

Submission status: Time Limit Exceeded

Solution code:
def main1():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    ans=[1]*len(A)
    for i in  range(len(A)-1):
        if ans[i]==0:
            continue
        for j in range(i+1,len(A)):
            if A[j]%A[i]==0:
                ans[j]=0
    an=0
    for i in range(len(A)-1):
        if A[i]!=A[i+1]:
            an+=ans[i]
    an+=ans[-1]
    print(an)
main1()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

A.sort()
ok = [False] * N

for i in range(N):
    for j in range(i+1, N):
        if ok[j]:
            continue

        if A[i] == A[j]:
            ok[i] = True
            ok[j] = True

        if A[j] % A[i] == 0:
            ok[j] = True

print(N-sum(ok))

Submission status: Time Limit Exceeded

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

ans = num

flg2 = 0
flg3 = 0
if(2 in input_line):
    flg2 = 1
if(3 in input_line):
    flg3 = 1

for i in range(num):
    now = input_line[i]
    if(now!=2):
        if(now%2==0):
            if(flg2):
                ans-=1
                continue
    if(now!=3):
        if(now%3==0):
            if(flg3):
                ans-=1
                continue
    for j in range(num):
        if(i!=j):
            if(now%input_line[j]==0):
                ans-=1
                break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(s) for s in input().split()]
# a = list(range(1, 2*10**5))
ans = 0
for i,j in enumerate(a):
  a_i = sum(a[i]%s==0 for s in a)
  ans += min([2, a_i])
  # print(min([2, a_i]))
# print('###')
print(n - (ans-n))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
aaa=list(map(int,input().split()))
aaa.sort()
aa=deque(aaa)
count=0
while aa:
    a=aa.popleft()
    if len(aa)!=0:
        b=aa.popleft()
    else:
      b=float("inf")
    if a!=b:
        count+=1
    if b!=float("inf"):
      aa.appendleft(b)
    k=len(aa)
    for t in list(aa):
        if t%a==0:
          aa.remove(t)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout

int_in = lambda: int(stdin.buffer.readline())
arr_in = lambda: [int(x) for x in stdin.buffer.readline().split()]
out = lambda o: stdout.write("{}\n".format(o))

def divisors(n, items_in_a):
    i = 2
    result = set()
    while i * i <= n:
        if n % i == 0:
            opp = n // i
            if i in items_in_a or opp in items_in_a:
                return [n] # short circuit hack
            result.add(i)
            result.add(opp)
        i += 1
    return result

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


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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
 
def isPrime(n):
  if n == 2:
    return True
  if n % 2 == 0:
    return False
  
  # nの平方根まで計算する
  m = math.floor(math.sqrt(n)) + 1
  for p in range(3, m, 2):
      if n % p == 0:
        return False
  return True


n=int(input())
As = list(map(int, input().split()))
i=0
j=0
count =0
if As.count(1)==1:
    print(1)
    sys.exit()
if As.count(1)>=2:
    print(0)
    sys.exit()
for a in As:
    if As.count(a)>=2:
        i+=1
        continue
    elif isPrime(a):
        count+=1
        i+=1
        continue
    for b in As:
        if i!=j:
            if a%b==0:
                break
            elif j==n-1:
                count+=1
        elif j==n-1:
            count+=1
        j+=1
    i+=1
    j=0

print(count)

Submission status: Time Limit Exceeded

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    import numpy as np
    N = int(input())
    A = np.array(list(map(int, input().split())))

    #output
    answer = 0
    for i in range(N):
        if N - np.count_nonzero(A[i] % A) > 1:
            answer += 1
    answer = N - answer
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i,x in enumerate(a):
  for j,y in enumerate(a):
    if x%y == 0 and i != j:
      cnt -= 1
      break
print(cnt)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
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:
import numpy as np
input()

def no_Divisible(num,num_list):
    for row in set(num_list):
        if num%row==0:
            return 0
    return 1

input_list = np.array(sorted(list(map(lambda x:int(x),input().split(" "))),reverse=True))
count = 0
prev_num = 0
for i,num in enumerate(input_list):
    if num == prev_num:
        continue
    #print(num)
    #print(input_list[i+1:]%num)
    #if sum(input_list[i+1:]%num==0):
    if no_Divisible(num,input_list[i+1:]):
        count += 1
    prev_num = num
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    for i in range(n):
      count_temp = 0
      for k in range(n):
        if i != k and a[i] % a[k] == 0:
          count_temp += 1
          break
      if count_temp == 0:
        count += 1
    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(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):
    if make_divisors(ns[i]) & dubbles:
        dubbles.add(ns[i])
        continue
    ans += 1
    dubbles.add(ns[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# abc170_d.py
N = int(input())
A = list(map(int,input().split()))
cnt = 0
for i in range(N):
    can_devide = False
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            # print(A[i] , A[j])
            can_devide = True
            break
    if not can_devide:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
d={}
ans=0
s1=0
d={i:0 for i in range(1,10**6+1)}
for i in arr:
    if i==1:
        s1+=1
    d[i]+=1
if s1!=0:
    if s1>1:
        print(0)
        quit()
    else:
        print(1)
        quit()
for i in range(n):
    x=arr[i]
    if d[x]==1:
        f=1
        for j in range(2,int(x**0.5)+1):
            y=x//j
            if (d[j]>=1 and x%j==0) or ( d[y]>=1 and x%(y)==0):
                f=0
                break
        if f==1:
             ans+=1
print(ans)

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

cnt = [0] * 1000001

for i in range(n):
    cnt[p[i]] += 1

ans = n

for i in range(n):
    c = make_divisors(p[i])
    for j in range(len(c)):
        if (not (c[j] == p[i]) or cnt[c[j]]>1) and cnt[c[j]]:
            ans -= 1
            break
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:
            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:
n=int(input())
a=list(map(int,input().split()))
tf=[1]*n
n=n-1
notdiv=True
firstyn=0
for i in range(n,-1,-1):
  notdiv=True
  for j in range(i):
    if a[i]%a[j] == 0:
      tf[i]=0
    if a[j]%a[i] == 0:
      tf[j]=0
print(sum(tf))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(N):
    flg = 0
    for j in range(i):
        #if A[j]*2 > A[i]:
            #print(A[j], A[i])
        #    break
        if i != 0:
            if A[i]%A[j] == 0:
                flg = 1
                break    
    if flg == 0:
        if i +1 < N:
            if A[i+1] != A[i]:
                ans += 1
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

def main():

    input = sys.stdin.readline

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

    ans = 0
    sort_A = sorted(set(A))

    c = collections.Counter(A)

    calc_list = []

    for a in sort_A:
        flag = True
        for k in calc_list:
            if a // 2 < k:
                break
            if (a % k == 0):
                flag = False
                break

        if flag == True:
            if c[a] == 1:
                ans += 1

            if len(calc_list) == 0:
                calc_list.append(a)
            elif calc_list[-1] != a:
                calc_list.append(a)

    print(ans)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

A_sort = sorted(A)
A_counter = Counter(A)
# print(A_sort)

res = 0
# res_list = []
for i in range(len(A_sort)):
    A_sort_tmp = A_sort[:i]

    if A_counter[A_sort[i]] >= 2:
        continue

    for j in range(len(A_sort_tmp)):
        if A_sort[i] % A_sort_tmp[j] == 0:
            break
    else:
        res += 1
        # res_list.append(i + 1)

print(res)
# print(res_list)

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
s=a_list.count(1)
if s==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]
elif s==1 :
  count=1
else :
  count=0


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]

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in make_divisors(i):
    if f in a:
      if f == i and a.count(f) > 1:
        b += 1
        break
      elif f != i:
        b += 1
        break
print(num - b)

Submission status: Time Limit Exceeded

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

ans = 0
for i, val in enumerate(A):
    curr_set = set(A[:i] + A[i+1:])
    if val in curr_set:
        continue
    for j in range(1, int(sqrt(val)) + 1):
        if (val % j == 0 and j in curr_set) or val / j in curr_set:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

cnt = {}
kouho = []
for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1

    flag = True
    for j in range(i):
        # print(arr[j],end=" ")
        if arr[j] > arr[i]//2+1:
            break
        if arr[i]%arr[j] == 0:
            flag = False

    if flag:
        kouho.append(arr[i])

# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
       ans += 1

print(ans)

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 = [i for i in a_list if i<=(val/2)]
  # print(val, ref_list)
  if a_list.count(val) != 1:
      cnt -= 1
  else:
    for j in ref_list:
      # print(val, j)
      if val % j != 0:
        continue
      else:
        cnt -= 1
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
counter = n
for i in range(n):
    for j in range(n):
        if i != j and lis[i]%lis[j] ==0:
            counter -=1
            break
print(counter)

Submission status: Time Limit Exceeded

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

ans = 0
  
while True:
  d = A.pop(0)
  if d in A:
    ans -= 1
  
  '''for a in A[::-1]:
    if a % d == 0:
      A.remove(a)'''
  A = list(reversed([ a for a in A[::-1] if a % d != 0]))
  ans += 1
  if A:
    True
  else:
    break
  
print(ans)

Submission status: Time Limit Exceeded

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

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

a.sort()
#print(a)

ans = 0
div = []
if a[0] == a[1]:
    pass
else:
    ans += 1

div.append(a[0])

for i in range(1, n-1):
    if a[i] == a[i-1]:
        pass
    elif a[i] == a[i+1]:
        div.append(a[i])
    else:
        flg = True
        for j in div:
            if j*2 > a[i]:
                break
            if a[i] % j == 0:
                flg = False
                break
        if flg:
            div.append(a[i])
            ans += 1
    #print(i, a[i], div, ans)

if a[n-2] == a[n-1]:
    pass
else:
    flg = True
    for j in div:
        if a[n-1] % j == 0:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()