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:
#!/usr/bin/env python3

import numpy as np
from collections import Counter

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = int(input())
    A = LII()
    A.sort()
    C = Counter(A)
    ans = 0
    while len(A) != 0:
        a = A[0]
        A = list(filter(lambda x: x % a != 0, A))
        if C[a] == 1:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

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]

def main():
    n = int(input())
    a = list(map(int,input().split()))
    s = set(a)
    cnt = 0
    from collections import Counter
    c = Counter(a)
    for i in range(n):
        if c[a[i]] > 1:
            continue
        tmp = set(make_divisors(a[i]))
        if len(tmp) - len(tmp-s) == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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
ans=0
for i in range(N):
    a=A[i]
    D=make_divisors(a)
    #print(D)
    L=A[:i]+A[i+1:]
    for d in D:
        if d in L:
            ans+=1
            break
print(N-ans)

Submission status: Time Limit Exceeded

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

A.sort()
ans=N
i=0
while i<N:
    if i<N-1 and A[i]==A[i+1]:
        ans-=1
        i+=1
        continue
    for a in A[:i]:
        if A[i]%a==0:
            ans-=1
            break
    i+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
x=[0 for i in range(max(A))]
#print(x)
for i in range(N):
  if(x[A[i]-1]==0):
    if(A.count(A[i])==1):
      ans+=1
    j=1
    while(j*A[i]<=max(A)):
      x[j*A[i]-1]=1
      j+=1
print(ans)
#print(x)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    MAX = 1000001
    N = int(input())
    arr = list(map(int, input().split(" ")))
    arr.sort()
    is_ans = [True]*MAX
    ans = 0

    dup = set()
    for a in arr :
        if a in dup:
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

        dup.add(a)

    for a in arr :
        if is_ans[a]:
            ans += 1
            j = a
            while j < MAX :
                is_ans[j] = False
                j += a

    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
seen = set()
same = set()
ans = 0
for i in a:
    if i in seen:
        same.add(i)
        continue
    for j in seen:
        if i%j==0:
            break
    else:
        ans += 1
        seen.add(i)
print(ans-len(same))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
M=max(A)
def NFactors(n,ifsort=True):
    ret=set()
    for i in range(1,int(-(-n**0.5//1))+1):
        if n%i==0:
            ret.add(i);ret.add(n//i)
    ret=list(ret)
    if ifsort:
        ret.sort()
    return ret


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

ans = 0

for a in A:
    l = NFactors(a, False)
    d[a] -= 1
    for j in l:
        exist = False
        if j in d and d[j]>0:
            exist = True
            break
    if not exist:
        ans += 1
    d[a]+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


#隣接リスト 1-order
def make_adjlist_d(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
        res[edge[1]].append(edge[0])
    return res


def make_adjlist_nond(n, edges):
    res = [[] for _ in range(n + 1)]
    for edge in edges:
        res[edge[0]].append(edge[1])
    return res


#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    N = NI()
    A = NLI()
    A = sorted(A)
    hurui = [1] * len(A)
    prev = 0
    for i, a in enumerate(A):
        if a == prev:
            hurui[i-1] = 0
            hurui[i] = 0
            prev = a
            continue
        if i == len(A)-1:
            prev = a
            continue
        if hurui[i] == 0:
            prev = a
            continue
        for j, b in enumerate(A[i+1:]):
            if hurui[i+1+j]==0:
                prev = a
                continue
            if b % a == 0:
                hurui[i+1+j] = 0
            prev = a
    print(sum(hurui))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse = True)
ans = 0
while A:
    a = A.pop(-1)
    if not A or a != A[-1]:
        ans += 1
    A = [i for i in A if i%a != 0]
print(ans)

Submission status: Time Limit Exceeded

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

ok = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if AS[i] % AS[j] == 0:
            break
    else:
        ok.append(i)

print(len(ok))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [int(x) for x in input().split()]
A.sort()
ans = 0
for i, a in enumerate(A):
    if i != n - 1 and A[i + 1] == a:
        continue
    do_count = True
    for j in range(i):
        b = A[j]
        if a % b == 0:
            do_count = False
            break
    if do_count:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

l.sort()

def isAns(a, ans):
    for num in ans:
        if a % num == 0:
            return False
    return True

duplicated_number = set()
ans = []
for a in l:
    if ans:
        if a == ans[-1]:
            duplicated_number.add(a)
            continue
    if isAns(a, ans):
        ans.append(a)

print(len(ans) - len(duplicated_number))

Submission status: Time Limit Exceeded

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

A.sort()
res = N
for i in range(N):
    if i != N-1:
        if A[i] == A[i+1]:
            res -= 1
            continue
    if i != 0:
        if A[i] == A[i-1]:
            res -= 1
            continue

    for j in range(0, i):
        if A[i]%A[j]==0:
            res -= 1
            break
print(res)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i]%a[j] == 0:
            ans[i] = 1
            break

print(ans.count(0))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

c = collections.Counter(a)

a.sort()

answer = 0

for i in range(len(a)):
    if c[a[i]] > 1:
        pass
    else:
        if i == 0:
            answer += 1
        else:
            p = True
            for j in range(i):
                if a[i] % a[j] == 0:
                    p = False
            if p:
                answer += 1
print(answer)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            ans -= 1
            break

print(ans)

Submission status: Time Limit Exceeded

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

N,*A = map(int, sys.stdin.buffer.read().split())

A = sorted(A)
setA = set(A)

def yakusu(x):
  if x==1:
    return []
  result = [1]
  y = 2
  while y**2<=x:
    if x%y==0:
      result.append(y)
      result.append(x//y)
    y += 1
  return result

count = N
for i in range(N):
  a = A[i]
  if i>0 and a==A[i-1]:
    count -= 1
    continue
  if i<N-1 and a==A[i+1]:
    count -= 1
    continue
  for y in yakusu(a):
    if y in setA:
      count -= 1
      break

print(count)

Submission status: Time Limit Exceeded

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

    ok = [1] * N

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

    for i in range(N):
        if ok[i]==1: ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
an=list(map(int,input().split()))
c=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if an[i]%an[j]==0:
            j=-1
            break
    if j==n-1:
        c+=1
print(c)

Submission status: Time Limit Exceeded

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

a.sort()
count = 0

for i in range(n):
    if all(a[i] % a[j] != 0 for j in range(i)) and a[i] not in (a[:i] + a[i+1:]):
        count += 1

print(count)

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()
ans = 0

for i in range(n):
    for j in range(n):
        if (i == j): continue
        if a[i] % a[j] == 0: break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
div = set()
dict_a = collections.Counter(a)
for i in range(n):
    flag = True
    for j in range(1,int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            if j in div or a[i] // j in div:
                flag = False
                break
    div.add(a[i])
    if flag and dict_a[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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 = list(map(int, input().split()))

c = Counter(A)
ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 約数を取得
    divi = make_divisors(a)
    for d in divi:
        # チェック中と同じ値は無視
        if d == a:
            continue
        # 約数がハッシュにあるなら割り切れる数が1個はあるので性質を満たさない
        if d in c:
            break
    # 約数が1個もハッシュにない＝割り切れる数がないので性質を満たす
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

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(reverse=True)
    return divisors

def main():
    D = {}
    for i in range(n):
        if A[i] not in D:
            D[A[i]] = 1
        else:
            D[A[i]] += 1
    ans = 0
    for i in range(n):
        d = make_divisors(A[i])
        for x in d:
            if x != A[i]:
                if x in D:
                    break
            else:
                if D[x] >= 2:
                    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()))

cnt=0

for i in range(n):
  for j in range(n):
    if i==j:
      continue
    elif a[i]%a[j]==0:
      break
  else:
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
  # print(lis)
num = [0 for i in range(10 ** 6+5)]
ans = 0
for i in range(n):
    key = 1
    number = lis[i]
    if i > 0:
        if lis[i] == lis[i-1]:
            key = 0
    if i < n-1:
        if lis[i] == lis[i+1]:
            key = 0
    for i in range(1,math.ceil(math.sqrt(number))+1):
        if number % i == 0:
            a = number//i
            b = i
            if num[a] != 0 or num[b] != 0:
                key = 0
    if key == 1:
        ans += 1
    num[number] = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n,*a=map(int,open(0).read().split())
    a.sort()
    s=set(a)
    import collections
    c=collections.Counter(a)
    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
    ans=0
    for i in a[::-1]:
        if c[i]>1:
            continue
        l=set(make_divisors(i))
        if l&s=={i}:
            ans+=1
        
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def is_ok(k):
    ctr[k] -= 1
    d = 1
    while d*d <= k:
        if k%d==0:
            if ctr[d] > 0:
                ctr[k] += 1
                return False
            if ctr[k//d] > 0:
                ctr[k] += 1
                return False
        d += 1
    ctr[k] += 1
    return True

ans = 0
for k,v in ctr.items():
    if v > 1: continue
    if is_ok(k):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

a.sort()

aa = s(a)

ans = 0

for i in range(len(aa)):
	co = 0
	f = 0
	for j in range(i):
		if aa[i][0] >= aa[j][0] * 2:
			if aa[i][0] // aa[j][0] == aa[i][0] / aa[j][0]:
				f = 1
		else:
			break
	if aa[i][1] != 1:
		f = 1
	if not f:
		ans += 1



print(ans)

Submission status: Time Limit Exceeded

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

is_prime = [True] * (10**6 + 1)
pre_a = 0
for a in A:
    if a == pre_a:
        is_prime[a] = False
    j = 2 * a
    while j <= 10**6:
        is_prime[j] = False
        j += a
    
    pre_a = a

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


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 solve(N: int, A: "List[int]"):
    ans = 0
    c = collections.Counter(A)
    dupes = {k for k, v in c.items() if v > 1}
    aset = set(A)
    for a in A:
        if a in dupes:
            continue
        for v in (set(make_divisors(a)) - {a}):
            if v in aset:
                break
        else:
            ans += 1
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
div = set()
dict_a = collections.Counter(a)
for i in range(n):
    flag = True
    for j in range(1,int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            if j in div or a[i] // j in div:
                flag = False
    div.add(a[i])
    if flag and dict_a[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

def divisor(N):
	divisor_list = []
	n = int((N ** 0.5) // 1)
	for i in range(1, n):
		if N % i == 0:
			divisor_list.append(i)
			divisor_list.append(int(N // i))
	#平方数かどうかで場合分け
	if n ** 2 == N:
		divisor_list.append(n)
	else:
		if N % n == 0:
			divisor_list.append(n)
			divisor_list.append(int(N // n))

	return sorted(divisor_list)

#処理内容
def main():
	N = int(input())
	A = getlist()
	DD = defaultdict(int)
	for i in range(N):
		DD[A[i]] += 1

	ans = N
	for i in range(N):
		DD[A[i]] -= 1
		div = divisor(A[i])
		for j in div:
			if DD[j] >= 1:
				ans -= 1
				break
		DD[A[i]] += 1

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    b = set(A)
    c = {}
    def find(x):
        if x in c:
            return c[x]
        l = make_divisors(x)
        for j in l:
            if j == x:
                if a[j] > 1:
                    c[x] = 0
                    return 0
            else:
                if j in b:
                    c[x] = 0
                    return 0
        c[x] = 1
        return 1
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())

Submission status: Time Limit Exceeded

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

ans = 0
n = int(input())
A = list(map(int,input().split()))
B = [0] * (10**6+3)
for i in range(n):
    B[A[i]] += 1

for i in range(n):
    Y = []
    for j in range(1, int(A[i]**0.5)+1):
        if A[i] % j == 0:
            Y.append(j)
            if j != A[i]//j:
                Y.append(A[i]//j)
    # print(Y)
    ok = 1
    for j in range(len(Y)):
        if (Y[j] == A[i] and B[Y[j]] > 1) or (Y[j] != A[i] and B[Y[j]] > 0):
            ok = 0
            break
    # print(ok)
    ans += ok
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def calc_factors(n):
    factors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            j = n // i
            if j != i: factors.append(j)
            factors.append(i)
    return factors

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

ans = 0
done = set()
for i in range(n):
    num = a[i]
    if i < n-1 and a[i] == a[i+1]:
        done.add(num)
        continue
    factors = calc_factors(num)
    for f in factors:
        if f in done:
            break
    else:
        ans += 1
    done.add(num)
print(ans)

Submission status: Time Limit Exceeded

Solution code:


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

nums = {}
for a in arr:
    if a not in nums:
        nums[a] = 1
    else:
        nums[a] += 1

# def factorize(N):
#     up = int(np.sqrt(N))+2
#     out = {}
#
#     for i in range(2,up):
#         if N%i == 0:
#             temp = N
#             count = 0
#             while(True):
#                 N = N//i
#                 count += 1
#                 if N%i != 0:
#                     break
#             out[i] = count
#         else:
#             continue
#     if N != 1:
#         out[N] = 1
#     return out

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

# print(nums)
ans = 0
for i in range(n):
    f = make_divisors(arr[i])
    # print(f)
    cnt = 0
    for key in f:
        if key == arr[i]:
            if key in nums and nums[key] > 1:
                cnt += 1
        else:
            if key in nums:
                cnt += 1

    if cnt == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
div = set()
dict_a = collections.Counter(a)
for i in range(n):
    flag = True
    for j in range(1,int(a[i] ** 0.5) + 1):
        if a[i] % j == 0:
            if j in div or a[i] // j in div:
                flag = False
    div.add(a[i])
    if flag and dict_a[a[i]] == 1:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N=int(input())
arr = np.array(list(map(int, input().split())))
ans=0

for i in range(N):
    if (not 0 in arr[i] % arr[:i]) and (not 0 in arr[i] % arr[i+1:]):
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

def slove():
    n = int(input())
    A = list(map(int,input().split()))
    ans = [1]*n
    for i in range(n-1):
        for j in range(i+1,n):
            if A[i] % A[j] == 0:
                ans[i] = 0
            if A[j] % A[i] == 0:
                ans[j] = 0
    print(sum(ans))


if __name__ == "__main__":
    slove()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import Counter
def divisors(n, sort=False):
    """
    nの約数をO(√n)で列挙する
    """
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i != n // i:
                d.append(n//i)
    if sort:
        d.sort()
    return d
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

div = set(A)
cnt = Counter(A)
ans = 0
for a in A:
    flg = True
    for d in divisors(a):
        if d == a:
            if cnt[a] >= 2:
                flg = False
                break
        elif d in div:
            flg = False
            break
    if flg:
        ans += 1
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()))

    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:
n=int(input())
a=[int(j)for j in input().split()]
a.sort()
s=set(a)
import collections
c=collections.Counter(a)
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
ans=0
for i in a[::-1]:
    if c[i]>1:
        continue
    l=set(make_divisors(i))
    if l&s=={i}:
        ans+=1
    
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)


def divisors(n):
    m = 1
    divs = []
    while m * m <= n:
        if n % m == 0:
            divs.append(m)
            if n != m * m:
                divs.append(n // m)
        m += 1
    divs.sort()
    return divs


N, *A = map(int, read().split())

cnt = 0

for i, a in enumerate(A):
    divs = divisors(a)
    if len(set(set(divs) & (set(A[:i]) | set(A[i + 1:])))) == 0:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        x = a[i]
        div=[]
        for check in range(1,int(x**0.5)+1):
            if(x%check==0):
                div.append(check)
                div.append(x//check)
        flag = 1
        for e in div:
            if dic[e]:
                flag = 0
                break
        if i < n-1 and a[i] == a[i+1]:
            flag = 0
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def yakusu(x):
    tmp=int(pow(x, 1/2))+1
    out=set()
    for i in range(1, tmp):
        if x%i==0:
            out.add(i)
            out.add(x//i)
    if pow(x, 1/2)%1==0:
        out.add(pow(x, 1/2))
    out=list(out)
    out.sort()
    return out
  
counter=0

B=[0]*(10**6+1)
for a in A:
  B[a]+=1

A=set(A)
for a in A:
  nums=yakusu(a)
  nums=nums[:-1]
  judge=True
  for num in nums:
    if num in A:
      judge=False
      
  if judge==True and B[a]==1:
    counter+=1

print(counter)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
alist = sorted([int(v) for v in input().split()], reverse=True)

last = 0
count = 0
for i, a in enumerate(alist):
    if a == last:
        continue
    last = a
    res = True
    for b in alist[i + 1:]:
        if a % b == 0:
            res = False
            break
    if res:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
div=defaultdict(list)
p=10**6+2 
for i in range(1,p):
    for j in range(i,p+1,i):
        div[j].append(i)

n=int(input())
cnt=0 
l=[int(i) for i in input().split()]
l.sort()
seen=[0]*(10**6+4)
for i in l:
    f=0 
    for x in div[i]:
        f+=seen[x]
    if f==0:
        cnt+=1 
    seen[i]+=1 
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

N = ri()
A = sorted(ri_(), reverse=True)
B = [1] * N
for i in range(N):
    for j in range(i):
        if A[j] % A[i] == 0:
            B[j] = 0
            if A[j] == A[i]:
                B[i] = 0
print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


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 solve(N: int, A: "List[int]"):
    ans = 0
    c = collections.Counter(A)
    dupes = {k for k, v in c.items() if v > 1}
    aset = set(A)
    for a in A:
        if a in dupes:
            continue
        if not (set(make_divisors(a)) - {a} & aset):
            ans += 1
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()