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:
import numpy as np

input()
A = np.fromstring(input(), int, sep=' ')
A.sort()

f = np.ones_like(A, dtype=bool)
count = 0
for i, x in enumerate(A):
    if not f[i]:
        continue
    count += 1
    f[i+1:] &= (A[i+1:] % x != 0)

    if i != len(A)-1 and A[i] == A[i+1]:
        count -= 1

print(count)

Submission status: Time Limit Exceeded

Solution code:

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

ans=0

for i in range(N):
    Acp=A.copy()
    kkk=Acp.pop(i)
    a=set(make_divisors(A[i]))
    b = a&set(Acp)
    if len(b)==0:
        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 a:
	count=0
	b=a.copy()
	b.remove(i)
	for j in b:
		if i%j==0:
			count+=1
			break
	if count==0:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
memo = {}
ans = 0

for a in A:
    if not a in memo:
        flag = True
        for div in memo:
            if a % div == 0:
                flag = False
                break
        if flag:
            ans += 1
            memo[a] = 1
    else:
        if memo[a] == 1:
            ans -= 1
            memo[a] += 1
        else:
            continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n= int(input())

a_s= np.array(input().split(' '))

count=0

def f(index):
	A= int(a_s[index])
	for index2 in range(n):
		if index2!=index:
			if A% int(a_s[index2])==0:
				return False
	return True


for index in range(n):
	if f(index):
		count+=1
print(count)

Submission status: Time Limit Exceeded

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

k=0
for i in range(N):
  t=0
  for h in range(N):
    if S[i]%S[h]==0:
      t+=1
  if t==1:
    k+=1 
print(k)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
array = list(map(int, input().split()))
count = 0
for i in range(n):
    judge = 1
    ai = array[i]
    for j in range(n):
        aj = array[j]
        if j == i:
            continue
        if ai % aj == 0:
            judge *= 0
            continue
    if judge != 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
A_list = list(map(int, input().split()))
sorted_A_list = sorted(A_list)

ans = 0

#print(sorted_A_list)

for i in range(N):
    ans = ans+1
    if not i == N-1:
        if sorted_A_list[i] == sorted_A_list[i+1]:
            ans = ans-1
            continue
    for j in range(i):
        if sorted_A_list[i]%sorted_A_list[j] == 0:
            ans = ans-1
            #print(sorted_A_list[i])
            break

print(ans)

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]%a[j] != 0 or i == j for j in range(n)]
    if False in tmp:
        continue
    else:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
    C = Counter(A)
    U = set()
    ans = 0
    for e in A:
        if C[e] > 1:
            U.add(e)
        else:
            flag = 1
            for f in U:
                if e%f == 0:
                    flag = 0
                    break
            if flag == 1:
                ans += 1
            U.add(e)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
flags = [1] * n
for i in range(1, n):
    for j in range(i):
        if A[i] == A[j]:
            flags[i] = 0
            flags[j] = 0
        if A[i] % A[j] == 0:
            flags[i] = 0
            break
print(sum(flags))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
A.sort()
s=set()
B=[]
while A:
    x=A.pop()
    if A:
        if x!=A[-1]:
            s.add(x)
            B.append(x)
        else:
            s.add(x)
            while A:
                y=A.pop()
                if y!=x:
                    A.append(y)
                    break
    else:
        s.add(x)
        B.append(x)
        
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]

ans=0
for x in B:
    div=make_divisors(x)
    for j in div:
        if j==1:
            if x==1:
                continue
            else:
                if j in s:
                    break
        elif j==x:
            continue
        elif x%j==0:
            if x//j in s or j in s:
                break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

X.sort()
Y=[]
onaji=0
pre=-1
for x in X:

    if x==pre:
        onaji+=1
        pre=-1

    flag=0#warenai

    for y in Y:
        if x%y==0:
            flag=1#wareta

    if flag==0:#全部われなかった
        Y.append(x)
        pre=x

print(len(Y)-onaji)

Submission status: Time Limit Exceeded

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

flag = [True]*n
for i in range(n):
  for j in range(i+1,n):
    if flag[i] == True and flag[j] == True:
      if A[i]%A[j] == 0:
        flag[i] = False
      if A[j]%A[i] == 0:
        flag[j] = False
print(flag.count(True))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque, Counter
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def prime_factorize(n):
    """
    素因数分解
    
    Sample:
        prime_factorize(36)
        => [2, 2, 3, 3]

        collections.Counter(prime_factorize(36))
        => {2:2, 3:2}
    """
    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

    if len(arr) == 0:
        arr.append((n, 1))
    return arr

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]

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()
C = Counter(A)
# log(C)

ans = 0

for i,a in enumerate(A):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            if C[d] > 1:
                # log(C[d])
                ok = False
                break
        elif d in C:
            ok = False
            break
    if ok:
        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())
a = list(map(int, input().split()))
res = 0
for i in range(n):
    s = make_divisors(a[i])
    aa = a[:i] + a[i + 1:]
    l = set(s) & set(aa)
    if len(l) == 0:
        res += 1
print(res)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
a = list(map(int,input().split()))
a.sort()
c = Counter(a)
res = 1
divisors = [a[0]]
if N==1:
    print(1)
    exit()
if a[0]==a[1]:
    if a[0]==1:
        print(0)
        exit()
    else:
        res = 0
t = []
for k,v in c.items():
    if v>=2:
        divisors.append(k)
    else:
        t.append(k)
for tgt in t:
    flg = 1
    for dv in divisors:
        if tgt%dv==0:
            flg = 0
            break
    if flg==1:
        res += 1
        divisors.append(tgt)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


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

    return sorted(ans)


def main():
    N = int(input())

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

    is_in_A_flag = [0] * (10**6+1)

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

    B = [None] * N
    for i in range(N):
        B[i] = yakusu(A[i])

    ans = 0
    for i in range(N):
        is_ans = True
        # for b in B[i][:-1]:
        for j in range(len(B[i])-1):
            b = B[i][j]
            if is_in_A_flag[b] > 0:
                is_ans = False
                break

        if is_ans:
            if is_in_A_flag[B[i][-1]] > 1:
                is_ans = False

        if is_ans:
            ans += 1

    return ans


print(main())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=input()
a0=a.split()
al=list()
k=0
for i in range(n):
    al.append(int(a0[i]))
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
print(k)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  i = 2
  if Adic[temp] >= 2:
    continue
  while i*i <= temp:
    #print(i,temp)
    if temp%i == 0:
      #print(i,temp//i,temp)
      if i in Aset or temp//i in Aset:
        Flag = False
        #print(i,temp//i,"X")
        break
    i += 1
  if not Flag:
    continue
  ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

alist.sort()

count = 0

for i in range(0, N):
  
  a = alist[i]
  flag = 0
  
  if i != N - 1:
    if alist[i + 1] == a:
      continue
      
  if i != 0:
    if alist[i - 1] == a:
      continue

  for j in range(i):
    b = alist[j]
    
    if a % b == 0:
      flag = 1
      break
        
  if flag == 0:
    count += 1
      
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


cnt=0
for i in range(n):
    flg=0
    for j in range(n):
        if i==j:
            continue

        if a[i]%a[j]==0:
            flg+=1

    if flg==0:
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
ansList = [1]*n

for i in range(n):
    if ansList[i] == 1:
        for j in range(i+1,n):
            if a[i]%a[j] == 0:
                ansList[i] = 0
            if a[j]%a[i] == 0:
                ansList[j] = 0

c = Counter(ansList)
print(c[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=map(int, input().split())
*a,=map(int, input().split())
sa=Counter(a)

def fct(x):
    f1=[1]
    f2=[]
    for i in range(2,min(int(x**(1/2)+7),x)):
        if x%i==0:
            f1.append(i)
            f2.append(x//i)
    return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    fa=fct(ai)
    ad=True
    for f in fa:
        if f in sa and f!=ai:
            ad=False
            break
    if ad:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7


def get_divisors(n):
    divs = []
    for i in range(2, int(n**0.5)+1):
        c = 0
        while n % i == 0:
            n = n // i
            c += 1
        if c > 0:
            divs.append((i, c))
    if n > 1:
        divs.append((n, 1))
    return divs

N = ri()
A = rl()

import collections
H = collections.defaultdict(set)
D = []
for i, a in enumerate(A):
	divs = get_divisors(a)
	D.append(divs)
	for d, c in divs:
		for j in range(1, c+1):
			k = pow(d, j)
			H[k].add(i)

del_list = set()
for i, divs in enumerate(D):
	s = set(range(N))
	for d, c in divs:
		for j in range(1, c+1):
			k = pow(d, j)
			s &= H[k]
	del_list |= s - set([i])
print(N-len(del_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 0
divs = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(i+1, n):
    if a[i] % a[j] != 0:
      divs[i][j] = 1
    if a[j] % a[i] != 0:
      divs[j][i] = 1
  
  if sum(divs[i]) == n-1:
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
seq=LI()
seq.sort()
c=Counter(seq)
lis=[seq[0]]
for i in range(1,n):
    count=0
    for x in lis:
        if seq[i]%x!=0:
            count+=1
    if count==len(lis):
        lis.append(seq[i])
#print(lis)
ans=len(lis)
for x in lis:
    if c[x]>1:
        ans-=1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    divisible = False
    for j in range(N):
        if i!=j:
            if As[i] < As[j]:
                # Ajのほうが大きければ、割り切れない
                continue
            if (As[i] % As[j]) == 0:
                # Ajで割り切れた
                divisible = True
                break
    if divisible == False:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

P = [0]*(1000001)
for i in a: P[i] += 1


def check(N,P):
    if N == 1:
        if P[1]==1: return True
        else: return False

    if P[1] >= 1: return False
    if P[N] >= 2: return False
    i = 1
    
    for i in range(2,N):
        if i*i >= N: break
        if N%i == 0:
            #print(i,N)
            if P[i]>=1: return False
            if P[N//i]>=1: return False
    if i*i == N:
        if P[i]>=1: return False

    return True    

ans = 0
for N in a:
    if check(N,P): ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = [int(_c) for _c in input().split(" ")]

a_list_set = sorted(set(a_list))

answers = []
for a in a_list_set:
    if len(answers) == 0:
        answers.append(a)
        continue

    append_num = True
    for answer in answers:
        if a % answer == 0:
            append_num = False
            break
    if append_num:
        answers.append(a)

res = 0
for _answer in answers:
    if a_list.count(_answer) == 1:
        res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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


main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
table = [True for i in range(N)]
for i in range(N):
    if table[i]:
        if i < N-1 and A[i] == A[i+1]:
            table[i] = False
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                table[j] = False
print(table.count(True))

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):
  if A[i] == 0:
    continue
  else:
    if i == N - 1 or (i < N - 1 and A[i] != A[i+1]):
      ans += 1
    for j in range(i+1, N):
      if A[j] % A[i] == 0:
        A[j] = 0
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):
    count = 0
    for j in range(n):
        if a[i] % a[j] == 0:
            count += 1
    if count == 1:
        ans += 1
        #print(a[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse = True)
ans = 0
while A:
    a = A.pop(-1)
    if not A or a != A[-1]:
        ans += 1
    A = [i for i in A if i%a != 0]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)
    A = set(A)

    def trial_division(n):
        divs = set()
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divs.add(i)
                if i != n//i:
                    divs.add(n//i)
        divs.discard(n)
        return divs

    ans = 0
    for a in A:
        if a in bl:
            continue
        divs = trial_division(a)
        if not A & divs:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
for i in range(n):
    flag=0
    if i<len(a):
        j=i+1
        while j <len(a):
            if a[j]==a[i]:
                flag=1
            if a[j]%a[i]==0:
                a.pop(j)
            else:
                j+=1
        if flag==0:
            ans+=1
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

#nを素因数分解したリストを返す
def prime_decomposition(n):
    table=[]
    for i in range(1,n+1):
        if n%i==0:
            table.append(i)
    return table


#n=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(n):
    temp=prime_decomposition(a[i])
    atemp=a.copy()
    atemp.pop(i)
    for j in range(len(temp)):
        if temp[j] in atemp:
            count+=1
            break
print(n-count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6+1)]
for i in range(n):
  l[a[i]]+=1
ans=0
for i in range(n):
  x=a[i]
  if l[a[i]]==1:
    flag=1
    for j in range(1,int(x**0.5)+2):
      if x%j==0:
        if x!=j and l[j]>0:
          flag=0
          break
        if x!=x//j and x%(x//j)==0 and l[x//j]>0:
          flag=0
          break
    if flag==1:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(i) for i in input().split()]
A.sort()
ans = 0
ans_list = []
kaburi = {}
for i in A:
    Flag = True
    for j in ans_list:
        if i==j:
            kaburi[i]=True
            Flag = False
            break
        if i%j==0:
            Flag = False
            break
    if Flag:
        ans_list.append(i)
        ans += 1
print(ans-len(kaburi))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
A = sorted(list(map(int, input().split())))
c = Counter(A)
result = 0
piyo = []
for k, v in c.items():
    if v > 1:
        piyo.append(k)
        A.remove(k)
for a in A:
    flag = False
    for hoge in piyo:
        if a % hoge == 0:
            flag = True
            break
    if not flag:
        piyo.append(a)
        result += 1
print(result)

Submission status: Time Limit Exceeded

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


def resolve():
    from collections import Counter
    import sys
    input = sys.stdin.readline
    _ = int(input())
    a = list(map(int, input().split()))
    c = Counter(a)
    s = set(a)
    ans = 0
    for i in s:
        if c[i] >= 2:
            continue
        for j in make_divisors(i):
            if j in s and j != i:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

ctr = Counter(A)
memo = set()
ans = 0

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

    for i in range(1, int(a ** 0.5) + 1):
        if a % i == 0:
            if (i in memo) or (a // i in memo):
                break
    else:
        if ctr[a] == 1:
            ans += 1

    memo.add(a)
        
print(ans)

Submission status: Time Limit Exceeded

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

print(sum(is_ok))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter

setrecursionlimit(10 ** 7)

n = int(stdin.readline().rstrip())
a = list(map(int,stdin.readline().rstrip().split()))
a.sort()
c = Counter(a)

se = set()

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 in a:
    k = make_divisors(i)
    flag = True
    for j in k:
        if j in se:
            flag = False
    if flag:
        se.add(i)

point = len(se)

for i in se:
    if c[i] > 1:
        point -= 1

print(point)

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
A=list(map(int,input().split()))
from math import sqrt
s=set()
A.sort()
a=0
t=0
if A[0]!=1:
    for i in A:
        if i in s:
            if t==i:
                a-=1
                t=0
            continue
        s.add(i)
        for j in range(2,int(sqrt(i)+1.5)):
            if i%j:
                continue
            if j in s:
                break
            if i//j in s:
                break
        else:
            t=i
            a+=1
else:
    if N>1 and A[1]==1:
        a=0
    else:
        a=1
print(a)

Submission status: Time Limit Exceeded

Solution code:
#d
n = int(input())
a = list(map(int, input().split()))
a_l = sorted(a)
count = 0
for i in range(len(a_l)):
    flag = 0
    if a_l.count(a_l[i])>1:
        flag=1
    for j in range(i):
        if a_l[i] % a_l[j] == 0:
            flag = 1
            break
    if flag == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
X=10**6+1
E=[1 for i in range(X)]
E[0]=0
N=int(input())
A=list(map(int,input().split()))

import copy
B=copy.deepcopy(A)
B.sort()

D={}
for i in range(N):
    if A[i] not in D:
        D[A[i]]=1
    else:
        D[A[i]]=2
ANS=0
for i in range(N):
    if D[B[i]]==2:
        for j in range(1,10**7):
            if B[i]*j>=len(E):
                break
            else:
                E[B[i]*j]=0
    else:
        if E[B[i]]!=0:
            ANS+=1
            for j in range(1,10**7):
                if B[i]*j>=len(E):
                    break
                else:
                    E[B[i]*j]=0
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
b=list(map(int,input().split()))
a=dict()
for i in b:
    if i not in a:
        a[i]=1
    else:
        a[i]+=1
ans=0
for k in b:
    divisors=[]
    for i in range(1,int(k**0.5)+1):
        if k%i==0:
            divisors.append(i)
            if i!=k//i:
                divisors.append(k//i)
    for j in divisors:
        if (j in a and j!=k)or(j==k and a[j]>1):
            break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            break
        else:
            pass
        if j == n - 1:
                p += 1

print(p)