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:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  tf=[1]*n
  n=n-1
#r=[]
#print(n)
#print(a)
  #notdiv=True
  #firstyn=0
  for i in range(n,-1,-1):
  #print(i)
  #notdiv=True
    if tf[i] ==0:
      continue
    for j in range(i):
    #print(a[j])
      if a[i]%a[j] == 0:
        tf[i]=0
        if a[i]==a[j]:
          tf[j]=0
        break
  print(sum(tf))
main()

Submission status: Time Limit Exceeded

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

    num=[2]
    max = A[N-1]
    for k in range(3,max):
        chk=True
        for k2 in num:
            if k%k2 == 0:chk=False
        if chk==True:num.append(k)

    ans = 0
    temp = 0
    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    for i in range(N):
        if i == 0 and A[i+1] != A[i]:
            ans += 1
            continue

        temp = A[i]
#同じ数があるかどうか
        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue
#もし素数ならループから外す
        if temp in num:
            ans += 1
            continue

        for j in range(N):
            if A[j] <= temp/2 and A[i]%A[j] == 0:
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print(main())

Submission status: Time Limit Exceeded

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

    A.sort()

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

            A[i - 1] = -1
            A[i] = -1
        else:
            prev = A[i]

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

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


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    

    n = int(lines[0])
    a = [int(e) for e in lines[1].split(' ')]

    return (n, a)


def solve(n, a):

    if n == 1:
        return 1
    
    count_dict = dict()
    for i in range(n):
        cnt = count_dict.get(a[i], 0)
        cnt = cnt + 1
        count_dict[a[i]] = cnt
    
    b = list(count_dict.keys())
    b.sort()

    tmp = b.copy()
    result = []
    while len(tmp) > 0:
        h = tmp[0]
        result.append(h)
        tails = tmp[1:]
        tmp2 = [t for t in tails if t % h != 0]
        tmp = tmp2

    result_2 = []    
    removed = set([k for k, v in count_dict.items() if v > 1])
    for r in result:
        if r in removed:
            pass
        else:
            result_2.append(r)
    
    len_result = len(result_2)

    return len_result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':
  
    main()

Submission status: Time Limit Exceeded

Solution code:
def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

import bisect

N=one_int()

As = many_int()

def naive(As, N):
    l = len(As)
    As = sorted(As)
    count=0
    for i in range(l):
        flg = True
        for j in range(min(i+2,l)):
            if i==j:
                continue
            if As[i]%As[j]==0:
                flg=False
                break
        if flg:
            count+=1
    return count
  
print(naive(As,N))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    n= int(input())
    inlis = list(map(int, input().split()))
    inlis.sort()
    for i in range(len(inlis)):
        #print(num, inlis)
        
        new = [e for e in inlis[i:] if e % inlis[i] == 0]
        new.sort()
        #print(new)
        if len(new) > 1:
            if new[0] != new[1]:
                for i in range(1, len(new)):
                    inlis.remove(new[i])
            else:
                for i in range(0, len(new)):
                    inlis.remove(new[i])
        

    print(len(inlis))

    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def divisors(n):
    lst = []; i = 1
    while i ** 2 <= n:
        q, r = divmod(n, i)
        if r == 0:
            lst.append(i)
            if i != q: lst.append(q)
        i += 1
    return lst

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
cnt = [0] * (10**6 + 1)
for a in A: cnt[a] += 1
ans = 0
for a in A:
    if cnt[a] > 1: continue
    for i in divisors(a):
        if i == a: continue
        if cnt[i] >= 1: break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
if(len(a) == 1):
    print(1)
else:
    a.sort()
    flug = 1
    for j in range(n):
        numl = []
        if(j >= len(a)):
            break
        else:
            flug = 1
            for i in range(j+1, len(a)):
                if(a[i] == a[j] and flug == 1):
                    numl.append(j)
                    flug = 0
                    numl.append(i)
                elif(a[i] % a[j]==0):
                    numl.append(i)
            for i in range(len(numl)):
                a.pop(numl[-(i+1)])
    print(len(a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
cnt = 0
bad = 0

def check(i, index):
    for j in range(n):
        if index == j:
            continue
        if a[index] % a[j] == 0:
            return False
    return True

for i in range(n):
    if check(a[i], i):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()
time = 0
for i in range(N):
    list = []
    for z in range(N):
        list.append(z )
    list.remove(i )
    point = 0
    for y in range(len(list)):
        x = int(A[i]) % int(A[list[y]])
        if x == 0:
            point += 1
    if point == 0:
        time += 1
print(time)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)
    A = [next(it) for i in range(N)]
    A.sort()
    AX2 = A[-1] // 2

    if N == 1:
        print(1)
        return
    if A[0] == 1:
        print(0 if A[1] == 1 else 1)
        return

    ax = []
    ans = j = 0

    i = 1
    while i < N:
        a0 = A[i-1]
        for x in ax:
            if a0 % x == 0:
                i += 1
                break
        else:
            if a0 <= AX2:
                ax.append(a0)
            if a0 == A[i]:
                for i in range(i+1, N):
                    if a0 != A[i]:
                        i += 1
                        break
                else:
                    break
                continue
            ans += 1
            i += 1

    if A[-2] != A[-1]:
        a0 = A[-1]
        for x in ax:
            if a0 % x == 0:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
chols={}
ansls={}
ans=0
for i in range(n):
  s=l[i]
  st=s//2
  flag=True
  for j in range(ans):
    if s%ansls[j]==0:
      if s==ansls[j]:
        chols[s]=1
      flag=False
      break
    if ansls[j]>st:
      if ansls[ans-1]==s:
        flag=False
        chols[s]=1
      break
  if flag:
    ansls[ans]=s
    ans+=1
de=chols.keys()

print(ans-len(de))

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
li = list(map(int,input().split()))
set1 = set()
ban = set()
for i in li:
    if i not in set1:
        if len(set1):
            flg2 = True
            for j in set1:
                if i % j == 0:
                    flg2 = False
                    break
            if flg2:
                set1.add(i)
        else:
            set1.add(i)
    else:
        ban.add(i)
set2 = copy.copy(set1)
cnt = 0
for i in set1:
    set2.remove(i)
    flg = False
    if i in ban:
        flg = True
    else:
        for j in set2:
            if flg:
                break
            if i != j:
                if i % j == 0:
                    flg = True
    if not flg:
        cnt += 1
        set2.add(i)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    yn = [0]*(10**6+1)
    for i in a:
        yn[i] += 1

    a1 = a.count(1)
    if a1 == 1:
        print(1)
        exit()
    elif a1 > 1:
        print(0)
        exit()

    ans = 0
    for i in a:
        f = True
        if yn[i] != 1:
            continue
        ni = 2
        while ni**2 <= i:
            if i%ni == 0:
                if yn[ni]:
                    f = False
                    break
                if yn[i//ni]:
                    f = False
                    break
            ni += 1
        if f:
            ans += 1

    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from numba import njit


@njit
def divisors(n):
    res = set()
    for i in range(1, n + 1):
        if i * i > n:
            return res
        d, m = divmod(n, i)
        if m == 0:
            res.add(i)
            res.add(d)
    return res


def count_nondivisors(n, bs):
    ctr = {b: 0 for b in bs}
    for b in bs:
        ctr[b] += 1
    ds = {k: sum(ctr.get(k, 0) for k in divisors(k)) for k in ctr.keys()}
    num_div_elems_table = [ds[bs[i]] for i in range(n)]
    res = sum(num_div_elems_table[i] == 1 for i in range(n))
    return res


def main():
    n = int(input())
    bs = [int(b) for b in input().split()]
    res = count_nondivisors(n, bs)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

cand = set(a)

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

dame_set = set()

a.sort()
ret = 0

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

print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_str = []
a_str = input().split()#pはlist
list = []

for i in a_str :
    a = int(i)
    list.append(a)

num = 0

for i in range(n):
    check = []
    for j in range(n):
        if i == j :
            continue
        b = list[i] % list[j]
        check.append(b)
    if not 0 in check :
        num += 1

print(num)

Submission status: Time Limit Exceeded

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

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

d = [0 for i in range(max(a)+1)]
for i in range(N):
    d[a[i]] += 1
ans = 0

for i in range(N):
    divisors = make_divisors(a[i])
    flag = 1
    d[a[i]] -= 1
    for d_temp in divisors:
        if d[d_temp] > 0:
            flag = 0
    if flag == 1:
        ans += 1
    d[a[i]] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# import numpy as np
n = int(input())
# As = np.array([int(i) for i in input().split()])
As = [int(i) for i in input().split()]
As.sort()
# print(As)

# As に1があったら、1だけ
# if As[0] == 1:
#     if 1 in As[1:]
#     print(1)
#     sys.exit()

index = -1
while index + 1 < len(As): #リストの最後までループ
    index += 1# As[index] が割り切れなかったやつ
    As_index = As[index]
    # print(As_index)
    # delete_list = []

    #自分自身があれば、削除
    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:
            # delete_list.append(i)
            As.pop(i)
    # print(As)
    # As = np.delete(As, delete_list)

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

# print(As)
print(len(As))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    nums = []

    A.sort()

    while A:
        if len(A) >=2 and A[0] == A[1]:
            head = A[0]
            while head in A: A.remove(head)
            continue

        flag = True

        for num in nums:
            if A[0] % num == 0:
                flag = False
                break

        if flag == True:
            nums.append(A[0])

        A.pop(0)

    print(len(nums))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect

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

A.sort()
s = set()
sx = set()

for a in A:
    if a not in s:
        s.add(a)
    else:
        sx.add(a)


cnt = 0
for i in range(N):
    result = False
    a = A[i]

    if a in sx:
        result = True

    # limit = math.floor(a ** (1/2))
    # limit_index = bisect.bisect_left(A, limit)
    limit_index = bisect.bisect_left(A, a)

    for j in range(0, limit_index):
        can_devided = a % A[j] == 0
        if can_devided:
            result = True
            break

    if not result:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
iter = 0
"""
for i in a:
  lst = [i%j for j in a]
  if lst.count(0) == 1:
    iter = iter + 1
"""

a.sort()
for i in a:
  lst = list(filter(lambda x: x<=i, a))
  lst = [i%j for j in lst]
  if lst.count(0) == 1:
    iter = iter + 1
print(iter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
# A = np.array(A)
# def div(n):
#     lower_divisors , upper_divisors = [], []
#     i = 1
#     while i*i <= n:
#         if n % i == 0:
#             lower_divisors.append(i)
#             if i != n // i:
#                 upper_divisors.append(n//i)
#         i += 1
#     return lower_divisors + upper_divisors[::-1]

ans = 0

for i in range(N):
    Ao = np.array(A[:i]+A[i+1:])
    Ao = Ao[Ao<=A[i]]
    # mod = set(A) & set(div(A[i]))
    # print(div(a))

    if all([A[i]%a!=0 for a in Ao]):
    # if len(mod)==1:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
double = set(a)
for i in double:
    if not a.count(i) == 1:
        ans -= a.count(i)
a = sorted(a)
# a.sort()
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()

check = True
loop = list(range(len(a)))
for i in loop:
    for j in range(0, i):
        if not a[j] == 1:
            if a[j]*2 > a[i]:
                break
        if i == j:
            continue
        if a[i]%a[j] == 0:
            check = False
            break

    if check:
        ans += 1
        # print(i)
    check = True
# print(a)
# print(ans)
# print(double)

# ans -= len(set(double))
# ans -= len(double)
print(ans)

Submission status: Time Limit Exceeded

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

def henkan(LIST):
    ANS=[LIST[i] for i in range(len(LIST)) if not LIST[i] % min(LIST) == 0]
    return ANS
cnt=0
check=1
for i in range(10**9):
    cnt+=1
    l=len(A)
    if l>=1:
        if A.count(min(A))>=2:
            check+=1
        A=henkan(A)
    elif l==0:
        print(cnt-check)
        exit()

Submission status: Time Limit Exceeded

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


for i in range(N):
  for j in range(N):
    if i != j:
      if num_list[i] % num_list[j]==0:
        count = count + 1
        break
        
print(N-count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
cnt = 0
for i in range(N):
    for j in range(N):
        if i != j:
            if A[i] < A[j]:
                break
            elif A[i] % A[j] == 0:
                cnt += 1
                break
            else:
                pass     
print(N-cnt)

Submission status: Time Limit Exceeded

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


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

counter = 0
for a in A:
    if A.count(a)>= 2:
        counter +=1
        continue
    li = make_divisors(a)
    for i in li:
        
        if not i == a and i in set(A):
            counter += 1
        
            break
print(N-counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split(' ')))
 
not_divisible = 0
for num_i, Ai in enumerate(As):
    for num_j, Aj in enumerate(As):
        if num_i==num_j:
            continue
        if Ai%Aj==0:
            break
    else:
        not_divisible += 1
print(not_divisible)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    black_list = set()
    ans = 0
    for a in sorted(A_dict.keys()):
        for b in black_list:
            if a % b == 0:
                break
        else:
            if A_dict[a] == 1:
                ans += 1
            black_list.add(a)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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

cnt = 0
while a:
    min_val = min(a)
    a.remove(min_val)

    if c[min_val] == 1:
        cnt += 1

    if not a:
        break

    max_val = max(a)

    del_a = set()
    mul = 2
    while True:
        mul_val = min_val * mul

        if mul_val > max_val:
            break

        if mul_val in a:
            del_a.add(min_val * mul)

        mul += 1

    a -= del_a

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math as mt
input=sys.stdin.buffer.readline  
#t=int(input())
def printDivisors(n) : 
      
    # Note that this loop runs till square root 
    i = 1
    l3=[]
    while i <= mt.sqrt(n): 
          
        if (n % i == 0) : 
              
            # If divisors are equal, print only one 
            if (n / i == i) : 
                l3.append(i) 
            else : 
                # Otherwise print both 
                l3.append(i)
                l3.append(n//i)
        i = i + 1
        
    return l3    
t=1
for __ in range(t):
    
    #x,n=map(int,input().split())
    l=[0]*(10**6+1)
    n=int(input())
    #a=[[0 for j in range(m)] for i in range(n)]
    a=list(map(int,input().split()))
    l1=[]
    ans=0
    d={}
    for i in a:
        d[i]=d.get(i,0)+1
    a=list(set(a))
    for i in a:
        fact=printDivisors(i)
        ch=0
        #print(i,fact)
        for j in fact:
            
            if d.get(j,-1)!=-1 and j!=i:
                ch=1
        if ch==0 and d[i]==1:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 約数
N = ir()
A = lr()
A.sort()
answer = 0
bl = [0] * (10**6+1)

def make_divisors(n):  # 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

for i, a in enumerate(A):
    if i < N-1 and a == A[i+1]:
        bl[a] = 1
        continue
    divs = make_divisors(a)
    flag = True
    for x in divs:
        if bl[x] == 1:
            flag = False
            break
    bl[a] = 1
    if flag:
        answer += 1

print(answer)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    '''
    code here
    '''
    import math
    import collections
    N = int(input())

    A_list = [int(item) for item in input().split()]    
    A_list.sort()

    cnt = 0

    while len(A_list) > 0:
        # print(A_list)
        cnt += 1
        temp = A_list[0]
        del A_list[0]

        is_same = False
        for item in A_list[:]:
            if item == temp:
                is_same = True
            if item % temp == 0:
                A_list.remove(item)
        
        if is_same:
            cnt -= 1

    print(cnt)





if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

@njit
def main(N, a):
    a.sort()
    if a[0] == 1:
        if a[1] == 1:
            return 0
        return 1
    i = 0
    while True:
        num = a[0]
        if 2 > len(a):
            return len(a)+i
        while True:
            if num == a[1]:
                a = [i for i in a if i != num]
                if 2 > len(a):
                    return len(a)+i
                num = a[0]
            else:
                break
        if num*2 > a[len(a)-1]:
            a = [i for i in a if i % num != 0]
            return len(a)+i+1
        a = [i for i in a if i % num != 0]
        i = i+1


N = int(input())
a = list(map(int, input().split()))
print(main(N, a))

Submission status: Time Limit Exceeded

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

A.sort()
checked = []
ans = 0
before = 0
first = True
for i in A:
    if before == i and first:
        if flag:
            ans -= 1
        first = False
        continue
    elif before != i:
        first = True
    elif not first:
        continue
    flag = True
    for l in checked:
        if l > i // 2:
            break
        if i % l == 0:
            flag = False
            break
    if flag:
        checked.append(i)
        ans += 1
    before = i

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for Ai in A:
  flag = 0
  double = 0
  for Aj in sortedA:
    if Ai == Aj:
      double += 1
      continue
    if (Ai % Aj) == 0:
      flag = 1
      break
  if flag == 0 and double < 2:
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = sorted(list(map(int, input().split())))
answer = 0
b = deque(a)

d = -1

for x in range(n):
    c = b.pop()
    if c == d:
        continue
    else:
        temp = 1
        for y in b:
            if c % y == 0:
                temp = 0
                break
        answer += temp
        d = c

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

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

            
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
n = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in a:
  l = list(map(lambda x: i % x, a))
  # print(l)
  if l.count(0) == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
yaku = [[] for _ in range(N)]
d = defaultdict(int)
for i in a:
    d[i] += 1
for i in range(N):
    if d[a[i]] != 1:
        continue
    for j in range(1, int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            yaku[i].append(j)
            if j != a[i] // j:
                yaku[i].append(a[i]//j)
asort = sorted(a)
cnt = 0

for i in range(N):
    if yaku[i] == []:
        continue
    cntF = True
    for j in yaku[i]:
        tmp = bisect.bisect_left(asort, j)
        if a[i] % asort[tmp] == 0:
            if tmp == len(yaku) - 1:
                continue
            if a[i] == asort[tmp]:
                if asort[tmp] != asort[tmp + 1]:
                    continue
            cntF = False
            break
    if cntF:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

A = int(stdin.readline())
B = list(map(int,stdin.readline().split()))
B.sort()
count=0
T=0
Q=0

if B.count(1)>0:
    if B.count(1)>1:
        print(0)
    elif B.count(1)==1:
        print(1)
    B=[]
    T=1

while len(B)>0:
    if len(B)==1:
        if Q==0:
           count+=1
        break
    K=B[0]

    B.remove(B[0])

    Q=0
    D=B.copy()
    for t in D:

        if t==K:
            Q=1
        if t%K==0:
            B.remove(t)

    if Q==0:
       count+=1

if T==0:
   print(count)

Submission status: Time Limit Exceeded

Solution code:
# 出現した数のフラグを立てればよいだけでは
import sys
from collections import Counter

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
# A = list(map(int, read().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0
for i in range(N):
    if count[A[i]] >= 2:
        ans += 1
        happend.add(A[i])
        continue
    for j in range(1, int(A[i]**(1/2))+2):
        if A[i] % j == 0:
            if j in happend or A[i]//j in happend:
                ans += 1
                break
    happend.add(A[i])
print(N-ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

    for i in range(lenb):
        if Boo[i] and B[i]<500004:
            temp = Boo[i]*2 -1
            for j in range(i+1,lenb):
                if Boo[j] and s[B[j]-1]==False and B[j]>temp and B[j] % B[i] == 0:
                    Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and C[B[i]]==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A.sort()
L = []
pre_val = A[0]
count = 0
for a in A:
    if pre_val == a:
        count += 1
    else:
        temp = [pre_val, count]
        L.append(temp)
        count = 1
        pre_val = a
L.append([pre_val, count])

res = 0
for i in range(len(L)):
    flag = False
    if L[i][1] != 1:
        continue
    Ai = L[i][0]
    for j in range(i):
        Aj = L[j][0]
        if Ai % Aj == 0:
            flag = True
            break
    if flag is False:
        res += 1
print(res)