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

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

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:
    temp_ans.append(i)
print(len(temp_ans) - len(set(div)))

Submission status: Time Limit Exceeded

Solution code:
line = input()
line = line.rstrip().split(' ')
n = int(line[0])

line = input()
line = line.rstrip().split(' ')
a = []
for i in line:
    a.append(int(i))

a.sort()

answer = 0

for i in range(len(a)):
    dividable = False
    for j in range(len(a)):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            dividable = True
            break

    if dividable == False:
        answer += 1

print(answer)

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()))
  Auniq = set(A)
  res = 0
  for i, Ai in enumerate(A):
    Aeq = list(filter(lambda x: x == Ai, A))
    if len(Aeq) == 1:
      Aless = list(filter(lambda x: x < Ai, Auniq))
      if len(Aless) == 0:
        res += 1
      else:
        res += solve(set(Aless), Ai)
  return res

print(main())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=a.copy()
a=set(a)
for i in range(1,b[-1]+1):
    bi=b.count(i)
    if bi>=2:
        for j in range(bi):
            b.remove(i)
a=list(a)
n=len(a)
m=len(b)
for i in range(m):
    for j in range(n):
        if a[j]!=b[i] and b[i]%a[j]==0:
            b[i]=0
print(m-b.count(0))

Submission status: Time Limit Exceeded

Solution code:

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

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
    tp = arr[i]
    while True:
        erat[tp] = False
        tp += arr[i]
        if tp > 10**6:
            break
# 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(map(int,input().split()))

dic={}
for i in range(N):
    if A[i] not in dic:
        dic[A[i]]=1
    else:
        dic[A[i]]+=1

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

if 1 in dic:
    if dic[1]>1:
        print(0)
        exit()
    else:
        print(1)
        exit()

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

ans=0
for i in range(N):
    if dic[A[i]]>1:
        continue
    f=False
    for j in range(2, int(A[i]**0.5)+1):
        if A[i]%j==0:
            if j in dic or A[i]//j in dic:
                f=True
                break
    if f:
        continue
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input().strip())
A = [int(v) for v in input().strip().split(" ")]

A = sorted(A)

counter = 0
for i in range(N):
    count_flag = True
    for j in range(N):
        if i == j:
            continue
        if A[i] < A[j]:
            break
        if A[i] % A[j] == 0:
            count_flag = False
            break
    if count_flag:
        counter += 1

print(counter)

Submission status: Time Limit Exceeded

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

#Adic = {}

#for i in range(N):
#	Adic[A[i]] = i + 1

Asorted = sorted(A)
#divlist = []
dup = [x for x in set(Asorted) if Asorted.count(x) > 1]
Asorterd = set(Asorted)

count = 0
for i in range(len(Asorted)):
	divflag = False
	for j in range(i):
		if Asorted[i] % Asorted[i - j - 1] == 0:
			divflag = True
			break
	if divflag == False and Asorted[i] not in dup:
		#divlist.append(Asorted[i])
		count+=1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))
l.sort()
s_b = set(range(n))
res = 0
for i in range(n):
    if i in s_b:
        v = l[i]
        if i < n-1 and v == l[i+1]:
            res += 0
        else:
            res += 1
        s_b.remove(i)
        l_r = []
        for j in s_b:
            if l[j]%v==0:
                l_r.append(j)
        for j in l_r:
            s_b.remove(j)
print(res)

Submission status: Time Limit Exceeded

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

i = 0
while i < len(a):
  b = []
  for j in range(i+1):
    b.append(a[j])
  for j in range(i+1,len(a)):
    if a[j]%a[i]!=0 or a[j]==a[i]:
      b.append(a[j])
  a = b
  i += 1

for i in a:
  if a.count(i)>=2:
    a = [j for j in a if i!=j]

print(len(a))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a_list=list(map(int,input().split()))
count=0
import collections
a_list=sorted(a_list, reverse=True)
s=a_list.count(1)
a_list=collections.Counter(a_list)
key_list=list(a_list.keys())
item_list=list(a_list.values())

m=len(item_list)
before_num=0

if s==0 :
  for i in range(m) :
    if item_list[i]==1 :
      flag=True

      for j in reversed(range(i+1,m)) :
        if key_list[i]%key_list[j]==0  :
            flag=False
            break
      if flag :
        count+=1

elif s==1 :
  count=1
else :
  count=0


print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.append(0)
a.sort()
a.reverse()
ans=0
for i,ai in enumerate(a[:-1],1):
    # print(">",ai)
    for j,aj in enumerate(a[i:],1):
        # print(ai,aj,j)
        if a.count(ai) >= 2:
            continue
        if aj == 0:
            ans += 1
        elif ai % aj == 0:
            # print(">>next")
            break
        # elif j == len(a[i:]):
        #     ans += 1
        #     print(">>add")
print(ans)

Submission status: Time Limit Exceeded

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

A_list.sort()

cnt = 0

while len(A_list)>1:
    num = A_list.pop(0)
    if num != A_list[0]:
        cnt+=1
    A_list = [x for x in A_list if x%num!=0]

if len(A_list) == 1:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(N):
    if i != 0 and i != N - 1:
        if A[i - 1] == A[i] or A[i] == A[i + 1]:
            div.add(A[i])
div = list(div)

# print(A)
# print(div)
for i in range(N):
    for j in range(len(div)):
        if A[i] % div[j] == 0:
            ans -= 1
            break
    div.append(A[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# スペース区切りの整数の入力
N = int(input())
A = np.array(list(map(int, input().split())))


count = 0
while len(A) > 0:
    a = A[0]
    A = A[1:]
    
    # a で割り切れない部分
    f1 = A % a > 0
    # a を割り切れない部分
    f2 = a % A  > 0 
        
    # 0がなければCountする
    if np.sum(f2 == 0) == 0:
        count += 1

    # AとAinvの不要な箇所を削除
    A = A[f1]

print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = []
    while len(a) != 0:
        now = a[0]
        arr = a.copy()
        cnt = 0
        for i in a:
            if i % now == 0:
                if i == now:
                    cnt += 1
                arr.remove(i)
        a = arr.copy()
        if cnt > 1:
            continue
        ans.append(now)
    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = [False]*n
a.sort()
z = 0
for i,v in enumerate(a):
    if b[i]:
        continue
    for j in range(i+1,n):
        if a[j] == v:
            b[i] = True
            b[j] = True
        elif a[j] > a[-1]//v * v:
            break
        elif a[j] % v == 0:
            b[j] = True
print(b.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
rm_dct = {}
# rm_list = []
for c in a:
  if str(c) not in rm_dct:
    # rm_list.append(c)
    rm_dct[str(c)] = 1
  else:
    rm_dct[str(c)] += 1
a = list(set(a))

index = 0
p = a[0]
last = a[-1]
flg = False
while True:
  for i in range(index+1, len(a)):
    if a[i] % p == 0:
      a[i] = 0
  for i in range(index+1, len(a)):
    if a[i] > 0:
      index = i
      p = a[i]
      flg = True
      break
  if not flg or p >= last/2:
    break
  flg = False

ans = 0
for c in a:
  if c != 0 and ((str(c) not in rm_dct) or rm_dct[str(c)] <= 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()
p = []
k = set()
while a:
    prime = min( a )

    p.append( prime )

    i = 0
    flag = 0
    while i < len( a ):
        if a[ i ] == prime and flag == 1:
            k.add( prime )
        flag = 1
        if a[ i ] % prime == 0:
            a.pop( i )
            continue
        i += 1

# print( p, k )
print( len( p ) - len( k ) )

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
count = 0
flag = 0
for i in range(N):
	for j in range(N):
		if a[i]%a[j] ==0 and i!= j:
			flag = 1
	if(flag == 0):
		count = count +1
	flag = 0
print(count)

Submission status: Time Limit Exceeded

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

als = sorted(al)
m = als[-1]

from collections import Counter
c = Counter(als)


res = 0
kouho =[]
for i in range(n):
    flg = 0
    j = als[i]
    if c[j] >1:
        if j in kouho:
            pass
        kouho.append(j)
        pass
    else:
        for k in kouho:
            if j % k ==0:
                flg = 1
                break
        if flg != 1:
            res += 1
            kouho.append(j)
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N, *A = map(int, open(0).read().split())

    ctr = Counter(A)
    memo = []
    dp = set()
    ans = 0

    for a in sorted(A):
        if a == 1:
            if ctr[a] == 1:
                ans = 1
            break

        if ctr[a] == 1:
            for v in memo:
                if a % v == 0:
                    break
            else:
                ans += 1

        memo.append(a)
        dp.add(a)

    print(ans)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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



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

out = 0

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

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

for A in As:
    exists[A] = True

for A1, num in counter.items():
    if num >= 2:
        continue
    
    exist = False

    ds = make_divisors(A1)
    for d in ds:
        if exists[d]:
            if d != A1:
                exist = True

    if not exist:
        out += 1

print(out)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = 0
for i in b:
    if b.count(i) != 1:
        c += 1
    else:
        for f in b[:b.index(i)]:
            if i % f == 0:
                c += 1
                break
print(num - c)

Submission status: Time Limit Exceeded

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

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]==0:
                jud=0
                break

        j+=1

    if jud==1:
        num+=1

    i+=1

print(num)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

n=int(input())
C=list(map(int,input().split()))
A = np.array(sorted(C))
ans = 0

for i in range(n):
    if len(A) == 0:
        print(ans)
        sys.exit()
    elif len(A) ==1:
        ans +=1
        print(ans)
        sys.exit()
    elif len(A) !=1 and A[0] != A[1]:
        ans +=1
    A = A[A%A[0] !=0]
print(ans)
sys.exit()

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

v_a = [k for k, v in n_map.items() if v <= 1]

v_a.sort()
vv_a = []

for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)

print(len(vv_a))

Submission status: Time Limit Exceeded

Solution code:
# 2020/06/14
# AtCoder Beginner Contest 170 - D

# Input
n = int(input())
a = list(map(int,input().split()))
a.sort()
a.append(10**7)
sosulist = list()
sosulist.append(0)

# Calc
ans = n

if a[0] == a[1]:
    ans = ans - 1

for i in range(1, n):
    if a[i] == a[i+1]:
        ans = ans - 1
        sosulist.append(i)

    else:
        wkval = 1
        slen = len(sosulist)
        for j in range(slen):
            if a[i] % a[sosulist[j]] == 0:
                ans = ans - 1
                wkval = 0
                break
        if wkval == 1:
            sosulist.append(i)

# Output
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    a = list(map(int, input().rstrip().split()))
    count = 0
    b = []
    for i in range(n):
      count_temp = 0
      if not a[i] in b:
        for k in range(n):
          if i != k and a[i] % a[k] == 0:
            count_temp += 1
            break
        if count_temp == 0:
          count += 1
          b.append(a[i])
    print(count)
  
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
p = 0
counter = n
for i in range(n):
    if i>0 and lis[i] == lis[i-1]:
        counter -=1
    elif i>0 and lis[i]<lis[0]*2:
        p += 1
    else:
        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 Counter

def solve(i,j,a):
    k=False
    sc=0
    for v in [2,3,5,7,11,13,17,19]:
        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()))
cnt=0
a.sort()
max_a=a[n-1]
#a_table=[True for i in range(n)]
while len(a) > 0:
    min_a=a[0]
    if a.count(min_a)==1:
        cnt+=1
    #for k in range(1,max_a//min_a+1):
    a=[ele for ele in a if ele%min_a != 0]
    #print(a)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())))
ans = 0

for idx, num in enumerate(A):
  B = num % A
  if np.count_nonzero(B!=0) == n-1:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)
ans = 0

for i in range(n):
    if c[li[i]] > 1:
        ans += 1
        continue
    for j in range(n):
        if i == j:
            continue
        if li[i]%li[j] == 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)

A_div = [0 for _ in range(N)]
for i in range(N):
    if A_div[i] == 0:
        for j in range(i + 1, N):
            if A[i] % A[j] == 0:
                A_div[i] += 1
            if A[j] % A[i] == 0:
                A_div[j] += 1

print(A_div.count(0))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A = [int(e) for e in input().split()]

    A.sort()

    D = set()
    prev = -1
    for i in range(n):
        if A[i] == prev:
            D.add(A[i])
            A[i - 1] = -1
            A[i] = -1
        else:
            prev = A[i]

    A = [a for a in A if a != -1]
    ans = 0
    for i in range(len(A)):
        if len([d for d in D if A[i] % d == 0]) == 0:
            ans += 1
            D.add(A[i])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

answer = []

for i1,v1 in enumerate(A):
    status = False
    for i2,v2 in enumerate(A):
        if i1 != i2 and v1 % v2 == 0:
            #print(i1,i2,v1,"%",v2,"=",v1 % v2)
            status = True
            break
    if status:
        answer.append(i1)

print(N - len(set(answer)))

Submission status: Time Limit Exceeded

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        i = 1
        while i * val <= 10 ** 6:
            dame_set.add(i * val)
            i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            while i * val <= 10 ** 6:
                dame_set.add(i * val)
                i += 1

print(ret)

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]
    if len(np.where(a[idxes] == var)[0]) == 0:
        count += 1
    idxes = idxes[np.where(a[idxes] % var != 0)[0]]
print(count)

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:
        a_list = a_list[:i] + a_list[i+1:]
        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:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

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


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

    # divisors.sort()
    return divisors


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

count = 0
for num in A:
    if countA[num] >= 2:
        continue
    divisors = make_divisors(num)
    if all((e not in setA) for e in divisors):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for i in range(N):
    if count[A[i]] >= 2:
        ans += 1
        happend.add(A[i])
        continue
    for j in range(1, int(A[i]**(1/2))+2):
        if A[i] % j == 0:
            if j in happend or A[i]//j in happend:
                ans += 1
                break
    happend.add(A[i])
print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
#D
N = int(input())
A = list(map(int, input().split()))
counter = 0
for i in range(N):
    can_divide = False
    for j in range(N):
        if i!=j and A[i]%A[j]==0:
            can_divide = True
            break
    if not can_divide:
        counter+= 1
print(counter)
#文字通りい作ったもの。TLE

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
counter = 0
for i in range(n):
  flag = True
  for j in range(n):
    if i == j:
      continue
    if a[i] % a[j] == 0:
      flag = False
      break
  if flag:
    counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
x = []
i = 0
while len(A) != 0:
    j = i + 1
    flag = True
    q = []
    while j < len(A):
        if A[j] == A[i]:
            flag = False
        if A[j]%A[i] != 0:
            q.append(A[j])
        j = j + 1
    if flag:
        x.append(A[i])
    A = q
    i = 0
print(len(x))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        if Boo[i] and B[i]<500004:
            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 C[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 = input()
a_list = input().split()

n = int(n)

def check():
    exact_list = []
    for i in range(0, n):

        # 一回も割り切れない場合を探す
        flg = False

        for j in range(0, n):
            # 一緒の数字ならば飛ばす
            if i == j:
                continue

            # 割り切れない場合を探せ
            # print(int(a_list[i]) % int(a_list[j]))
            if int(a_list[i]) % int(a_list[j]) == 0:
                flg = True
        
        # 割り切れた場合、該当配列を記録する
        if flg == False:
            exact_list.append(i+1)


    print(len(exact_list))

check()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

MOD = 10**9+7

def lcm(a, b):
    return a*b//gcd(a, b)

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def main():
    N = ii()
    A = list(mi())
    A.sort()
    cnt = 0
    dic = {}
    for i in range(N):
        if not A[i] in dic:
            dic[A[i]] = 0
        dic[A[i]] += 1
    ans = []
    while A:
        t = A.pop(0)
        if dic[t] == 1:
            ans.append(t)
        A = list(filter(lambda x: x%t!=0, A))
    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [int(s) for s in input().rstrip().split()]

count = 0

def explore(i):
  n_i = nums[i]
  n_i_half = n_i // 2
  for j in range(N):
    if j != i:
      n_j = nums[j]
      if n_j == n_i:
        return 0
      if n_j <= n_i_half:
        if n_i % n_j == 0:
          return 0
  return 1

for i in range(N):
  count += explore(i)

print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
t=list(set(a))
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] and a[i]%t[j]==0:
        ans=ans-1
        break
print(ans)

Submission status: Time Limit Exceeded

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


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 = {b: 0 for b in bs}
    for b in bs:
        ctr[b] += 1
    ds = {k: sum(ctr.get(k, 0) 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=input();
N=int(N);
A=input().split();
A=[int(s) for s in A];
ans_list=[];
flag=True;
for i in range(N):
  for j in range(N):
    if i==j:
      continue;
    if A[i]%A[j]==0:
      flag=False;
      break;
  if (not A[i] in ans_list) and flag==True:
    ans_list.append(A[i]);
  flag=True;
print(len(ans_list))

Submission status: Time Limit Exceeded

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

N = int(input())

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

AList.sort()

ResultList = []
PrimeList = []

tmp = 0

if N > 1:
    if AList[0] != AList[1]:
        ResultList.append(AList[0])
else:
    ResultList.append(AList[0])
PrimeList.append(AList[0])


for p in range(1, N - 1):
    tmp = 0
    if AList[p - 1] != AList[p] and AList[p] != AList[p + 1]:
        for q in PrimeList:
            if AList[p] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AList[p])
            PrimeList.append(AList[p])
    else:
        PrimeList.append(AList[p])

tmp = 0
if N > 1:
    if AList[N - 2] != AList[N - 1]:
        for q in PrimeList:
            if AList[N - 1] % q == 0:
                tmp = 1
                break
        if tmp == 0:
            ResultList.append(AList[N - 1])

print(len(ResultList))

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)[::-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:
n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        continue
    for j in range(i+1,n):
        if done[j] == 0:
            if li[j]==li[i]:
                done[i]=1
                done[j]=1
                dp[i]=0
                dp[j]=0
                continue
            elif li[j]%li[i]==0:
                done[j]=1
                dp[j]=0
 
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import defaultdict
# import math
# from itertools import product, accumulate, combinations, product
# import bisect# lower_bound etc
import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba
#import math

def run():
    N = int(input())
    A = list(map(int, sysread().split()))
    NN = 10 ** 6 + 1
    A = sorted(A)
    checks = np.array([True] * NN)
    ret = 0
    for i, a in enumerate(A[:-1]):
        if checks[a] and a != A[i+1]:
            ret += 1
        checks[a:NN+1:a] = False
    if checks[A[-1]]:
        ret += 1


    print(ret)

if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

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

data.sort()

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