Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
mis=0
for i in range(len(a)):
  # if a[i]==a[i-1]:
  #   continue
  for j in range(min(len(a),i+2)):
    if a[i]%a[j]==0:
      if i!=j:
        mis=1
        break
  if mis==0:
    ans+=1
  mis=0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a_origin = sorted(inpl())
ans = 0
count = collections.defaultdict(int)
a = []
for i in range(n):
    count[a_origin[i]] += 1
    if count[a_origin[i]] < 3:
        a.append(a_origin[i])
n = len(a)


class Cell:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


prev = Cell(a[0])
now = prev
for i in range(1, n):
    new = Cell(a[i])
    prev.next = new
    new.prev = prev
    prev = prev.next
while now:
    if not now.next:
        ans += 1
        break
    target = now.next
    while target:
        if target.value == now.value:
            ans -= 1
        if target.value % now.value == 0:
            if target.next:
                target.next.prev = target.prev
                target.prev.next = target.next
            else:
                target.prev.next = None
        target = target.next
    ans += 1
    now = now.next
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import defaultdict
    N = int(input())
    A = []
    C = defaultdict(int)
    for i in map(int, input().split()):
        if C[i] == 0:
            A.append(i)
        C[i] += 1
    A.sort()
    X = []
    ans = 0
    if C[1] > 1:
        print(0)
        sys.exit()
    elif C[1] == 1:
        print(1)
        sys.exit()
    for a in A:
        for x in X:
            if a % x == 0:
                break
            if 2 * x > a:
                if C[a] == 1:
                    ans += 1
                X.append(a)
                break
        else:
            if C[a] == 1:
                ans += 1
            X.append(a)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

s = set()
for a in A:
  dv = divisors(a)
  for d in dv:
    if d in s:  
      break
  else:
    s.add(a)
      
ans = 0
C = Counter(A)
for si in s:
  if C[si]==1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
    count = 0 # 割り切れた回数
    flag = True # 割り切れなかったか確認
    for j in range(N):
        if A[i]%A[j] == 0:
            count += 1
        if count == 2:
            flag = False
            break
            
    if flag == True :
        ans += 1
print(ans)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

(n) = map(int, sys.stdin.readline().strip().split())
list_input = list(map(int, input().split()))

# 1の数をカウント
counts_one = list_input.count(1)
if counts_one == 1:
    print(counts_one)
    sys.exit()
elif counts_one > 1:
    print(0)
    sys.exit()

# 全て同じ数字かチェック
counts_same = list_input.count(list_input[0])
if counts_same == n:
    print(0)
    sys.exit()

counts_two = list_input.count(2)

anti_ans = 0
list_a = list_input.copy()
for i in list_input:
    for iloop in range(len(list_a)-1):
        if i == 2 and counts_two == 1:
            break
        if i == 2 and counts_two >= 2:
            anti_ans += 1
            break
        if i != 2 and counts_two >= 2 and i % 2 == 0:
            anti_ans += 1
            break
        if i % list_a[iloop+1] == 0:
            anti_ans += 1
            break
    # a = list_a.pop(0)
    # list_a.append(a)
    list_a.append(list_a.pop(0))
print(len(list_input) - anti_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**5)

N = int(input())
A = deque(sorted(list(map(int, input().split()))))
 
ans = 0
def func(c, q):
    global ans
    if c == 0:
        return 
    if c == 1:
        ans += 1
        return
    new_c = 0
    new_q = deque()
    if q[0] != q[1]:
        ans += 1
    a_i = q[0]
    for a_j in q:
        if a_j % a_i != 0:
            new_q.append(a_j)
            new_c += 1
    func(new_c, new_q)

func(N, A)
print(ans)

Submission status: Time Limit Exceeded

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

num = 0
t_2 = False
t_3 = False
t_5 = False
t_7 = False
A = sorted(A)

for i in range(N):
    flag = True

    if t_2 == True:
        if A[i] % 2 == 0:
            flag = False
    if t_3 == True:
        if A[i] % 3 == 0:
            flag = False
    if t_5 == True:
        if A[i] % 5 == 0:
            flag = False
    if t_7 == True:
        if A[i] % 7 == 0:
            flag = False

    if flag == True:
        for j in range(N):
            if A[i] % A[j] == 0 and i != j:
                flag = False
                break

    if i < 20:
        if A[i] == 2:
            t_2 = True
        elif A[i] == 3:
            t_3 = True
        elif A[i] == 5:
            t_5 = True
        elif A[i] == 7:
            t_7 == True


    if flag == True:
        num += 1

print(num)

Submission status: Time Limit Exceeded

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

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

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

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

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

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

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 = sorted(list(map(int, input().split())))
cnt = 0
cnt1 = 0
for i in a:
    if i == 1:
        cnt1 += 1
        if cnt1 == 2:
            print(0)
            sys.exit()
# if cnt1 > 1:
    # print(0)
    # sys.exit()
if cnt1 == 1:
    print(1)
    sys.exit()
if n == 1:
    print(1)
    sys.exit()
for i in range(n):
    d = make_divisors(a[i])
    # print(d)
    if i == 0 and a[i] == a[i + 1]:
        continue
    if i == n - 1 and a[i - 1] == a[i]:
        continue
    if i not in [0, n - 1] and (a[i - 1] == a[i] or a[i] == a[i + 1]):
        continue
    if len(d) == 2:
        cnt += 1
        continue
    d = d[:-1]
    for j in d:
        if a[bisect_left(a, j)] == j:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

X = 1
ans = 0
for i in range(N):
    for j in range(1,N):
        if A[0] % A[j] == 0:
            X = 0
    ans += X
    A.append(A[0])
    del A[0]
    X = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# import sympy
from collections import defaultdict, Counter
# def factors(N): #約数を全て求める。ただし、順不同
#     from collections import deque
#     ret = deque()
#     middle = int( N**(1/2))
#     for i in range(1, middle):
#         if N%i == 0:
#             ret.append(i)
#             ret.append(N//i)
            
#     if N%middle == 0:
#         ret.append(middle)
#         if middle != N//middle:
#             ret.append(N//middle)
#     return ret

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)

    divisors.sort()
    return divisors


def main():
    N = int( input())
    A = list( map( int, input().split()))
    CA = Counter(A)
    d = defaultdict( lambda : False)
    for a in A:
        d[a] = True
    ans = 0
    for a in A:
        if CA[a] > 1:
            continue
        for p in make_divisors(a):
            if p == a:
                continue
            if d[p]:
                break
        else:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

if n==1:
    print(1)
    sys.exit()
"""
def fsort(a,max):
    n=len(a)
    f=[0]*(max+1)
    b=[0]*n

    for i in range(n):
        f[a[i]]+=1
    for i in range(1, max+1):
        f[i]+=f[i-1]
    for i in range(n-1,-1,-1):
        f[a[i]]-=1; b[f[a[i]]]=a[i]
    for i in range(n):
        a[i]=b[i]

fsort(a, 10**6)
"""
def quicksort(a, left: int, right: int):
    #a[left]〜a[right]をクイックソート
    pl=left
    pr=right
    pivot= a[(left +right)//2]

    #print(f'a[{left}]~a[{right}] : ', *a[left : right +1])

    while pl<=pr:
        while a[pl] <pivot: pl+=1
        while a[pr] >pivot: pr-=1
        if pl <= pr:
            a[pl], a[pr]= a[pr], a[pl]
            pl+=1
            pr-=1

    if left < pr: quicksort(a, left, pr)
    if pl < right: quicksort(a, pl, right)

def quick_sort(a):
    quicksort(a, 0, len(a)-1)

quick_sort(a)
if a[0]==1:
    if a[1]==1:
        print(0)
        sys.exit()
    else:
        print(1)
        sys.exit()

if a[0]==a[1]:
    count=0
else:
    count=1

for i in range(n-2):
    if a[i+2]==a[i+1]:
        continue
    if a[i+1]==a[i]:
        continue
    for l in range(i+1):
        if a[i+1]%a[l]==0:
            break
        if i==l:
            count+=1

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
As = [int(i) for i in input().split()]
As.sort()
index = -1
max_value = As[-1]
while index + 1 < len(As): #リストの最後までループ
    index += 1# As[index] が割り切れなかったやつ
    As_index = As[index]
    if As_index > max_value:
        break

    #自分自身があれば、削除
    self_deleted = False
    if index + 1 <  len(As):
        if As_index == As[index + 1]:
            # print(As)
            # delete_list.append(index)
            self_deleted = True
            
    for i in range(len(As)-1, index, -1): # As[index] で割り切れたやつを削除
        if i == index : #　同じならとばす
            continue

        if As[i] % As_index == 0:
            As.pop(i)

    max_value = As[-1]

    if self_deleted:
        As.pop(index)
        index -= 1

print(len(As))

Submission status: Time Limit Exceeded

Solution code:
import sys
a = int(input())
b = list(map(int,input().split()))
count = 0
b = sorted(b)
for i in range(a):
  _count = 0
  _main = b[i]
  if (i+2)<=a:
    if _main==b[i+1]:
      continue
  for j in range(0,i):
    if i==j:
      continue
    if (_main%b[j])==0:
      break
    else:
      _count +=1
  if _count == i:
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

for a in A:
  A = np.delete(A,np.where((A%a==0) & ((A!=a) | (2<=len(np.where(A==a)[0])))))

print(len(A))

Submission status: Time Limit Exceeded

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

sum = 0

if N == 1:
    print(1)

else:
    while True:
        X = A.pop(0) #左端をとる
    
        i = len(A)

        OK = True

        for Y in reversed(A):
            i -= 1

            if Y == X:
                OK = False
                A.pop(i)

            elif Y%X == 0:
                A.pop(i)

        if OK:
            sum += 1

        if len(A) == 0:
            break

    print(sum)

Submission status: Time Limit Exceeded

Solution code:
# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod

    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)

def ncr(n, r,  fact, ifact):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t



def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def check_sorted(a):
    ''' returns True/False '''
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True
def ceil(n, k=1): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []
def write(s): return sys.stdout.write(s)












###################################################################
def main():
    #CODE GOES HERE:
    n=ii()
    a=li()
    a.sort()
    count=0
    oops=a.count(1)
    if oops>0:
        if oops>2:
            print(0)
            return
        else:
            print(1)
            return
    
    for i in range(n):
        check=True
        if(i!=n-1):
            if(a[i]==a[i+1]):
                continue
        for j in range(n):
            if i!=j:
                if a[i]%a[j]==0:
                    check=False
                    break
            if a[j]>a[i]:
                break
        if check:
            count+=1
    print(count)
    
    
































""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

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


class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

""" main function"""

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

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

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

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

    return arr

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    #rootA=math.sqrt(ListA[i])
    MaxVal=ListA[i]/factorization(ListA[i])[0][0]

    # if(ListA[i]%2==0):
    #     Maxval=ListA[i]/2
    # if(ListA[i]%3==0):
    #     Maxval=ListA[i]/3
    # if(ListA[i]%5==0):
    #     Maxval=ListA[i]/5
    # if(ListA[i]%7==0):
    #     Maxval=ListA[i]/7


    for j in range(i):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>MaxVal):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Time Limit Exceeded

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



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0 and cnt[a]==1:
        ans += 1
    for i in range(10**7):
        x = a*i
        if x>10**6:
            break
        P[x] = 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
c=collections.Counter(l)
x=list(set(l))
x.sort()
ans=0
s=set()
if len(x)==0:
  print(0)
else:
  for y in x: 
    if c[y]<2:
      memo=0
      for j in range(1,int(y**0.5)+1):
        if y%j == 0 :
          if y//j in s or j in s:
            memo-=1
      if memo==0:
        ans+=1     
    s.add(y)
  print(ans)

Submission status: Time Limit Exceeded

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

count = 0

oddA = list(filter(lambda x: x % 2 == 1, A))
oddN = len(oddA)
for i in range(oddN):
    if i < oddN - 1:
        if oddA[i] == oddA[i+1]:
            continue
    if i > 0:
        if oddA[i] == oddA[i-1]:
            continue
    div_flag = True
    for j in range(i):
        if oddA[i] % oddA[j] == 0:
            div_flag = False
            break
    if div_flag:
        count += 1

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
count=0
for i in range(n):
	t=l[i]
	c=0
	for j in range(n):
		if t%l[j]!=0:
			c+=1
	if c==len(l)-1:
		count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*n
    a.sort(reverse=True)
    if a.count(1) == 1:
        print(1)
        exit()
    if a.count(1) >= 2:
        print(0)
        exit()
    for i in range(n-1):
        if cnt[i] == 1:
            continue
        for j in range(i+1,n):
            if a[i] == a[j]:
                cnt[i] = 1
                cnt[j] = 1
                break
            if a[i]%a[j] == 0:
                cnt[i] = 1
                break
    print(n - sum(cnt))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if n == 1:
  print(1)
else:
  i = 0
  ans = 0
  for _ in range(n):
    count = 1
    for j in range(i):
      if a_list[i] % a_list[j] == 0:
        if i < n/1000:
          del a_list[i]
          i -= 1
        count = 0
        break
    if count == 1:
      if i == len(a_list)-1:
        ans += 1
      elif a_list[i] != a_list[i+1]:
        ans += 1
    i += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = [int(_) for _ in input().split()]
 
a_list = list(sorted(a_list))

for i in range(0, 100000+1):
    if len(a_list) > i:
        a_list = list(filter(lambda x: x%a_list[i] != 0 or x == a_list[i], a_list))

ans = []
for i, a in enumerate(a_list):
    if i < len(a_list)-1:
        if a == a_list[i+1]:
            continue
    if i == 0:
        ans.append(a)
    else:
        is_ok = True
        for a_j in a_list[0:i]:
            q, mod = divmod(a, a_j)
            if mod == 0:
                is_ok = False
                break
        if is_ok:
            ans.append(a)

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools

def main():
    n = int(input())
    a = list(map(int,input().split()))
    b = set(a)
    ansAry = [0] * 10000000

    num = len(a) - len(b)

    count = 0

    a.sort()

    x =  list(itertools.combinations(a,2))
    # print (x)

    
    for i in range(len(x)):
        if x[i][1] % x[i][0] == 0 and ansAry[x[i][1]] == 0 :
            count += 1
            ansAry[x[i][1]] = 1

    print(n - count - num)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    lower.extend(reversed(upper))
    return lower


def main():
    N, *A = map(int, read().split())
    A.sort()
    C = Counter(A)
    A_set = set(A)

    ans = 0
    for a in A:
        if C[a] != 1:
            continue
        D = divisors(a)
        if all(d not in A_set for d in D[:-1]):
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()