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()))
checker = [1 for _i in range(10**6+1)]
a.sort()
a.append(-1)
result = 0
for i in range(n):
    if a[i] == a[i+1]:
        checker[a[i]] = 0
    result += checker[a[i]]
    checker[a[i]] = 0
    x = 2
    while a[i]*x <= 10**6:
        checker[a[i]*x] = 0
        x += 1
print(result)

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)

    for a in A:
        v = 2*a
        while v <= 10**6:
            c[v] += 1
            v += a

    ans = 0
    for a in A:
        if c[a] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]

for x in p:
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
 
c = Counter(p)
for (k,v) in c.items():
    if v>1:
        s.discard(k)
print(len(s))

Submission status: Time Limit Exceeded

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

n = int(input())

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

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []

for i in a:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in a:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

cnt = [0] * ((10**6) + 1)
ans = 0

for i in a:
    for j in range(i, (10**6)+1,i):
        cnt[j] += 1

for i in a:
    if cnt[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=list(map(int,input().split()))
ans=0
for i in range(a):
  for j in range(a):
    if b[i]%b[j]==0 and not i==j:
      break
    elif j==a-1:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=list(map(int,input().split()))
ans=[0]*a
for i in range(a):
  for j in range(a):
    if b[i]%b[j]==0 and not i==j:
      ans[i]=0
      break
    elif j==a-1:
      ans[i]=1
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
#Not Dibvisible
N = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(N):
    flag = True
    for j in range(N):
        if i != j and A[i]%A[j] == 0:
            flag = False
            break
    if flag :
        count += 1
                
print(count)

Submission status: Time Limit Exceeded

Solution code:
_,*a=map(int,open(0).read().split())
a=[i for i in a if a.count(i)==1]
a.sort()
b=0
while a:
    b+=1
    a=[i for i in a[1:] if i%a[0]!=0]
print(b)

Submission status: Time Limit Exceeded

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

B = 0
for i in range(N):
    P = A[i]
    P = int(P)
    C = 0
    for j in range(N):
        Q = A[j]
        Q = int(Q)
        if i != j:
            if not(P % Q == 0):
                C += 1
    if N - 1 == C:
        B += 1

print(B)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
count = 0
for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(N-count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
A.sort()
count = 0
for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(len(A)-count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input()
A = A.split()
A = [int(c) for c in A]
count = 0
for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            count += 1
            break
print(len(A)-count)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
r=0
f=Counter(a)
for i in a:
  ff=0
  for j in range(1,int(pow(i,0.5))+1):
    if(i%j==0):
      if(i//j==i and f[i]>1):
          ff=1
      if((j in f and j!=i) or (i//j  in f and j!=1)):
        ff=1
  if(ff==0):
    r+=1
print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
arr = sorted(list(map(int, input().split())))
ans_list = []
chohuku = [x for x in set(arr) if arr.count(x) > 1]
count_arr = [0]*arr[-1]

ans = 0
for i in arr:
    if count_arr[i-1] == 0:
        ans += 1
        ans_list.append(i)
    for j in range(1,(arr[-1]//i)+1):
        count_arr[(i*j)-1] += 1

for i in ans_list:
    if i in chohuku:
        ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]
prev = 0
for x in p:
    if prev == x:
        s.discard(x)
        continue
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
    prev=x

print(len(s))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
p=sorted(list(map(int,input().split())))
s=set()
m = 10**6+1
a=[True for _ in range(m)]

for x in p:
    if a[x]:
        s.add(x)
    i = 2
    y = i*x
    while y<m:
        a[y] = False
        i+=1
        y = i*x
 
c = Counter(p)
for (k,v) in c.items():
    if v>1:
        s.discard(k)
print(len(s))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
set_a = set(a)
max_a = max(a)
dup_a = {ai for ai in set_a if a.count(ai) > 1}
nd = [True] * (max_a + 1)
cnt = 0
for ai in sorted(list(set_a)):
    if nd[ai] == True and ai not in dup_a:
        cnt += 1
    elif nd[ai] == False:
        continue
    multi = 2
    while ai*multi <= max_a:
        nd[ai*multi] = False
        multi += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
set_l = set(l)
set_l = sorted(set_l)
limit = 10**6
mp = [0]*(limit+1)
pre = None
for i in range(n):
    num = l[i]
    if(pre==num):
        mp[num] += 1
    pre = num

for x in set_l:
    num = x
    while(x <= limit):
        mp[x] += 1
        x += num

cnt = 0
for num in set_l:
    if(mp[num]==1):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted([int(i) for i in input().split()])
set_a = set(a)
max_a = max(a)
dup_a = {ai for ai in set_a if a.count(ai) > 1}
nd = [True] * (max_a + 1)
cnt = 0
for ai in sorted(list(set_a)):
    if nd[ai] == True and ai not in dup_a:
        cnt += 1
    multi = 2
    while ai*multi <= max_a:
        nd[ai*multi] = False
        multi += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    flag = 0
    for j in range(N):
        if i!=j and A[i]%A[j] == 0:
            #print("i=%d,j=%d,A[j]=%d"%(i,j,A[j]))
            flag +=1
            break
    if flag == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
ans = 0
for i in range(N):
    flag = 0
    for j in range(N):
        if i!=j and A[i]%A[j] == 0:
            #print("i=%d,j=%d,A[j]=%d"%(i,j,A[j]))
            flag +=1
    if flag == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
c = [0]*1000001

for i in range(n):
  c[a[i]] -= 1
  for j in range(a[i],1000001,a[i]):
    c[j] += 2

ans=c.count(1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
flag=[1]*N

for i in range(len(A)-1):
    a=A[i]
    for j in range(i+1,len(A)):
        if flag[j]==0: continue
        b=A[j]
        if a==b: flag[i]=0
        if b%a==0: flag[j]=0

print(sum(flag))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
 
import numpy as np

n = int(input())
a = list(map(int,input().split()))
count=0
a.sort()
for i in reversed(a):
	sum=0
	for j in a:
		# print(i,j)
		if i % j == 0 and i!=j:
			break
		elif i % j and i!=j:
			sum=sum+1
	if sum==n-1:
		count=count+1		

print(count)

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(_) for _ in input().split()]
B=[]
C=[]
for i in range(N):
  for j in range(N):
    if A[i]%A[j]==0:
      B.append(i)
for x in set(B):
  if B.count(x)<2:
    C.append(x)
print(len(C))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a.sort()
a=np.array(a)
i = 0
while len(a):
    try:
        if a[0] != a[1]:
            i+=1
    except:
      i+=1
    a = a[a%a[0] != 0]
print(i)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    mat = np.zeros(U + 1, np.int64)
    ret = 0
    exist_counts = [0] * U
    for x in a:
        if exist_counts[x]:
            exist_counts[x] = 2
            continue
        mat[x::x] += 1
    for x in a:
        ret += mat[x] == 1
    print(ret)

main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(_) for _ in input().split()]
B=[]
for i in range(N):
  for j in range(N):
    if A[i]%A[j]==0:
      B.append(i)
C=([x for x in set(B) if B.count(x) < 2])
print(len(C))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    _, primes = prime_table(U)
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    mat = np.zeros(U + 1, np.int64)
    ret = 0
    for x in a:
        mat[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            mat[p * i] += mat[i]
    for x in a:
        ret += mat[x] == 1
    print(ret)
    '''
    N = int(readline())
    a = list(map(int, readline().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)
    '''


def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,*a=map(int,open(0).read().split())
a=np.array(sorted(a))
i = 0
while len(a):
    try:
        if a[0] != a[1]:
            i+=1
    except:
      i+=1
    a = a[a%a[0] != 0]
print(i)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

import numpy as np

U = 10 ** 6 + 10


def main():
    readline = stdin.readline
    N = int(readline())
    a = list(map(int, readline().split()))
    mat = np.zeros(U + 1, np.int64)
    ret = 0
    for x in a:
        mat[x::x] += 1
    for x in a:
        ret += mat[x] == 1
    print(ret)

    
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = map(int,input().split())
a = list(map(int,input().split()))
counter = 0
for s,i in enumerate(a):
  start = 0
  for t,j in enumerate(a):
    if i % j == 0 and s != t:
      start = 1
  if start == 0:
    counter+=1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import copy

def run(n, num_array):
    '''
    '''
    # results = []
    # array_len = len(num_array)
    #   table = [](l(array_len)
    #   w if len([j for j in range(array_len) if j != i and num_array[i]%num_array[j] == 0]0: # i:
    #         continueが n の約数である場合、 n/i も n の約数
    #     results.append(i+1)
    
    # print(len(results))

    def divisor(n):
        i = 1
        table = []
        while i * i <= n:
            if n%i == 0: # i が n の約数である場合、 n/i も n の約数
                table.append(i)
                table.append(n//i)
            i += 1
        return set(table)
    
    count = 0
    for i in range(len(num_array)):
        _list = copy.deepcopy(num_array)
        del _list[i]
        if len(divisor(num_array[i]) & set(_list)) >= 1:
            continue
        count += 1

    print(count)

if __name__ == "__main__":
    n = int(input())
    num_array = list(map(int, input().split()))
    run(n, num_array)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
count=0
a.sort()
for i in reversed(a):
	sum=0
	for j in a:
		if i % j == 0 and i!=j:
			break
		elif i % j and i!=j:
			sum=sum+1
	if sum==n-1:
		count=count+1		

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = [int(x) for x in input().split()]
M = max(Alist)
A0 = ['NotUse']
Abool = A0 + [0 for x in range(M)]
Alist.sort()
ans = 0

for i in Alist:
    for j in range(M+1):
        if j == 0:
            None
        elif Abool[j] >= 2:
            None
        else:
            if j % i == 0:
                Abool[j] += 1
    
for i in Alist:
    if Abool[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def run(n, num_array):
    '''
    '''
    results = []
    array_len = len(num_array)
    for i in range(array_len):
        if len([j for j in range(array_len) if j != i and num_array[i]%num_array[j] == 0]) != 0:
            continue
        results.append(i+1)
    
    print(len(results))


        

if __name__ == '__main__':
    n = int(input())
    num_array = list(map(int, input().split()))
    run(n, num_array)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

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

A.sort()

dp = {a: True for a in A}

ans = N
for i, a_i in enumerate(A):
    if not dp[a_i]:
        continue

    for a_j in A[i + 1:]:
        if a_j % a_i == 0:
            dp[a_j] = False

ans = 0
for flag in dp.values():
    if flag:
        ans += 1

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):
	sum=0
	for j in range(n):
		if i!=j and a[i] % a[j] == 0:
			break
			
		elif i!=j and a[i] % a[j] !=0:
			sum=sum+1
			
	if sum==n-1:
		count=count+1		

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
b = collections.Counter(a)
b = set(b)
check = [0 for i in range(10 ** 6 + 1)]
for i in a:
    check[i] += 1
    for j in range(i * 2, 10 ** 6 + 1, i):
        check[j] += 2
ans = 0
for g in list(b):
    if check[g] == 1:
        ans += 1
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):
	sum=0
	for j in range(n):
		if i!=j and a[i] % a[j] != 0:
			sum=sum+1
			
	if sum==n-1:
		count=count+1		

print(count)

Submission status: Time Limit Exceeded

Solution code:
#import math
#=input()
n=int(input())
#=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

def div(x):
    lm,li = [],[]
    i = 1
    while i ** 2 <= x:
        if x % i == 0:
            lm.append(i)
            if i != x // i:
                li.append(x//i)
        i += 1
    return lm + li[::-1]

cnt = 0
for i in range(n):
    z = div(a[i])
    l = list(a)
    l.remove(a[i])
    q = 0
    for j in range(len(z)):
        if z[j] in l:
            q = 1
            break
    if q == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 20 16:25:37 2020

@author: naoki
"""

N = int(input()) # the number of integers
A = list(map(int,input().split())) # the row of integers
A.sort() # sorting the contents of the row from small numbers 
count = 0 

# the smallest number is not divided by any numbers in the row except for the same number 
for i in range(N): # the divided number
    k=0
    while  (A[i] % A[k] != 0 or k == i) and k<=min(i+1,N-1): # if divisible, drop out the loop                  
        if k==min(i+1,N-1):
            count+=1
            break
        else:
            k+=1
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
y = list(map(int, input().split()))
tf = [bool(z+1) for z in range(x)]
y.sort()

for a in range(x-1):
    if tf[a]==True:
        for b in range(a+1,x):
            if tf[b]==True:
                if y[a]==y[b]:
                    tf[a]=False
                if y[b]%y[a]==0:
                    tf[b]=False

print(sum(tf))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
X=[A[0]]
if N>1 and A[0]==A[1]:
  ans=0
else:
  ans=1
f=True
if A[0]==1:
  if N>1 and A[0]==A[1]:
    print(0)
  else:
    print(1)
  exit(0)
for i in range(1,N):
  if A[i]==A[(i+1)%N]:
    f=False
    continue
  
  F=True
  for x in X:
    if A[i]%x==0:
      F=False
      break
  if F:
    X.append(A[i])
    if f:
      ans+=1
  f=True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
number = int(input())
# values = [i+2 for i in range(2*10**5)]
values = list(map(int, input().split()))

maxV = 10**6+1
dp = [0]*(maxV)

for a in values:
    i = 1
    if dp[a] > 1:
        continue
    while i * a < maxV:
        i_a = i * a
        dp[i_a] = dp[i_a] + 1
        i += 1

count = 0
for a in values:
    if dp[a] == 1:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=sorted(list(map(int,input().split())))
X=[A[0]]
if N>1 and A[0]==A[1]:
  ans=0
else:
  ans=1
f=True
for i in range(1,N):
  if A[i]==A[(i+1)%N]:
    f=False
    continue
  
  F=True
  for x in X:
    if A[i]%x==0:
      F=False
      break
  if F:
    X.append(A[i])
    if f:
      ans+=1
  f=True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split())) 
A.sort()
ans = [0] * (10**6+1)
watched = set()
for i in A:
    ans[i] = 1
for i in range(N-1):
    if A[i] == A[i+1]:
        ans[A[i]] = 0
    temp = A[i]
    if temp in watched:
        continue       
    for j in range(i+1, N):
        if A[j]%temp == 0:
            ans[A[j]] = 0
            watched.add(A[j])
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy
N=int(input())
A=list(map(int,input().split()))
A.sort()
n=max(A)
cnt=0

while A:
    p=A[0]
    tmp=[]
    flg=True
    for i in range(1,len(A)):
        if A[i]%p!=0:
            tmp.append(A[i])
        if p==A[i]:
            flg=False
    if flg:
        cnt+=1
    A=copy.deepcopy(tmp)


print(len(A)+cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
list(set(a))
a.sort()
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  if(a.count(a[i]) >= 2):
    continue
  if(2 in a and a[i] % 2 == 0):
    continue
  flg = False
  for j in range(i):
    if(a[i] % a[j] == 0):
      flg = True
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#import math
#=input()
n=int(input())
#=map(int,input().split())
a=list(map(int,input().split()))
#=[list(map(int,input().split())) for _ in range()]

cnt = 0
for i in range(n):
    z = a[i]
    l = list(range(n))
    del l[i]
    q = 0
    for j in l:
        x = a[j]
        if z % x == 0:
            q = 1
            break
    if q == 0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

y.sort()
remove = []
ans = []

while len(y) > 0:
    for i in range(1,len(y)):
        if y[i] % y[0] == 0:
            remove.append(y[i])
    if len(y)>1 and y[0] == y[1]:
        remove.append(y[0])
    else:
        ans.append(y.pop(0))
    while len(remove) != 0:
        y.remove(remove.pop(0))
    

print(len(ans))

Submission status: Time Limit Exceeded

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

A.sort()
So = [True] * N

for i in range(N):
  if not So[i]:
    if i>0 and A[i-1] == A[i]:
      So[i-1] = False
    continue
  val = A[i]
  for j in range(i+1,N):
    if not So[i]:
      continue
    if A[j] % val == 0:
      So[j] = False
      
      
ans = 0
for i in range(N):
  if So[i]:
    ans += 1
#print(So)
print(ans)

Submission status: Time Limit Exceeded

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

A.sort()
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li1 = list(map(int, input().split()))
li1 = sorted(li1)
re = 0
for i in range(n):
    check = 0
    for i2 in range(n):
        if i != i2:
            if li1[i] == li1[i2]:
                check = 1
        if i > i2:
            if li1[i] % li1[i2] == 0:
                check = 1
        if check == 1:
            break
    if check == 0:
        re += 1
print(re)

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, (input().split())))
A.sort()
cnt = np.zeros(10**6+10, dtype=np.int32)
for i in range(N):
    cnt[A[i]] += 1
for i in range(N-1):
    if cnt[A[i]] != 0:
        cnt[A[i]*2::A[i]] = 0
ans = np.count_nonzero(cnt==1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li1 = list(map(int, input().split()))
re = 0
for i in range(n):
    check = 0
    for i2 in range(n):
        if i != i2:
            if li1[i] % li1[i2] == 0:
                check = 1
        if check == 1:
            break
    if check == 0:
        re += 1
print(re)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li1 = list(map(int, input().split()))
re = 0
for i in range(n):
    check = 0
    for i2 in range(n):
        if i != i2:
            if li1[i] % li1[i2] == 0:
                check = 1
    if check == 0:
        re += 1
print(re)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort(reverse=True)
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[-1:i:-1]:
    # print(v[0], vv[0])
    if v[0] / 2 < vv[0]:
      break
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
readline()
b = list(map(int, readline().split()))

b.sort(reverse=True)
# print(b)

x = len(b)
c = [(k, len(tuple(L))) for k, L in groupby(b)]
# print(c)
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[-1:i:-1]:
    # print(v[0], vv[0])
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

Submission status: Time Limit Exceeded

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

dp = [True for _ in range(max(a) + 1)]
ans = 0
y = -1
for x in a:
    if x == y:
        continue
    y = x

    if x in a_set:
        ans += 1 if dp[x] else 0

    while y <= max(a):
        dp[y] = False
        y += x

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import groupby

readline = sys.stdin.buffer.readline
a = map(int, readline().split())
b = list(map(int, readline().split()))
b.sort(reverse=True)

x = len(b)
c = [(k, len(list(L))) for k, L in groupby(b)]
for i, v in enumerate(c):
  if v[1] > 1:
    x -= v[1]
    continue
  for vv in c[i+1:]:
    if not v[0] % vv[0]:
      x -= 1
      break
print(x)

Submission status: Time Limit Exceeded

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

a.sort()
a_set = set(a)
for i in range(n-1):
    if a[i] == a[i + 1]:
        if a[i] in a_set:
            a_set.remove(a[i])

dp = [True for _ in range(max(a)+1)]
y = -1
for x in a:
    if x == y:
        continue
    y = 2*x
    while y <= max(a):
        dp[y] = False
        y += x

ans = 0
for x in list(a_set):
    ans += 1 if dp[x] else 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=A[0]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==True: 
    if a not in A:
      ans+=1
    k=a
    while k<=max_a:
      dp[k]=False    
      k+=a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=A[0]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==True: 
    if a not in A:
      ans+=1
    i=1
    k=a
    while k<=max_a:
      dp[k]=False
      i+=1
      k=a*i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=A[0]
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==False:
    continue
  if a not in A:
    ans+=1
  i=1
  k=a
  while k<=max_a:
    dp[k]=False
    i+=1
    k=a*i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
max_a=max(A)
dp=[True]*(max_a+1)
ans=0
for i in range(N):
  a=A.pop()
  #print(a)
  if dp[a]==False:
    continue
  if a not in A:
    ans+=1
  i=1
  k=a
  while k<=max_a:
    dp[k]=False
    i+=1
    k=a*i
print(ans)

Submission status: Time Limit Exceeded

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

y.sort()
ans = []
while len(y) != 0:
    judge = y.pop(0)
    remove = []
    if len(y) == 0:
        ans.append(judge)
        break;
    if judge != y[0]:
        ans.append(judge)
    for i in y:
        if i % judge == 0:
            remove.append(i)
    for i in remove:
        y.remove(i)
        
            
print(len(ans))

Submission status: Time Limit Exceeded

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

y.sort()
ans = [bool(a+1) for a in range(x)]

for i in range(x-1):
    if ans[i] == True:
        if y[i] == y[i+1]:
            ans[i] = False
        for j in range(i+1 ,x):
            if (ans[j] == True) and (y[j]%y[i]==0):
                ans[j] = False

print(sum(ans))

Submission status: Time Limit Exceeded

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

y.sort()
ans = [bool(a+1) for a in range(x)]

for i in range(x-1):
    if y[i] == y[i+1]:
        ans[i] = False
    for j in range(i+1 ,x):
        if (ans[j] == True) and (y[j]%y[i]==0):
            ans[j] = False

print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n = int(input())
c = Counter(map(int, input().split()))
s = set()
for i in c:
    c[i] -= 1
    for j in range(i, 10**6+1, i):
        if c[j]:
            s.add(j)
    c[i] += 1
r = 0
for i in c:
    r += c[i] * (i not in s)
print(r)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
ans=[]
k=0
for i in range(0,n):
  for j in range(0,n):
    if(i != j and l[i] %l[j] ==0):
      k=0
      break
    else:k=1
  
  if(k==1):ans.append(i)
    
print(len(set(ans)))

Submission status: Time Limit Exceeded

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

ans = 0

for i, j in enumerate(y):
    for k, l in enumerate(y):
        if (k != i) and (j % l == 0):
            break;
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i, j in enumerate(y):
    for k, l in enumerate(y):
        if k != i and j % l == 0:
            break;
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0

for i, j in enumerate(y):
    for k, l in enumerate(y):
        if k == i or j % l != 0:
            pass
        else:
            break;
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

ans = list()
for i in range(N):
        for j in range(N):
            if i == j:
                continue
            else:
                if A[i]%A[j] == 0:
                    ans.append(A[i])
                    break
print(N-len(ans))