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 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

n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    if k in dic:
        dic[k]=0
        continue
    f=1
    x=make_divisors(k)
    for i in x:
        if i in dic:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

Submission status: Time Limit Exceeded

Solution code:
n, *l = map(int,open(0).read().split())
import itertools
check = [1] * n
for v in itertools.combinations(l,2):
#     print(v)
    if max(abs(v[0]) , abs(v[1]) ) % min(abs(v[0]) ,abs( v[1]) )== 0 :
        if abs(v[0]) > abs(v[1]):
            delete = v[0]
        else:
            delete = v[1]
        index_num = [n for n, e in enumerate(l) if e == delete]
        for e in index_num:
            check[e] = 0
#     print(check)
print(sum(check))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n = int(input())
a_list = np.asarray(list(map(int, input().split())))
flag_list =  np.asarray([1] * n)
for i in range(0, n):
    temp = np.where(a_list % a_list[i], 1, 0)
    temp[i] = 1
    flag_list *= temp
    if np.sum(flag_list) == 0:
        break


print(np.sum(flag_list))

Submission status: Time Limit Exceeded

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

B = [0 for _ in range(n)]
for i in range(n):
  c = 0
  if i < n-1 and A[i] == A[i+1]:
    B[i] = 1
    B[i+1] = 1
  while(A[i]*c <= A[n-1]):
    c += 1
    for j in range(n)[i+1:]:
      if A[i]*c > A[j]:
        continue
      if A[j] == A[i]*c:
        B[j] = 1
print(n-sum(B))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i  in range(len(a)):
    flag = 1
    for j in range(len(a)):
        if i != j and a[i] % a[j] == 0:
            flag = 0
            break

    if flag == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
  if i == 0 and n >= 2 and a[i] == a[i+1]:
    continue
  if i == n-1 and n >= 2 and a[i] == a[i-1]:
    continue
  if i != 0 and i != n-1 and (a[i] == a[i-1] or a[i] == a[i+1]):
    continue
  ok = True
  if a[i] == 1:
    ans += 1
    continue
  for j in range(1, int(a[i]**(1/2))+1):
    if j == 1:
      if j in s:
        ok = False
        break
      else:
        continue
    if a[i] % j == 0:
      rem = a[i] // j
      if j in s or rem in s:
        ok = False
        break
  if ok:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
y = [0 for i in range(max(a) + 1)]
same = [0 for i in range(max(a) + 1)]
for i in a:
    same[i] += 1

# 約数
def divisor(x):
    ret = []
    for i in range(1, int(x ** 0.5) + 1):
        if x % i == 0:
            ret.append(i)
            ret.append(x // i)
    return list(set(ret))


ans = 0
for i in a:
    flag = True
    for j in divisor(i):
        if y[j] == 1:
            flag = False
    y[i] = 1
    if flag and same[i] <= 1:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

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

N=int(input().rstrip('\n'))
As=[int(x) for x in input().rstrip('\n').split()]
As2 = sorted(As)
for i in range(N):
  try:
    now = As2[i]
    As3=[x for x in As2[i+1:] if x%now!=0]
    As2 = As2[:i]+As3
    if As.count(now)==1:
      As2.insert(i,now)
  except:
    break
print(len(As2))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))
ans=N
L=[]
P=[]
A.sort()

for i in range(N):
    flg=True
    for j in range(len(L)):
        if A[i]%L[j]==0:
            if A[i]==L[j]:
                P.append(A[i])
            flg=False
            break
    if flg:
        L.append(A[i])

print(len(L)-len(set(P)))

Submission status: Time Limit Exceeded

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

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

# 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]

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table

ans = 0
for a in A:
    flag = True
    # da = make_divisors(a)
    da = divisor(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(N):
    tmp = len(nA[A[i]%nA == 0]) 
    if(tmp == 1):
        cnt += 1    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().split()]

def func1():
    cnt=0
    a.sort()
    chker={}
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
        else:
            for j2 in chker:
                j=int(j2)
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
        chker[str(i)]=1
    print(cnt)
func1()

Submission status: Time Limit Exceeded

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

res = 0
cnt = [False] * a[-1]
for i in range(n):
    j = 1
    while j * j <= a[i]:
        if a[i] % j == 0 and (cnt[j-1] or cnt[a[i]//j-1]):
            res += 1
            break
        j += 1
    if j * j > a[i] and i + 1 < n and a[i] == a[i+1]:
        res += 1
    cnt[a[i]-1] = True

print(n - res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = set()
d = 0
for i in range(N):
  f = True
  for j in ans:
    if A[i] % j == 0:
      f = False
      break
  if f:
    ans.add(A[i])
    if i < N - 1 and A[i] == A[i+1]:
      d += 1
print(len(ans) - d)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A.sort()
# print(A)

ans = 0
for i in range(N):
    is_ok = True
    for j in range(i+2):
        if i == j:
            continue
        if j == N:
            break
        if A[i] % A[j] == 0:
            # print("break {} {}".format(i, j))
            is_ok = False
            break
    if is_ok:
        # print(A[i])
        ans += 1
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
    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:
n = int(input())
a = list(map(int, input().split()))

a.sort(key=lambda x: -x)
i = 0
p = []
while len(a) != 0:
    i = a.pop()
    if i in a:
        a.remove(i)
        while i in a:
            a.remove(i)
        continue
    p.append(i)
    a2 = []
    for ai in a:
        if ai % i != 0:
            a2.append(ai)
    a = a2

print(len(p))

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

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

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

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

memo = {}
def make_divisors(n):
    if n in memo:
        return memo[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
    
    memo[n] = lower_divisors + upper_divisors[::-1]
    return memo[n]

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

ans = 0

for i,a in enumerate(A):
    div = make_divisors(a)
    ok = True
    for d in div:
        if d == a:
            if C[d] > 1:
                # log(C[d])
                ok = False
                break
        elif d in keys:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

flags = [True] * N

count = 0
for i in range(N):
    if flags[i]:
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                flags[j] = False
            if A[j] == A[i]:
                flags[i] = False
        if flags[i]:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
c = [False]*N
ans = 0
for i in range(N):
    if c[i]:
        continue
    if i == N-1 or A[i] != A[i+1]:
        ans += 1
    if i == N-1:
        break
    for j in range(i+1,N):
        if not c[j] and A[j]%A[i]==0:
            c[j] = True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    if a.count(10 ** 6) == n:
        print(0)
        exit()

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# A_i/A_j False
num = int(input())
A = [int(x) for x in input().split()]
i = 0
result = list()
for l in A:
    devide = 0
    for j in range(num):
        if j == i:
            continue
        else:
            ans = A[i]/A[j]
            # print(ans)
            if (ans.is_integer()):
                devide += 1
                break
    if (devide==0):
        result.append(l)
    i += 1
print(len(result))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    not_divisible = True
    for j in range(i):
        if a_ls[i] % a_ls[j] == 0:
            not_divisible = False
        if a_ls[i]//2 < a_ls[j]:
            break
    if i > 0:
        if a_ls[i-1] == a_ls[i]:
            not_divisible = False
    if i < n-1:
        if a_ls[i+1] == a_ls[i]:
            not_divisible = False
    if not_divisible:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#デフォルト
import itertools
from collections import defaultdict
import collections
import math
import sys
sys.setrecursionlimit(200000)
mod = 1000000007

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

tf = defaultdict(int)
ans = 0
for i in range(n):
    cnt = a[i]
    cc = 1
    while cnt * cc <= max(a):
        tf[cnt * cc] += 1
        cc += 1

for i in range(n):
    if tf[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1

ans = 0
for n, c in a:
    if c == 1:
        r = bisect.bisect_right(b, n//2)
        ok = True
        for i in range(r):
            if n % b[i] == 0:
                ok = False
                break
        if ok:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a = list(map(int,input().split()))
anp = np.array(a)
a_sort_idx = np.argsort(anp)
que = []
flg = []
for i in a_sort_idx:
    if len(que) == 0:
        que.append(a[i])
        flg.append(0)
    else:
        for j in range(len(que)):
            if a[i] == que[j]:
                flg[j] = 1
                break
            if a[i] % que[j] == 0:
                break
        else:
            que.append(a[i])
            flg.append(0)
        
print(len(que)-sum(flg))

Submission status: Time Limit Exceeded

Solution code:
''''atcoder beginner contest-170'''

import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*n
cnt=0
for i in range(n):
    trr=True
    for j in range(n):
        if i!=j and a[i]%a[j]==0:
            trr=False
            break
    if trr==True:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n,*a = map(int,open(0).read().split())
c = Counter(a)
d = sorted(c.keys(),reverse=True)
m = len(d)
ans = 0
for i in range(m):
  if c[d[i]] != 1:
    continue
  for j in range(i+1,m):
    if d[i]%d[j]==0:
      break
  else:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
array = list(map(int, input().strip().split()))
ans = 0
a = [True] * len(array)
for i in range(N):
    for j in range(N):
        if a[i] == False:
            break
        if i != j and (array[i] % array[j] == 0 or array[i] == array[j]) :
            break
        if i != j and (array[j] % array[i] == 0):
            a[j] == False
        if j == N-1:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
B = [0] * (10**6 + 1)
for i in range (N - 1):
    if A[i] == A[i + 1]:
        B[A[i]] = 1
        c = A[i]
        d = A[i]
        while c + d <= 10**6:
            c = c + d
            B[c] = 1
ans = 0
for i in range(N):
    if B[A[i]] == 0:
        ans += 1
        B[A[i]] = 1
        c = A[i]
        d = A[i]
        while c + d <= 10**6:
            c = c + d
            B[c] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as cl

def main() :
    N = int(input())
    A_list = [int(i) for i in input().split()]
    A_list.sort()
    A_counter = cl.Counter(A_list)

    # memo 最小値が2つあるとき

    cnt = 0
    for i in range(N) :
        not_divisible = True
        if (A_counter[A_list[i]] > 1) :
            # 数列内に同じものを含んでいる場合は必ず割り切れるのでパスする
            continue

        for k in range(i) : 
            # print(A_list[i],A_list[k])
            if (A_list[i] % A_list[k] == 0) :
                not_divisible = False
                # print("divisble", A_list[i],A_list[k])
                break
        if (not_divisible) :
            cnt += 1

    print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))
ans = 0

for i in a:
    x = np.ones(n)
    x *= i
    x %= a
    if np.count_nonzero(x==0) == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

    divisors.sort()
    return divisors

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

    a_list=list(map(int,input().split()))
    n_list=[0]*1000000

    for a in a_list:
        n_list[a-1]+=1

    cnt=0

    for a in a_list:
        y_list=make_divisors(a)[:-1]

        flag=True
        for y in y_list:
            if n_list[y-1]>=1:
                flag=False
                continue
            
        if n_list[a-1]>=2:
            flag=False

        if flag:
            cnt+=1

    print(cnt)            

if __name__ =='__main__': 
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

l = {}

for a in A:
    if a in l.keys():
        l[a] += 1
    else:
        l[a] = 1

# 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]

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n % i == 0:
            table.append(i)
            table.append(n // i)
        i += 1
    table = list(set(table))
    return table

ans = 0
for a in A:
    flag = True
    # da = make_divisors(a)
    da = divisor(a)
    for d in da:
        if d != a:
            if d in l.keys():
                flag = False
                break
        elif l[d] >= 2:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


d = {}
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1

ans = 0

for a in A:
    d[a] -= 1

    exist = False 

    for i in range(1, int(-(-a**0.5//1))+1):
        if a%i == 0:
            if i in d and d[i]>0:
                exist = True
                break
            if a//i in d and d[a//i]>0:
                exist = True
                break

    if not exist:
        ans += 1
    d[a]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (acos, asin, atan, ceil, cos, degrees, factorial, gcd, hypot,
                  log2, pi, radians, sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


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


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


n = inp()

a = inlist()
res = 0
for i in range(n):
    f = True
    for j in range(n):
        if i != j:
            if a[i] % a[j] == 0:
                f = False
                break

    if f:
        res += 1
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
    flg = False
    for j in range(n):
        if i==j:
            continue
        if a[i] % a[j] == 0:
            flg=True
    cnt += 0 if flg else 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit
import numpy as  np


@jit(nopython = True)
def not_divisible(n,length,  num_list):
    count = int(0)

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

    return n - count



n = int(input())
n = int(n)

num_list = list(map(int, input().split()))
num_list = np.array(num_list)

length = int(len(num_list))

print(not_divisible(n,length,  num_list))

Submission status: Time Limit Exceeded

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

C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

U = 10 ** 6 + 1
memo = np.zeros(U, dtype=int)
tmp = np.arange(U)
ans = 0

for k in sorted(C.keys()):
    v = C[k]
    if v >= 2:
        ans += v
        if not memo[k]:
            memo[tmp % k == 0] = 1
        continue
    if memo[k]:
        ans += 1
    else:
        memo[tmp % k == 0] = 1

print(N-ans)

Submission status: Time Limit Exceeded

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

arr.sort()

result = np.zeros(n, dtype=np.int32)

for i in range(n):
    if result[i] >= 1:
        continue
    else:
        tmp = np.where(arr % arr[i] == 0)
        result[tmp] += 1
        result[i] -= 1
        if i < n - 1 and arr[i] == arr[i + 1]:
            result[i] += 1

print(np.where(result == 0)[0].shape[0])

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    for i in range(n):
        tmp = a[:i]
        for j in range(1, int(a[i] ** 0.5) + 1):
            if a[i] % j == 0:
                if j in tmp or (a[i] // j) in tmp:
                    break
        else:
            if not (n > 1 and i < n - 1 and a[i] == a[i + 1]):
                ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = sorted(list(map(int,input().split())))
#    C = Counter(A)
    U = [0] * (max(A)+1)
    ans = 0
    for e in A:
        U[e] += 1
    for e in A:
        t = e*2
        while t <= max(A):
            U[t] = 0
            t += e
        if U[e] > 1:
            U[e] = 0
    print(U.count(1))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n = int(input())
a = list(map(int, input().split()))
a.sort()
#print(a)
for i in range(n):
    wa = a[i]
    if a[i] == -1:
        continue
    if a[i] in a[i+1:]:
        a[i] = -1

    for j in range(i+1, n):
        if a[j] == -1: continue
        if a[j] % wa == 0:
            a[j] = -1
ans = len(set(a))
if -1 in a:
    ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    from math import sqrt
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)
    A = set(A)
    if c[1] == 1:
        return print(1)
    elif c[1] > 1:
        return print(0)

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


for i in range(N) :

  flag=True
  for j in range(N) :
    if i!=j :
      if a_list[i]%a_list[j]==0  :
        flag=False
        break
  if flag :
    count+=1

print(count)

Submission status: Time Limit Exceeded

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

result = 0
for i in range(N):
    flag = True
    for j in range(N):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            flag = False
            break
    if flag:
        result += 1

print(result)

Submission status: Time Limit Exceeded

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


j = 0
ans = []
while j <= N - 1:
    stock = []
    for i in range(N):
        # iとjが同じとき
        if (i == j):
            continue

        if (A[j] % A[i] != 0):
            stock.append(A[i])

    if (len(stock) == len(A) - 1):
        ans.append(j)
    j += 1

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
B = sorted([int(a) for a in input().split()])
dup = []
for i in range(N):
    if len(B) <= i:
        break
    j = i+1
    while True:
        if len(B) <= j:
            break
        if B[i] == B[j]:
            dup.append(B[i])
        if B[j] % B[i] == 0:
            del B[j]
        else:
            j += 1
print(len(B) - len(set(dup)))

Submission status: Time Limit Exceeded

Solution code:
# A_i/A_j False
num = int(input())
A = [int(x) for x in input().split()]
i = 0
result = list()
for l in A:
    devide = 0
    for j in range(num):
        if j == i:
            continue
        else:
            ans = A[i]/A[j]
            # print(ans)
            if (ans.is_integer()):
                devide += 1
    if (devide==0):
        result.append(l)
    i += 1
print(len(result))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int, input().split()))
ret = 0

for i in range(N):
  if sum( [1 for j in range(N) if (Alist[i] % Alist[j]) == 0] ) == 1:
    ret += 1

print( ret )

Submission status: Time Limit Exceeded

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
INF = 1000000000000

n = I()
a = LI()

a.sort()
f = [False]*n

if(n > 1):
    for i in range(1,n):
        if(a[i-1] == a[i]):
            f[i-1] = True
        for j in range(0,i):
            if(a[i] % a[j] == 0):
                f[i] = True
                break

count = 0
for i in range(n):
    if(not f[i]):
        count += 1

print(count)

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