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:
#brute force

n=int(input())
arr=list(map(int,input().split()))
short={}
for i in arr:
    if i not in short:
        short[i]=1
    else:
        short[i]+=1

count=0
for i in short:
    if short[i]==1:
        for j in short:
            if i%j==0 and i!=j:
                count+=1
                break
    else:
        count+=short[i]

ans=n-count
print(ans)

Submission status: Time Limit Exceeded

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

element1=[]
for u in range(N):
    for i in range(N):
        amari=A[u]%A[i]
        if A[u]<A[i]:
            continue
        if amari  == 0 :
            if i==u:
                continue
            element1.append(A[u])
a=set(A)^set(element1)
print(len(a))

Submission status: Time Limit Exceeded

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

element1=[]
for u in range(N):
    for i in range(N):
        amari=A[u]%A[i]
        if amari  == 0 :
            if i==u:
                continue
            element1.append(A[u])
a=set(A)^set(element1)
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n=int(input())
    ar=inpt()
    d=defaultdict(int)
    for i in ar:
        d[i]+=1
    #print(d)
    ar.sort(reverse=True)
    ct=0
    #print(ar)
    for i in ar:
        bl=False
        for j in range(1,int(i**(0.5))+1):
            if(i%j==0):
               #print('>>',i)
               if(j in d):
                   if(j==i and d[j]>1):
                       bl=True
                   elif(j!=i):
                       bl=True
               if (i // j in d):
                   #print(j, i // j)
                   if (i // j == i and d[i // j] > 1):
                       bl = True
                   elif(i // j != i):
                       bl = True

            if (bl == True):
                break
        if(bl==False):
            ct+=1
    print(ct)













BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
suretsu = list(map(int, input().split()))
# N = 5
# suretsu = [24, 11, 8, 3, 16]
count = 0

for i in range(N):
    check = suretsu[i]
    hanbetsu = 1
    for j in range(N):
        waru = suretsu[j]
        if i == j:
            continue
        elif check % waru == 0:
            hanbetsu = 0
    if hanbetsu:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [i for i in map(int, input().split(" "))]

target_count = 0
for index in range(N):
    target = nums[index]
    divisible_count = 0
    for num in nums:
        residue = target % num
        if residue ==0:
            divisible_count +=1
        if divisible_count>=2:
            break
    if divisible_count ==1:
        target_count+=1

print(target_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [i for i in map(int, input().split(" "))]

target_count = 0
for index in range(N):
    target = nums[index]
    divisible_count = 0
    for num in nums:
        residue = target % num
        if residue ==0:
            divisible_count +=1
    if divisible_count==1:
        target_count+=1

print(target_count)

Submission status: Time Limit Exceeded

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

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_array = list(map(int, input().split()))
ans = 0

for i in range(N):
    Ai = A_array[i]
    for j, Aj in enumerate(A_array):
        if j == i:
          if j == N-1:
            ans += 1
          else:
            continue
        else:
            if Ai % Aj == 0:
              break
            elif j == N - 1:
              ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
dp = [True for i in range(max(A) + 1)]
c = Counter(A)
s = set(A)
ans = 0
for i in s:
    TMP = i * 2
    while TMP <= max(A):
        dp[TMP] = False
        TMP += i
for i in s:
    if c[i] == 1 and dp[i] == True:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
dp = [True for i in range(max(A) + 1)]
c = Counter(A)
s = set(A)
ans = 0
for i in s:
    TMP = i * 2
    while TMP <= max(A):
        dp[TMP] = False
        TMP += i
for i in s:
    if c[i] == 1 and dp[i] == True:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = sorted(list(map(int, input().split())))
dp = [True for i in range(max(A) + 1)]
dp[0] = False
c = Counter(A)
ans = 0
for i in set(A):
    for j in range(2, (max(A) // i) + 1):
        if not dp[i * j]:
            continue
        else:
            dp[i * j] = False

for i in set(A):
    if c[i] == 1 and dp[i]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [0]*(max(a) + 1)
ans = 0

for i in a:
    for j in range(i, max(a) + 1, i):
        l[j] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
for a in A:
  B = []
  for b in A:
    B.append(a%b)
  if B.count(0) == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k
    
def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if b == 1:
                return 0 if p.count(1) > 1 else 1
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p))

Submission status: Time Limit Exceeded

Solution code:
import sys

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p))

Submission status: Time Limit Exceeded

Solution code:
import sys

def Not_Divisible(n,p):
    k=0
    for i,a in enumerate(p):
        for j,b in enumerate(p):
            if  i != j and a % b == 0:
                k-=1
                break
        k+=1
    return k

if __name__ == '__main__':
    input = sys.stdin.readline
    
    inp1 = input().rstrip()
    n = int(inp1)

    inp2 = input().rstrip().split()
    p = list(map(int,inp2))
    print(Not_Divisible(n,p))

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)
s = []
m = max(a) + 1
ans = 0
for ai in a:
    if ai in s:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        s.insert(0, i)
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)
s = []
m = max(a) + 1
ans = 0
for i in a:
    if i in s:
        continue
    if c[i] == 1:
        ans += 1
    for i in range(i, m, i):
        s.append(i)
print(ans)

Submission status: Time Limit Exceeded

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

A.sort()
B=[1]*n

from math import sqrt
def eratosu():
  # if not isinstance(n,int):
  #   raise TypeError("nがint型になってねえぞ")
  # if n<2:
  #   raise ValueError('nが2よりちっちぇえぞ')
  primec = 0
  # limit = sqrt(n)
  data = A  #2,3,4,...,n
  while len(data)>0:
    p = data[0]
    # if limit <= p:
    #     return prime + data
    if len(data)>1:
        if data[1]==p:
            primec-=1
    primec+=1 
    data = [e  for e in data if e % p != 0]
  return primec 

# for i in range(n):
#     if i>0:
#         if A[i]==A[i-1]: B[i]=0 ; B[i-1]=0 ; continue
    # if B[i]==1:
    #     for j in range(i+1,n):
    #         if A[j]%A[i]==0:
    #             B[j]=0
print(eratosu())

# print(sum(B))

Submission status: Time Limit Exceeded

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

A.sort()
B=[1]*n

from math import sqrt
def eratosu():
  # if not isinstance(n,int):
  #   raise TypeError("nがint型になってねえぞ")
  # if n<2:
  #   raise ValueError('nが2よりちっちぇえぞ')
  primec = 0
  # limit = sqrt(n)
  data = A  #2,3,4,...,n
  while len(data)>0:
    p = data[0]
    # if limit <= p:
    #     return prime + data
    if len(data)>1:
        if data[1]==p:
            primec-=1
    primec+=1 
    data = [e  for e in data if e % p != 0]
  return primec 

for i in range(n):
    if i>0:
        if A[i]==A[i-1]: B[i]=0 ; B[i-1]=0 ; continue
    # if B[i]==1:
    #     for j in range(i+1,n):
    #         if A[j]%A[i]==0:
    #             B[j]=0
print(eratosu())

# print(sum(B))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
 
dp = [True] * n
cnt = 0
for i in range(n):
    for j in range(n):
        if i==j:
            continue

        if dp[j]:
            if a[j]%a[i]==0:
                cnt += 1
                dp[j] = False

ans = n - cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
 
dp = [True] * n
for i in range(n):
    for j in range(n):
        if i==j:
            continue
            
        if dp[j]:
            if a[j]%a[i]==0:
                dp[j] = False

cnt = 0
for i in range(n):
    if dp[i]:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

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

cnt = Counter(a)
a.sort()

cand = a
ans = 0
while cand:
    p = cand[0]
    if cnt[p] == 1:
        ans += 1
    nex = []
    for num in cand:
        if num == p:
            continue
        if num % p:
            nex.append(num)
    cand = nex

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

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

cnt = Counter(a)
a = list(set(a))
a.sort()

def eratosthenes(a):
    cand = a
    ans = 0
    while cand:
        p = cand[0]
        if cnt[p] == 1:
            ans += 1
        nex = []
        for num in cand:
            if num == p:
                continue
            if num % p:
                nex.append(num)
        cand = nex
    return ans

print(eratosthenes(a))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    dp = [True for i in range(10**6+10)]
    ans = 0
    a.append(10000000000)
    for i in range(n):
        if a[i] == a[i+1]:
            dp[a[i]] = False
        if dp[a[i]]:
            ans += 1
        for j in range(1, 10**6+10):
            if a[i]*j > 10**6:
                break
            dp[a[i]*j] = False
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())

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

ans = 0
d = {}

for i in range(len(a)):
    if a[i] in d.keys():
        d[a[i]] += 1
    else:
        d[a[i]] = 1
# print(d)

for i in range(len(a)):
    flag = False


    if d[a[i]] > 1:
        continue

    if a[i] != 1 and 1 in d.keys():
        continue
    # print("a: ", a[i])
    j = 2
    while j <= math.sqrt(a[i]):
        if a[i] % j == 0:
            # print(j)
            if a[i] / j == j:
                if j in d.keys():
                    flag = True
                    break
            else:
                if j in d.keys() or (a[i]/j) in d.keys():
                    flag = True
                    break
    
        j += 1
    
    if flag == False:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

if N == 1:
  print(1)
  exit(0)
#
A.sort()
A.append(0) 

b = []
ans = 0
i = 0
while i < N:
  c = A[i]
  for j in b:
    if c % j == 0:
      break
  else:
    b.append(c)
    if c != A[i+1]:
      ans += 1
  while c == A[i+1]:
    i += 1
  i += 1
#          
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = []
for l in sys.stdin:
  input.append(l)

total = input.pop(0)

lst = list(map(int, input[0].split(' ')))
arr = np.asarray(lst, dtype = np.int32)
arr = np.sort(arr)[::-1]

cnt = 0
for i1, v1 in np.ndenumerate(arr):
  found = False
  for i2, v2 in np.ndenumerate(arr):
    if i1 == i2:
      continue
    if v1 % v2 == 0:
      found = True
      break
  if found == False:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

input = []
for l in sys.stdin:
  input.append(l)

total = input.pop(0)

lst = list(map(int, input[0].split(' ')))
arr = np.asarray(lst, dtype = np.int32)
arr.sort()

cnt = 0
for i1, v1 in np.ndenumerate(arr):
  found = False
  for i2, v2 in np.ndenumerate(arr):
    if i1 == i2:
      continue
    if v1 % v2 == 0:
      found = True
      break
  if found == False:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

ans = 0

for i in range(len(a)):
    flag = False
    for j in range(len(a)):
        if i == j:
            continue

        if a[i] % a[j] == 0:
            flag = True
            break
    
    if flag == False:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = []
for l in sys.stdin:
  input.append(l)

total = input.pop(0)

lst = list(map(int, input[0].split(' ')))
lst.sort()

cnt = 0
for i1, v1 in enumerate(lst):
  found = False
  for i2, v2 in enumerate(lst):
    if i1 == i2:
      continue
    if v1 % v2 == 0:
      found = True
      break
  if found == False:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()
 
for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

if 1 in dic.keys():
	if dic[1] == 1:
		print(1)
	else:
		print(0)
else:
	ans = 0
	appeared = set()
	lib = Factorization()
 
	for k, v in sorted(dic.items(),key=lambda x:x[0]):
		is_exist = False
 
		if v == 1:
			divisors = lib.get_divisors(k)
		
			for d in divisors:
				if d in appeared:
					is_exist = True
					break
 
			if is_exist == False:
				ans += 1
 
		if is_exist == False:
			appeared.add(k)
 
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
#以上をまとめると
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
result=[]
#条件を満たすリスト
botsu=[]
#条件を満たさないもののリスト
M=10**6

for i in range(len(A)):
    value=A.pop(0)
    if value in A:
        #取り出した数が複数ある場合
        #valueの倍数もまたresultではなくbotsuにはいる
        #1-Mの範囲でvalueの倍数をbotsuにくわえる
        m=M//value
        for j in range(1,m+1):
            botsu.append(value*j)
        A=[i for i in A if i not in botsu]
        #botsuに入ってないもののみを残す(resultの可能性あるもの)
    else:
        result.append(value)
        for j in range(2,M//value+1):
            botsu.append(value*j)
            #value自体はresultにっ加えているので、botsuには加えない
        A=[i for i in A if i not in botsu]
    if len(A)==0:
        break
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
remain = [0 for i in range(max(a) + 1)]
for ai in a:
    remain[ai] += 1
res = 0
for i in range(1, max(a) + 1):
    if remain[i] == 1:
        res += 1
    if remain[i]:
        for j in range(i * 2, max(a) + 1, i):
            remain[j] = 0
print(res)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
result=[]
#条件を満たすリスト
botsu=[]
#条件を満たさないもののリスト

for i in range(len(A)):
    value=A.pop(0)
    if value in A:
        #取り出した数が複数ある場合
        #valueを結果に加えない
        botsu.append(value)
        #また、valueの倍数もまたresultではなくbotsuにはいるので
        #Aを更新する
        A=[i for i in A if all([i%j !=0 for j in botsu])]
        #リスト内包表記
        #i(格納する変数) for i in l(所属する集合) if 条件式
    else:
        if i==0:
            result.append(value)
        if all([value%j != 0 for j in result]):
            result.append(value)
    if len(A)==0:
        break
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
result=[]

for i in range(len(A)):
    value=A.pop(0)
    #一番はじめの数をpopして取り出す
    if all([value % j !=0 for j in A]):
        #これで自分自身はpopで取り除いているので、他のものにかんしてのみみれる
        result.append(value)
    A.append(value)
    #後ろに加えて元どおりにする
print(len(result))

Submission status: Time Limit Exceeded

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
#for i in range(0,n):
#  lst[i] = int(lst[i])
for i in range(0,n):
  flag=0
  for j in range(0,n):
    if i==j:
      pass
    else:
      if int(lst[i])%int(lst[j])==0:
        flag=1
        j=n
        #break

  if flag==0:
    c = c+1
        
print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [int(x) for x in input().split()]
cnt = [0] * (10**6 + 1)

dic = Counter(a)

for i in set(a):
    if 1 < dic[i]:
        cnt[i] += 1
        
a = list(set(a))

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

ans = 0
for i in range(len(a)):
    if cnt[a[i]] == 1:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

N = int(input())
A = []
for a in map(int,input().split()):
    A.append(a)
A.sort()
c = 0
lenA = len(A)
for i in range(lenA):
    Ai = A[i]
    if i < lenA - 1:
        if Ai == A[i + 1]:
            continue
    Ad = make_divisors(Ai)
    sAd = set(Ad)
    l = A[:i]
    sl = set(l)
    s = sl - sAd
    if len(sl) == len(s):
        c += 1
print(c)

Submission status: Time Limit Exceeded

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

class Factorization:	
	def __init__(self):
		# privateなインスタンス変数を作成
		self.__factors = dict()
		self.__n = 0
	
	
	def get_factors(self, n):
		# [summary] 素因数分解した結果を、辞書([素因数, 指数]...)で返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			# 2より小さい数の場合、素因数分解できない
			return { n:1 }
		else:
			self.__factorization()
			
			return self.__factors
	
	
	def get_divisors(self, n):
		# [summary] 約数をリストに列挙
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return [1]
		else:
			self.__factorization()
			divisors = [1]
			
			for k, v in self.__factors.items():
				import copy
				copy_ = copy.deepcopy(divisors)
								
				for i in range(1, v + 1):
					for c in copy_:
						divisors.append(c * (k ** i))
			
			return divisors

				
	def count_divisors(self, n):
		# [summary] 約数の個数を返す
		self.__factors.clear()
		self.__n = n
		
		if n < 2:
			return 1
		else:
			self.__factorization()
			count = 1
			
			for v in self.__factors.values():
				count *= v + 1
			
			return count
	

	def	__factorization(self):
		# [summary]素因数分解した結果を、インスタンス変数に格納
		
		# 2,3,5で、割れなくなるまで割り続ける
		# (末尾に2,3,5のつく数は素数でないことが明白なので
		# 後続の処理で素数のリストに入れないように、先に処理する)
		self.__divide_with(2)
		self.__divide_with(3)
		self.__divide_with(5)
			
		# 平方根以下の素数で総当たりで試し割りする
		# (実際は、素数らしき数)
		import math
		sqrt_ = math.floor(math.sqrt(self.__n))
			
		primes = [7, 11, 13, 17, 19, 23, 29, 31]
		i = 0
		is_break = False
			
		while self.__n > 1:
			for p in primes:
				if p + i <= sqrt_:
					self.__divide_with(p + i)
				else:
					# 試し割りする数が平方根を超えたら、ループを抜ける
					is_break = True
						
					# 1が素因数に追加されることを防止
					if self.__n > 1:
						self.__factors.setdefault(self.__n, 1)
				
			if is_break:
				break
			else:
				i += 30
	
	
	def __divide_with(self, d):
		count = 0
		
		while self.__n % d == 0:
			self.__n //= d
			count += 1
		
		if count > 0:
			self.__factors.setdefault(d, count)


# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

ans = 0
appeared = set()
lib = Factorization()

for k, v in sorted(dic.items(), key=lambda x:x[0]):
	is_exist = False

	if v == 1:
		divisors = lib.get_divisors(k)
		
		for d in divisors:
			if d in appeared:
				is_exist = True
				break

		if is_exist == False:
			ans += 1

	if is_exist == False:
		appeared.add(k)

print(ans)

Submission status: Time Limit Exceeded

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

lp.sort()

ans = 0
newlist = []
lpmax = max(lp)

while True:
    try:
        left = lp[0]
        nl = lp[1:]
        if not left in nl:
            newlist.append(left)
        if len(nl) < 1:
            break

        lp = [ i for i in nl if i%left != 0 ]
    
    except IndexError:
        break

print(len(newlist))

Submission status: Time Limit Exceeded

Solution code:
def main():
    s = [input() for l in range(2)]
    N, A = int(s[0]), [int(x) for x in s[1].split()]
    results = []

    for i in range(0, (N), 1):
        flag = 0
        for j in range(0, (N), 1):
            if i == j:
                pass
            else:
                if A[i] % A[j] == 0:
                    flag = 1
                    break
                else:
                    pass
        if flag == 1:
            results.append(0)
        else:
            results.append(1)
    cnt = 0
    for x in results:
        if x == 1:
            cnt += 1
    print(cnt)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

if a[0] == a[-1]:
  if n > 1:
    print(0)
  else:
    print(1)
  exit()

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
 
    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def divisors(N):
    pf = primeFactor(N)
    ret = [1]
    for p in pf:
        ret_prev = ret
        ret = []
        for i in range(pf[p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return ret
    
s = set()
ans = 0
for nm,i in enumerate(a):
  c = set(divisors(i))
  if c&s == set() and ((nm < n-1 and a[nm+1] != i) or nm == n-1): 
    ans += 1
  s.add(i)

print(ans)