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

ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            ans = ans
        else:
            a = p[i]/p[j]
            d = a.is_integer()
            if d:
                ans = ans + 1
                break
print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import exit
N = int(input())
if N == 1:
  print(1)
  exit()
A = list(map(int, input().split()))

ban = set()
D = set()
for a in A:
  if a in D:
    ban.add(a)
  else:
    D.add(a)
D = deque(sorted(list(D)))
ans = 0
while D:
  ini = D.popleft()
  if not ini in ban:
    ans += 1
  if len(D) == 0:
    break
  for i in range(len(D)):
    d = D.popleft()
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()
b = [a[0]]
c = []
if a[0] == 1:
    d = a.count(1)
    if d == 1:
        print(1)
    else:
        print(0)
else:
    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:
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)
    co=0
    while co!=k:
      t=aa.popleft()
      co+=1
      if t%a!=0:
        aa.append(t)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
A = np.sort(A)
c = 0
while len(A) > 0:
    ai = A[0]
    AL = A[1:]
    if not ai in AL:
        c += 1
    mask = AL % ai != 0
    A = AL[mask]
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
 
ttable = [[False for i in range(N)] for j in range(N)]
 
for i in range(N):
  for j in range(i+1, N):
    if As[i] == As[j]:
      ttable[i][j] = True
      ttable[j][i] = True
    elif As[i] % As[j] == 0:
      ttable[i][j] = True
    elif As[j] % As[i] == 0:
      ttable[j][i] = True

cnt = 0
for i in range(N):
  if True not in ttable[i]:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

i = 0
while i < len(A):
    a = A[i]
    if i < len(A)-1:
        if A[i+1] == a:
            while a in A:
                A.remove(a)
            continue
    j = i + 1
    while j < len(A):
        if A[j] % a == 0:
            A.pop(j)
        else:
            j += 1
    i += 1
print(len(A))

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))
    num3=0
    if a2[0]==1:
        if a.count(1)==1:
            ans=1
        else:
            ans=0
    else:
        len2=len(a2)
        def c1(num1):
            return a.count(num1)
        def l1():
            return len(a2)
        for i in range(len2):
            num=0
            if c1(a2[i-num3])==1:
                for j in range(i-num3):
                    if a2[i-num3]%a2[j]==0:
                        num=1
                        a2.remove(a2[i-num3])
                        num3+=1
                        break
                    if a2[i-num3]/2+1<a2[j]:
                        break
                if num==0:
                    ans+=1
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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

results = deque()
while len(A) > 0:
    if not (len(A) > 1 and A[0] == A[1]):
        results.append(A[0])
    A = [a for a in A if a % A[0] != 0]

print(len(results))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N= int(input())
A = input().split()
Ans = 0
flag = 0
for i in range(N):
  for j in range(N):
    if i != j :
      if (int(A[i]) % int(A[j])) == 0:
        flag = 1
        break
      #print(i, j, A[i], A[j], flag)
  if flag == 0:
    Ans += 1
  flag = 0
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit,i8

@jit("i8(i8,i8[:])")
def counter(N,A):
    count = 0
    for i in range(N):
        sum1=0
        for j in range(i):
            if A[i]%A[j] != 0:
                sum1+=1
        if sum1 == i:
            count+=1
            if i<N-1 and A[i+1]==A[i]:
                count-=1

    return count
    
    
N = int(input())
A = list(map(int,input().split()))
A = np.array(sorted(A))

print(counter(N,A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    N = int(input())
    An = list(map(int, input().split()))
    ok = [False] * N
    a_An = np.array(An)
    for i, a in enumerate(An):
        temp = a_An / a
        temp[i] = 0.1
        check = (temp % 1 == 0)
        ok = ok | check
    print(np.count_nonzero(ok == 0))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

nums = [0] * (10 ** 6 + 5)

for a in A:
    nums[a] += 1

MAX = 10 ** 6 + 1
pr = set()
for a in A:
    nums[a] -= 1
    b = a
    while b <= MAX:
        if nums[b] > 0:
            pr.add(b)
        b += a
    nums[a] += 1

ans = len(A)
for a in A:
    if a in pr:
        ans -= 1
# print(pr)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
from numba.typed import List
import numpy as np

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


@jit
def test(As):
    num_i = 0
    num_j = 0
    not_divisible = 0
    for num_i, Ai in enumerate(As):
        for num_j, Aj in enumerate(As):
            if num_i==num_j:
                continue
            if Ai%Aj==0:
                break
        else:
            not_divisible += 1
    print(not_divisible)
    
test(As)

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:
  i = 0
  ans = 0
  for _ in range(n):
    count = 1
    for j in range(i):
      if a_list[i] % a_list[j] == 0:
        if i < 2/n:
          del a_list[i]
          i -= 1
        count = 0
        break
    if count == 1:
      if i == len(a_list)-1:
        ans += 1
      elif a_list[i] != a_list[i+1]:
        ans += 1
    i += 1
  print(ans)

Submission status: Time Limit Exceeded

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

def func1(a):
    a.sort()
    cnt=0
    chker=[]
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
        else:
            for j in chker:
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
        chker.append(i)
    print(cnt)
func1(a)

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)>0:
  a = a_l.pop(0)
#  print(f'a:{a}')
  if len(a_l) == 0 or 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))

Submission status: Time Limit Exceeded

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

A.sort()

count = 0
for i in range(N):
    if i < N - 1:
        if A[i] == A[i+1]:
            continue
    if i > 0:
        if A[i] == A[i-1]:
            continue
    div_flag = True
    for j in range(i):
        if A[i] % A[j] == 0:
            div_flag = False
            break
    if div_flag:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import jit

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++
@jit
def cc(v, pp):
	if v == pp[-1]:
		return False, -1
	
	for p in pp:
		if v % p == 0:
			return False, 0
		if v < 2*p:
			return True, 0
	return True, 0
			
@jit
def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al.sort()
	pp=[al[0]]
	n_same=0
	n_same_set=set()
	for v in al[1:]:
		tf, vv = cc(v, pp)
		if tf:
			pp.append(v)
		if vv == -1 and pp[-1] not in n_same_set:
			n_same_set.add(pp[-1])
			n_same += vv
	print(len(pp) + n_same)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

count = 0

for i in range(N):
    tmp = [A[i]] * N
    tmp = [j % k for(j, k) in zip(tmp, A)]
    if tmp.count(0) == 1:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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


N = int(input())
A = list(map(int, input().split()))
A.sort()
L = collections.Counter(A)

#print(A)
ans = 0

for i in reversed(range(N)):
    a = A[i]
    if L[a] != 1:
        continue
        
    jdg = 0
    if a % 2 == 0:
        index = bisect.bisect_right(A,a//2)
        #print(index,a)
        for k in range(index):
            if a % A[k] == 0:
                jdg += 1
                break
        if jdg == 0:
            ans += 1
            
    elif a % 3 == 0:
        index = bisect.bisect_right(A,a//3)
        #print(index,a)
        for k in range(index):
            if a % A[k] == 0:
                jdg += 1
                break
        if jdg == 0:
            ans += 1
            
    elif a % 5 == 0:
        index = bisect.bisect_right(A,a//5)
        #print(index,a)
        for k in range(index):
            if a % A[k] == 0:
                jdg += 1
                break
        if jdg == 0:
            ans += 1
            
    elif a % 7 == 0:
        index = bisect.bisect_right(A,a//7)
        #print(index,a)
        for k in range(index):
            if a % A[k] == 0:
                jdg += 1
                break
        if jdg == 0:
            ans += 1
    
    else:
        index = bisect.bisect_right(A,a//11)
        #print(index,a)
        for k in range(index):
            if a % A[k] == 0:
                jdg += 1
                break
        if jdg == 0:
            ans += 1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())

count = 0
A = list(map(int, input().split()))
A = np.sort(A, kind='mergesort')[::-1]
s = set([])

for i in range(n):
  for j in range(n):
    if i != n-j-1 and A[i] % A[n-j-1] == 0:
      s.add(i+1)
      break
      
print(n-len(s))

Submission status: Time Limit Exceeded

Solution code:

import collections
from copy import copy


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def f(n):
    facs = factorization(n)
    res = set()

    def g(arr, total):
        if len(arr) == 0:
            res.add(total)
            return

        a, b = arr.pop()
        for i in range(0, b + 1):
            num = a ** i
            res.add(num)
            g(copy(arr), total * num)

    g(facs, 1)

    return res


def main():
    n = int(input())
    A = tuple(map(int, input().split()))
    D = collections.defaultdict(int)
    for a in A:
        D[a] += 1

    ans = n
    for i in range(n):
        a = A[i]

        if D[a] > 1:
            ans -= 1
            continue

        if a == 1:
            continue

        res = f(a)
        res.remove(a)
        for num in res:
            if num in D:
                ans -= 1
                break

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(N) : 
    B = list(map(lambda x: A[i] % x , A))
    if B.count(0) == 1 :
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
t=list(set(a))
t.sort()
ans=n
for i in range(0,n):
  temp=0
  if i>1:
    if a[i]==a[i-1]:
      temp=1
  if i<n-1:
    if a[i]==a[i+1]:
      temp=1
  if temp==1:
    ans=ans-1
  else:
    for j in range(0,len(t)):
      if a[i]<t[j]:
        break
      if a[i]!=t[j] and a[i]%t[j]==0:
        ans=ans-1
        break
print(ans)

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, ai in enumerate(a):
    if i != n-1 and ai == a[i+1]:
        cnt += 1
        continue
    for j, aj in enumerate(a[:i+1]):
        if i!=j and ai%aj==0:
            cnt += 1
            break

print(n-cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve(i,j,a):
    k=False
    sc=0
    for v in [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973]:
        if j%v==0:
            break
    v=j//v
    for c in a:
        if c>v:
            break
        else:
            if j%c==0:
                k=True
                break
    return k

n=int(input())
a=sorted(list(map(int,input().split())))
ac=Counter(a)
ans=0
for i,j in enumerate(a):
    if ac[j]>=2:
        continue
    if solve(i,j,a):
        continue
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=sorted(A)
l=[]
for i in L:
    if L.count(i)==1:
        l.append(i)
for i in l:
    for j in l[l.index(i)+1:]:
        if j%i==0:
            l.pop(l.index(j))
        else:
            None
print(len(l))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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


def divisor(n):
    i = 1
    table = []
    while(i * i <= n):
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table


N = int(input())

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

A.sort()

ans = 0
ans = N
for i in range(N):
    divs = divisor(A[i])
    divs.sort()
    Set = set(A[:i])
    #print(A[i], "divs", divs)
    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()))

i=0
num=0

while i<n:

    j=0
    jud=1
    while j<n:
        if i!=j:
            if a[i]>=a[j]:

                if a[i]%a[j]==0:
                    jud=0
                    break

        j+=1

    if jud==1:
        num+=1

    i+=1

print(num)

Submission status: Time Limit Exceeded

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    

    n = int(lines[0])
    a = [int(e) for e in lines[1].split(' ')]

    return (n, a)


def solve(n, a):

    if n == 1:
        return 1
    
    count_dict = dict()
    for i in range(n):
        cnt = count_dict.get(a[i], 0)
        cnt = cnt + 1
        count_dict[a[i]] = cnt
    
    b = list(count_dict.keys())
    b.sort()

    tmp = b.copy()
    result = []
    while len(tmp) > 0:
        h = tmp[0]
        result.append(h)
        tails = tmp[1:]
        tmp2 = []
        for t in tails: 
            if t % h == 0:
                pass
            else:
                tmp2.append(t)

        tmp = tmp2

    result_2 = []    
    removed = set([k for k, v in count_dict.items() if v > 1])
    for r in result:
        if r in removed:
            pass
        else:
            result_2.append(r)
    
    len_result = len(result_2)

    return len_result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':
  
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

A.sort(reverse=True)
c = Counter(A)

ans = 0
for idx, a in enumerate(A):
    if c[a] >= 2:
        continue
    for b in A[idx + 1:]:
        if a % b == 0:
            break
    else:
        ans += 1
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())

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

ans = []
double = []

s = 0
while len(a) > 0:
    ans.append(a.popleft())
    if ans[s] in a:
        double.append(ans[s])
    a = deque([i for i in a if i % ans[s] != 0])
    s += 1

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

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

m = 10**6+100
n_map = {}
v_a = []
nn_map = {}
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
    if i in nn_map:
        continue
    for j in range(2, ceil(m / i) + 1):
        nn_map[i * j] = True


res = 0
for k, v in n_map.items():
    if v != 1:
        continue
    if k in nn_map:
        continue
    res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
def main():
    
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    
    from collections import defaultdict
    d = defaultdict(int)
    
    for k in A:
        d[k] += 1
    
    ans = 0
    A = list(d.keys())
    
    while(len(A)!=0):
        tmp = A[0]
        if d[A[0]] == 1:
            ans += 1
            
    
        for j in range(len(A)):
            if A[j] % tmp == 0:
                del d[A[j]]
        
        A = list(d.keys())
        
        
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(n):
  kotae.append(a[0])
  if 2<=len(a):
    if a[1]==a[0]:
      kotae.pop(-1)
  for j in range(1,len(a)):
    if a[j]%a[0]!=0:
      a2.append(a[j])
  a=a2
  a2=[]
  if len(a)==0:
    break
       
print(len(kotae))

Submission status: Time Limit Exceeded

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

temp_ans = [A.pop(0)]
div = []
ans = 1

for i in A:
  flag = 0
  for j in temp_ans:
    if i == j:
      div.append(i)
      flag = 1
      break
    if i % j == 0:
      flag = 1
      break
  if flag == 0:
    ans += 1
    temp_ans.append(i)
print(ans - len(set(div)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

count = 0

for i in range(n):
    a_ = [a[i] % t for t in a]
    c = a_.count(0)
    
    if c == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
h = int(input())
if h == 1:
	print(1)
	exit()
a = list(map(int,input().split()))
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

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

ans = 0
for i in b:
	t=makediv(i)
	mode = 1
	for l in t:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    if A.count(A[i]) <= 1:
        for j in range(i+1, N):
            if A[i] % A[j] == 0:
                break
        else:
                cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

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()))
setA = set(A)
dup = set([x for x in setA if A.count(x) > 1])

count = 0
for i in range(len(A)):
    flag = False
    if A[i] in dup:
        continue
    for div in make_divisors(A[i]):
        if div == A[i]:
            continue
        elif div in setA:
            flag = True
            break
    if not flag:
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

count = 0

for n in range(N):
  flg = True
  if A.count(A[n]) == 1:
    tmp = [a for a in A if a != A[n]]
    for m in tmp:
      if A[n]%m == 0: flg = False
  else: flg = False
  
  if flg == True: count += 1
    
print(count)