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:

import os
import sys
from io import BytesIO, IOBase


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    arr.sort()
    d = {}
    ans = 0
    s1 = 0
    d = {i: 0 for i in range(1, 10 ** 6 + 1)}
    for i in arr:
        if i == 1:
            s1 += 1
        d[i] += 1
    if s1 != 0:
        if s1 > 1:
            print(0)
            quit()
        else:
            print(1)
            quit()
    for i in range(n):
        x = arr[i]
        if d[x] == 1:
            f = 1
            for j in range(2, int(x ** 0.5) + 1):
                y = x // j
                if (d[j] >= 1 and x % j == 0) or (d[y] >= 1 and x % (y) == 0):
                    f = 0
                    break
            if f == 1:
                ans += 1
    print(ans)


# fast-io region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input():
    return sys.stdin.readline().rstrip("\r\n")


def write(*args, end="\n"):
    for x in args[:-1]:
        sys.stdout.write(str(x) + " ")
    sys.stdout.write(str(args[-1]))
    sys.stdout.write(end)


def r_array():
    return [int(x) for x in input().split()]


def r_int():
    return int(input())


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

cnt = 0
flag = -1
for i in range(N):
    flag = -1
    for j in range(N):
        if i != j:
            if A[i] % A[j] == 0:
                flag = 0
                break
    if flag == -1:
        cnt += 1

print(cnt)

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]

num = int(input())
a = list(map(int, input().split()))
b = 0
for i in a:
  for f in make_divisors(i):
    if f in a:
      if f == i and a.count(f) > 1:
        b += 1
        break
      elif f != i:
        b += 1
        break
print(num - b)

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]
        if i < n-1 and a[i] == a[i+1]:
            dic[a[i]] = 1
            continue
        flag = 1
        for check in range(1,int(x**0.5)+1):
            if(x%check==0):
                if dic[check]:
                    flag = 0
                    break
                if dic[x//check]:
                    flag = 0
                    break
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

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: # choufuku
                divisors.append(n//i)
    # divisors.sort()
    return divisors


exists = [False] * (10 ** 6 + 1)

input = raw_input
n0 = int(input())
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()


for A in As:
    exists[A] = True

for A1, num in counter.items():
    try:

        if num >= 2:
            continue
        
        exist = False

        ds = make_divisors(A1)
        for d in ds:
            if exists[d]:
                if d != A1:
                    exist = True

        if not exist:
            out += 1
    except:
        pass

print(out)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[int]"):
    cnt = 0
    for i in range(N):
        for j in range(N):
            if i != j and A[i] % A[j] == 0:
                break
        else:
            cnt += 1
    
    print(cnt)

    return


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


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
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:
import numpy as np

def main():
    n = int(input())
    a = np.array(list(map(int, input().split())))

    ans = 0
    #tmp = np.array([0]*n)
    for i in range(n):
        tmp = np.array([a[i]]*n) % a
        if np.count_nonzero(tmp) == n - 1:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
count = 0
for i in a:
  for j in a:
    if(i != j):
      if(i % j != 0):
        count = count +1
  if(count == n - 1):
    ans = ans +1
  count = 0
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
while len(A) > 0:    
    f = 0
    ans += 1
    s = A.pop()
    N = deque([])
    if len(A) == 0:
        break
    else:
        for i in range(len(A)):
            t = A.popleft()
            if t == s:
                f = 1
            elif t % s == 0:
                f = 0
            else:
                N.append(t)

        A = N
        #print(A)

        if f == 1:
            ans -= 1
        else:
            pass

print(ans)

Submission status: Time Limit Exceeded

Solution code:
input()
a = [int(i) for i in input().split()]
a.sort()

L = 0
for n,i in enumerate(a):
    H = 0
    for m,j in enumerate(a[:n+2]):
        if i % j == 0 and n != m:
            H = 1
            break
    if H == 0:
        L+=1
print(L)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nokori = N
kaburi = set()
ans = 0
A = list(map(int,input().rstrip().split(" ")))
A2 = set()
for i in A:
    if i in A2:
        kaburi.add(i)
    else:
        A2.add(i)
for i in kaburi:
    A2.remove(i)
for i in kaburi:
    k = i * 2
    while k < 1000000:
        A2.discard(k)
        k += i
while len(A2) != 0:
    i = min(A2)
    ans += 1
    k = i
    while k < 1000000:
        A2.discard(k)
        k += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque 
n = int(input())
a = list(map(int, input().split()))
a.sort()
a = deque(a)
if a.count(min(a)) >= 2:
    ans = 0
    z = 0
else:
    ans = 1
    z = 1
ln = [i for i in a if a.count(i) >= 2]
y = [min(a)]
while a:
    v = a.popleft()
    if v not in ln:
        x = 0
        for j in y:
            if v % j == 0:
                break
            else:
                x += 1
            if x == len(y):
                ans += 1
                y.append(v)
u = [i for i in y if i not in ln]
print(len(u))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
tf=[1]*n
n=n-1
notdiv=True
firstyn=0
for i in range(n,-1,-1):
  notdiv=True
  if tf[i] ==0:
    continue
  for j in range(i):
    if a[i]%a[j] == 0:
      tf[i]=0
    if a[j]%a[i] == 0:
      tf[j]=0
print(sum(tf))

Submission status: Time Limit Exceeded

Solution code:
# D - Not Divisible

n = int(input())
a = list(map(int, input().split()))
b = [1]*n
for i in range(n):
    for j in range(n):
        if i!=j:
            if a[i]%a[j]==0:
                b[i]=0

#check
#print(b)

print(sum(b))

Submission status: Time Limit Exceeded

Solution code:

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

ans_list=[i for i in range(N)]
for i in range(N):
  for j in range(N):
    if A[i]/A[j]-int(A[i]/A[j])==0 and i!=j:
      ans_list.remove(i)
      break
      
print(len(ans_list))
#print(gcd_list)

Submission status: Time Limit Exceeded

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

def calc():
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            if a[i] % a[j] == 0:
                break
        else:
            cnt += 1
    print(cnt)

calc()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
Alist = np.asarray( list(map(int, input().split())) )
y = np.zeros((N, ), dtype=np.int32)

for i in range(1, N):
  y += (Alist % np.roll( Alist, i ) ) == 0

print( sum(y==0) )

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
counter = collections.Counter(A)
B = list(set(A))
count = 0
for i in range(len(B)):
    if counter[B[i]]>1:
        continue
    if B[i]==1:
        count += 1
        continue
    else:
        check = 0
        for j in range(1,int(B[i]**0.5)+1):
            if (j != 1 and B[i]%j==0 and (j in counter or B[i]//j in counter)) or (j==1 and j in counter):
                check += 1
                break
        if check==0:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

flag = 0
cnt = 1
challengers = [a_l[0],]
for i in range(1,n):
    if a_l[i] in challengers:
        if flag == 0:
            cnt -= 1
        flag = 1
        continue
    else:
        flag = 0
    for num in challengers:
        if a_l[i]%num == 0:
            break
    else:
        cnt += 1
        challengers.append(a_l[i])

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n, *a = map(int, read().split())

b = [0] * n

a = sorted(a, reverse=True)

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

print(n - sum(b))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int, input().split())))
    pool = set()
    count = 0
    for i in range(n):
        t = a[i]
        if t in pool:
            continue
        if i+1 < n and t == a[i+1]:
            pool.add(t)
            continue
        limit = t // 2 +1
        is_ok = True
        for j in pool:
            if j > limit:
                break
            elif t % j == 0:
                is_ok = False
                #print("bad", t, j)
                break
        if is_ok:
            #print("good", t)
            pool.add(t)
            count += 1
    print(count)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for i in range(N):
    tmp = set()
    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:
            tmp.add(j)
            tmp.add(A[i]//j)

    if len(tmp & happend) >= 1 or count[A[i]] >= 2:
        ans += 1
    happend.add(A[i])

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:


def resolve():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip())

    a_set = set()
    duplicate = set()
    for a in input().rstrip().split():
        a = int(a)
        if a in a_set:
            duplicate.add(a)
        else:
            a_set.add(a)

    a_list = list(a_set)
    a_list.sort()

    answer = 0
    divisors = set()
    for a in a_list:
        judge = True
        for divisor in divisors:
            if a % divisor == 0:
                judge = False
                break
        if judge:
            divisors.add(a)
            if a in duplicate:
                continue
            answer += 1

    print(answer)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt=0
max_a= max(a)
#a_table=[True for i in range(n)]
while len(a) > 0:
    min_a=min(a)
    if a.count(min_a)==1:
        cnt+=1
    for k in range(1,max_a//min_a+1):
        a=[ele for ele in a if ele != min_a*k]
    #print(a)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math

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

dic = Counter(a)

ans = 0

memo = {}

for ai in a:
    cnt = 0
    f = 1
    if ai not in memo:
        for i in range(1, int(math.sqrt(ai))+1):
            if ai % i == 0:
                d = i
                if d in dic:
                    cnt += dic[d]
                if d == ai:
                    cnt -= 1
                if cnt > 0:
                    f = 0
                    break
                if i != ai // i:
                    d = ai // i
                    if d in dic:
                        cnt += dic[d]
                    if d == ai:
                        cnt -= 1
                    if cnt > 0:
                        f = 0
                        break
    else:
        f = memo[ai]
    ans += f
    memo[ai] = f

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().rstrip().split()]
done=[False for i in range(n)]

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

    if a[j]%a[i]==0:
      done[j]=True

print(done.count(False))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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()))
A.sort()
count = 0
B = deque([])
C = 0
for a in A:
    for b in B:
        if a % b == 0:
            if a == b and a != C:
                C = a
                count -= 1
            break
    else:
        B.appendleft(a)
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
sum = 0
for i, target in enumerate(a_list):
    for j, a in enumerate(a_list):
        if i == j:
            continue
        if target % a == 0:
            sum += 1
            # print('target:{}, a:{}'.format(target, a))
            break

print(n-sum)

Submission status: Time Limit Exceeded

Solution code:
n=input()
a_list=input().split()
for h in range(len(a_list)):
    a_list[h]=int(a_list[h])
num_suc=0

for i in range(len(a_list)):
    out=[]
    for j in range(len(a_list)):
        if i==j:
            continue
        else:
            if a_list[i]!=a_list[j]:
                q=a_list[i]//a_list[j]
                if a_list[j]*q==a_list[i]:
                    out.append("failed")
            else:
                out.append("failed")
    if not "failed" in out:
        num_suc+=1

print(num_suc)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if i == j:
            pass
        else:
            amari = a[i]%a[j]
            if amari == 0: # 次のaiへ
                flag = 1 # 割り切れなかった印
                break
            else: # 次のajへ
                pass
    if flag == 0: #　もし，一つも割り切れている要素が見つからなかったら
        ans += 1
    else:
        pass
    flag = 0 # フラグを元に戻す
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
C = Counter(A)

if 1 in C:
    if C[1] == 1:
        print(1)
    else:
        print(0)
    exit()

ans = 0
for k, v in C.items():
    if v > 1:
        continue
    for i in range(2, int(k**0.5)+1):
        if k % i == 0:
            if i in C:
                break
            if k // i in C:
                break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

temp_ans = [A.pop(0)]
div = []

for i in A:
  flag = 0
  for j in temp_ans:
    if i == j:
      div.append(i)
      flag = 1
      break
    if i % j == 0:
      flag = 1
      break
  if flag == 0:
    temp_ans.append(i)
print(len(temp_ans) - len(set(div)))

Submission status: Time Limit Exceeded

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

bunpu = [0 for i in range(10 ** 6 + 1)]
for _a in a:
  bunpu[_a] += 1

ans = 0
for _a in a:
  cnt = 0
  for i in range(1, int(_a ** 0.5) + 1):
    if _a % i == 0:
      cnt += bunpu[i]
      if i * i != _a:
        cnt += bunpu[_a // i]
    if cnt > 1:
      break
  if cnt == 1:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
A = Counter(list(map(int, input().split())))
A_keys = list(A.keys())
A_keys.sort()
for key in A_keys:
    A_keys = [x for x in A_keys if (x == key or x % key != 0)]
ans = 0
for key in A_keys:
    if A[key] > 1:
        continue
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


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

    MOD = 10 ** 9 + 7
    A.sort()
    A.append(MOD)
    s = set()

    ans = 0
    if A[0] != A[1]:
        ans += 1

    for i in range(1, n):
        if A[i] == A[i + 1] or i in s:
            continue

        for j in range(i):
            if A[i] % A[j] == 0:
                s.add(i)
                break
        else:
            ans += 1
            # print(f"{i = }, {j = }, {ans = }")

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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

ls=[]

for i,v in enumerate(a):
  ls.append([i+1,v])

ls.sort(key=lambda x: x[1])

i=0
deli=False
while i<len(ls):
  j = i+1
  while j<len(ls):
    if ls[j][1] == ls[i][1]:
      deli=True
    if ls[j][1] % ls[i][1] == 0:
      ls.pop(j)
      j-=1
    j+=1
    #print(ls)
  if deli:
    ls.pop(i)
    deli=False
    i-=1
  i+=1

print(len(ls))

Submission status: Time Limit Exceeded

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

ans = 0

while len(a) > 1:
    a0 = a[0]
    i_s = []
    for i in range(1,len(a)):
        if a[i]%a0 == 0:
            i_s.append(i)
    if a0 != a[1]:
        for i in range(len(i_s))[::-1]:
            a.pop(i_s[i])
        a.pop(0)
        ans += 1
    else:
        for i in range(len(i_s))[::-1]:
            a.pop(i_s[i])
        a.pop(0)

if len(a) == 1:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(len(A)):
    if i >= len(A)-1:
        break
    for j in range(len(A)-1,i,-1):
        if A[i] == A[j]:
            onaji = 1
        if A[j] % A[i] == 0:
            del A[j]
            
    if onaji == 1:
        del A[i]
        onaji = 0

print(len(A))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def make_divisors(n):
    divs = []
    i = 1
    while i*i <= n:
        if n % i == 0:
            divs.append(i)
            if i != n // i:
                divs.append(n//i)
        i += 1
    return divs

def solve():
    c = Counter(A)
    ret = 0
    set_A = set(A)
    for a in set_A:
        if 1 < c[a]:
            continue

        for d in make_divisors(a):
            if d == a:
                continue
            if d in set_A:
                break
        else:
            ret += 1
    print(ret)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 14 21:40:26 2020

@author: Kei
"""



N = int(input())

A = []*N
cnt_list = [0]*N
A = list(map(int,input().split()))

cnt = 1

for i in range(0,N):
    cnt = 1
#    print("Ai = "+str(A[i]))
    for j in range(0,N):
        if (i == j):
            continue
        if(A[i]%A[j] == 0):
#            print(A[i]%A[j])
            cnt = 0
#    print("cnt = "+str(cnt))
    if(cnt >= 1):
        cnt_list[i] = 1


print(cnt_list.count(1))

Submission status: Time Limit Exceeded

Solution code:


N = int(input())


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


A.sort()

d=[A[0]]
s=0
for i in range(N):
    if i!=N-1:
        if A[i]==A[i+1]:
            s+=1
            continue
    if i!=0:
        if A[i]==A[i-1]:
            s+=1
            continue
    if i==0:
        continue
    for j in range(len(d)):
            if A[i] % d[j] == 0:
                s += 1
                break
            if j == len(d)-1:
                d.append(A[i])

print(N-s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)
ans = 0

for i in range(len(a)):
  for j in range(a.index(a[i]) + 1, len(a)):
    if a[i] % a[j] == 0:
       ans += 1
       break

print(len(a) - ans)

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
        if A[j]*2 > A[i]:
            break
print(res)

Submission status: Time Limit Exceeded

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



cnt = Counter(A)
A.sort()
ans = 0
for i in range(len(A)):
    if cnt[A[i]] > 1:
        continue
    #idx = bisect.bisect_left(A, pow(A[i],0.5))
    #J = min(idx+1,i)
    J = i
    ok = True
    for j in range(J):
        #print(i,j)
        if A[i] % A[j] == 0:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import numpy as np

def get_input():
    if test_mode:
        return f.readline().rstrip()
    else:
        return input().rstrip()

def int_list(l):
    for i in range(len(l)):
        l[i] = int(l[i])
        
if os.path.exists('input.txt'):
    test_mode = True
else:
    test_mode = False

if test_mode:
    f = open('input.txt')
    
N = int(get_input())
A = get_input().split()
int_list(A)
A.sort()
ans = 0

for i in range(0, N):
    wareta = False
    for j in range(0, min([i+2, N])):
        if A[i] % A[j] == 0 and i != j:
            wareta = True
            break
    if not wareta:
        ans += 1
print(ans)

if test_mode:
    f.close()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A_list=list(map(int,input().split()))
ans=0
for i in A_list:
    count=0
    for j in A_list:
        if i%j==0:
            count+=1
    if count<=1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    A.sort()
    s = set(A)
    ret = 0
    found_1 = False
    for idx, v in enumerate(A):
        ok = found_1 or (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        if not ok:
            for i in range(2, 1001):
                if v == i:
                    continue
                if v % i == 0 and (i in s or v // i in s):
                    ok = True
                    break
        if not ok:
            ret += 1
        found_1 = found_1 or v == 1
    print(ret)

def solve_(N: int, A: "List[int]"):
    def is_p(v):
        i = 2
        while i * i <= v:
            if v % i == 0:
                return False
            i += 1
        return True
    primes = []
    for i in range(2, 1001):
        if is_p(i):
            primes.append(i)
    #print(primes)

    A.sort()
    ret = 0
    tmp = set(A)
    tmp2 = []
    for idx, v in enumerate(A):
        ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
        for p in primes:
            if ok or p * p > v:
                break
            if v % p == 0 and (p in tmp or v // p in tmp):
                ok = True
        #print(v, ok)
        if not ok:
            for t in A:
                if t == v:
                    continue
                #if ok or t * t > v:
                #    break
                if v % t == 0:
                    ok = True
                    break
        if ok:
            pass
        else:
            #tmp.add(v)
            #tmp2.append(v)
            ret += 1
    print(ret)
    #tmp = []
    #for idx, v in enumerate(A):
    #    l = len(tmp)
    #    i = 0
    #    ok = (idx > 0 and v == A[idx - 1]) or (idx < N - 1 and v == A[idx + 1])
    #    while not ok and i < l and tmp[i] * tmp[i] <= v:
    #        if v % tmp[i] == 0:
    #            ok = True
    #            break
    #        i += 1
    #    if ok:
    #        pass
    #    else:
    #        print(v)
    #        ret += 1
    #        tmp.append(v)
    #print(ret)
    #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:
n = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(n):
    f = True
    for j in range(n):
        if i == j:
            continue
        
        if A[i]%A[j] == 0:
            f = False
            break
    if f:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = [int(x) for x in input().split()]
invans = 0
for i in range(N):
    for j in range(N):
        if i == j or Alist[i] < Alist[j]:
            None
        else:
            if Alist[i] % Alist[j] == 0:
                invans += 1
                break

print(N - invans)

Submission status: Time Limit Exceeded

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

print(a-count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = 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] == 0:
                    break
            if j == n - 1:
                cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()