Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

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

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

Constraints

All values in input are integers.

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

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

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

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

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

a.sort()
check = []
ans = 0

### 2 から 1000までの素数を列挙
prime = [i+2 for i in range(999)]
### エラトステネスの篩
index = 0
ans = 0
while True :
  if index == len(a) :
    break
  else :
    p = a[index]
    check_index = index + 1
    flag = False
    while True :
      if check_index == len(a) :
        break
      else :
        if a[check_index] == p :
          flag = True
          a.pop(check_index)
        elif a[check_index] % p == 0 :
          a.pop(check_index)
        else :
          check_index += 1
    index += 1
    if flag :
      ans -= 1

print(index+ans)

Submission status: Time Limit Exceeded

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

a.sort()
check = []
ans = 0
### 小さいほうから順番にチェック
for i in range(len(a)) :
  ### 同じ数が存在するかチェック
  if len(check) > 0 :
    if check[-1] == a[i] :
      continue
  if i < len(a) - 1 :
    if a[i+1] == a[i] :
      check.append(a[i])
      continue
  
  ### これ以降は省略できないか?
  flag = False
  for p in check :
    if a[i]%p == 0 :
      flag = True
      break
  ### 割り切れるものがcheck内になかったものを数える
  
  if not(flag) :
    ans += 1
    check.append(a[i])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    flag = 0
    A2 = deepcopy(A)
    del A2[i]
    Aas = sorted(A2)
    if a not in A2:
        for b in Aas:
            if a % b  == 0:
                flag = 1
                break
            if a/b < 2:
                break
    else:
        flag = 1
    if flag == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
THE_NUM = 10**6 + 1

dp = [True] * THE_NUM

prev_num = -1
for i in A:
  # if the same number appears as before, that number cannot be counted in the answer.
  if prev_num == i:
    dp[i] = False
  prev_num = i
  for j in range(i * 2, THE_NUM, i):
    dp[j] = False

ans = 0
for i in A:
  # the same number after the second will not counted in the answer.
  if dp[i] == True:
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
count=0
b=Counter(a)
count_list=[0]*(10**6)
for i in a:
  if b[i]==1:
    if count_list[i-1]==0:
      count+=1
      j=1
      while i*j<=10**6:
        count_list[i*j-1]+=1
        j+=1
  else:
    j=2
    while i*j<=10**6:
      count_list[i*j-1]+=1
      j+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
A_max = A_list[N-1]

is_prime = [True] * (A_max+1)
is_prime[0] = False

for i in range(1, A_max):
    if i not in A_list:
        is_prime[i] = False


for i in A_list:
    if not is_prime[i]:
        continue
    for j in range(i*2, A_max+1, i):
        is_prime[j] = False
    if A_list.count(i) >= 2:
        is_prime[i] = False

print(is_prime.count(True))

Submission status: Time Limit Exceeded

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

is_prime = [True] * N
for i in range(N):
    if is_prime[i] == False:
        continue
    for j in range(i+1, N):
        if A_list[j] % A_list[i] == 0:
            is_prime[j] = False
    if i != N-1:
        if A_list[i] == A_list[i+1]:
            is_prime[i] = False

print(is_prime.count(True))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    flag = 0
    for j,b in enumerate(A):
        if a % b  == 0 and i != j:
            flag = 1
            break
    if flag == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
N = int(input())
A = list(map(int,input().split()))
count = 0
for i,a in enumerate(A):
    flag = 0
    A2 = deepcopy(A)
    del A2[i]
    for j in A2:
        if a % j == 0:
            flag = 1
            break
    if flag == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Nlist = []  # Aを順番に入れていきます
count = 0  # inputのリスト位置
ans = [0]*N  # 割り切れる場合と同じ場合に1を入れる
for A in input().split():
    for i in range(len(Nlist)):
        if int(A) == Nlist[i]:
            ans[count] = 1
            ans[i] = 1
        elif int(A) % Nlist[i] == 0:
            ans[count] = 1
        elif Nlist[i] % int(A) == 0:
            ans[i] = 1
    Nlist.append(int(A))
    count = count+1
print(ans.count(0))#同じではない場合と割り切れない場合は初期値0のまま

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
dp = [True for i in range(max(A)+1)]
d = {}
for i in A:
    if i in d.keys():
        d[i]+=1
    else:
        d[i] = 1

for i in A:
    
    
    if (dp[i]):
        if d[i]>1:
            dp[i]  = False
        j = 2*i
        while (j<=max(A)):
            dp[j] = False
            j+=i
count = 0
for i in A:
    if dp[i] == True:
        count +=1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
b = [False] * 1000010
for i in range(n - 1):
    if a[i] == a[i + 1]:
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

ans = 0
for i in range(n):
    if not b[a[i]]:
        ans += 1
        for j in range(a[i], 1000010, a[i]):
            b[j] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_n = sorted(list(map(int, input().split(' '))))
count = 0
for i in range(len(A_n)):
    # print(list(map(lambda x: x%A_n[i], A_n)))
    if list(map(lambda x: A_n[i]%x, A_n)).count(0) == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)
i = 0
for key, count in sorted_dict:
    if flag_list[i] == 0:
        i += 1
        continue
    if count > 1:
        flag_list[i] = 0
    i += 1
    j = i
    for key1, count1 in sorted_dict[i:]:
        if flag_list[j] == 0:
            j += 1
            continue
        if key1 % key == 0:
            flag_list[j] = 0
        j += 1
print(sum(flag_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = list(map(int, input().split()))
count = [0]*N
nums.sort()
answer = N
for i in range(N):
  fNum = nums[i]
  for j in range(N):
    sNum = nums[j]
    if (sNum > fNum):
      break
    elif (i == j):
      continue
    else:
      if (fNum%sNum == 0):
        answer -= 1
        break

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
p=[]
while True:
    if len(a)==0:
        break
    prime=min(a)
    p.append(prime)
    i = 0
    while i < len(a):
        if a[i] % prime == 0:
            a.pop(i)
            continue
        i += 1

for x in a:
    p.append(x)
g=0
for i in range(len(p)):
    if b.count(p[i])>1:
        g+=1
print(len(p)-g)

Submission status: Time Limit Exceeded

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

C = {a:0 for a in A}

for a in A:
    C[a] = C[a]+1

maxA = max(A)

D = {a:0 for a in A}

for a in A:
    t = 2
    while a*t <= maxA:
        if a*t in A:
            D[a*t] = D[a*t]+1
        t = t+1

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter = counter+1
        
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
# n = 10
# A = [33, 18, 33, 28, 8, 19, 89, 86, 2, 4]

C = {a:0 for a in A}

for a in A:
    C[a] = C[a]+1

maxA = max(A)

D = {a:0 for a in A}

for a in A:
    t = 2
    while a*t <= maxA:
        if a*t in A:
            D[a*t] = D[a*t]+1
        t = t+1

counter = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        counter = counter+1
        
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int,input().split()))
#n = 10
#A = [33, 18, 45, 28, 8, 19, 89, 86, 2, 4]

C = 0

for i in range(n):
    for j in range(n):
        if A[i] % A[j] == 0 and i != j:
            C = C+1
            break

print(n-C)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr= list(map(int,input().split(' ')))
arr.sort()
count=0
d= [True for i in range(arr[n-1]+1)]
for i in range(n):
    curr= arr[i]
    if d[curr]==True:
        if arr.count(curr)==1:
            count+=1
        db= curr*2
        while db<=arr[n-1]:
            d[db]=False
            db+=curr
print(count)

Submission status: Time Limit Exceeded

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

Sum = 0

A.sort()
sosuu = []

for i in range(N):

    if i > 0:
        if A[i] == A[i-1]:
            continue

    flag = True

    for j in range(len(sosuu)):
        if A[i] % sosuu[j] == 0:
            flag = False
            break

    if flag:
        if i + 1 < N:
            if A[i] != A[i+1]:
                Sum += 1
        else:
            Sum += 1
        
        sosuu.append(A[i])

print(Sum)

Submission status: Time Limit Exceeded

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

Sum = 0

A.sort()
sosuu = []

for i in range(N):

    if i > 0:
        if A[i] == A[i-1]:
            continue

    flag = True

    for j in range(len(sosuu)):
        if A[i] % sosuu[j] == 0:
            flag = False
            break

    if flag:
        if A.count(A[i]) == 1:
            Sum += 1
        sosuu.append(A[i])

print(Sum)

Submission status: Time Limit Exceeded

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

Sum = 0

A.sort()
sosuu = []

for i in range(N):

    flag = True

    for j in range(len(sosuu)):
        if A[i] % sosuu[j] == 0:
            flag = False
            break

    if flag:
        if A.count(A[i]) == 1:
            Sum += 1
        sosuu.append(A[i])

print(Sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
sieve=[0]*1000009
n=int(input())
s=sorted(map(int,input().split()))
for i in s:
    for j in range(i,1000009,i):sieve[j]+=1
print(sum(sieve[i]==1for i in s))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    count = 0
    for j in range(n):
        if i == j:
            continue

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

        elif a[i] % a[j] == 0:
            count += 1
        else:
            continue
    if count == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx + 1, len(An)):
            if An[i] != 0 and An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                    flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

Submission status: Time Limit Exceeded

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

An.sort()

idx = 0

while True:
    if idx >= len(An):
        print(len(An))
        exit()

    flg = False
    div_idx = idx + 1

    while True:
        if div_idx == len(An):
            break

        if An[div_idx] % An[idx] == 0:
            if An[div_idx] == An[idx]:
                flg = True
            An.pop(div_idx)
        else:
            div_idx += 1

    if flg:
        An.pop(idx)

    idx += 1

Submission status: Time Limit Exceeded

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

An.sort()

idx = 0

while True:
    if idx == len(An):
        ans = len(An) - An.count(0)
        print(ans)
        exit()

    flg = False
    if An[idx] != 0:
        for i in range(idx+1, len(An)):
            if An[i] % An[idx] == 0:
                if An[i] == An[idx]:
                   flg = True
                An[i] = 0
        if flg:
            An[idx] = 0

    idx += 1

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n==1:
    print(1)
else:
    l=[int(i) for i in input().split()]
    l.sort()
    d=dict()
    for i in l:
        d[i]=True
    res=0
    for i in range(n):
        if d[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(i+1,n):
                if not l[j]%l[i]:
                    d[l[j]]=False
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n==1:
    print(1)
else:
    oklist=[True for i in range(1000001)]
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    for i in range(n):
        if oklist[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(1,1000001):
                if l[i]*j<=1000000:
                    oklist[l[i]*j]=False
    print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
if n==1:
    print(1)
else:
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    ll=[]
    for i in range(n):
        flag=True
        for j in ll:
            if not l[i]%j:
                flag=False
                break
        if flag:
            ll.append(l[i])
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
    print(res)

Submission status: Time Limit Exceeded

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

total = 0
flag = 0

for i in range(n):
  if i != n-1:
    if a[i] == a[i + 1]:
      continue
  for j in range(i):
    if i == j:
      continue
    
    if int(a[i]/a[j]) == a[i]/a[j]:
      flag = 1
      break
    
  if flag == 0:
    total += 1
  else:
    flag = 0
    
print(total)

Submission status: Time Limit Exceeded

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

total = 0
flag = 0

for i in range(n):
  for j in range(i):
    if i == j:
      continue
    
    if int(a[i]/a[j]) == a[i]/a[j]:
      flag = 1
      break
  
  if i != n - 1:
    if a[i] == a[i + 1]:
      flag = 1
    
  if flag == 0:
    total += 1
  else:
    flag = 0
    
print(total)

Submission status: Time Limit Exceeded

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

total = 0
flag = 0

for i in range(n):
  for j in range(n):
    if i == j:
      continue
    
    if int(a[i]/a[j]) == a[i]/a[j]:
      flag = 1
      break
    
  if flag == 0:
    total += 1
  else:
    flag = 0
    
print(total)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

setA = set(A)
from collections import defaultdict
cnt = defaultdict(int)

for a in A:
    cnt[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]

score = 0
for a in A:
    if cnt[a] > 1:
        continue
    
    divisors = make_divisors(a)

    ng = False
    for d in divisors:
        if d==a: continue
        if d in setA:
            ng = True
            break
            
    if not ng:
        score += 1
    # print(a, divisors)
print(score)

Submission status: Time Limit Exceeded

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

setA = set(A)
from collections import defaultdict
cnt = defaultdict(int)

for a in A:
    cnt[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]

score = 0
for a in A:
    if cnt[a] > 1:
        continue
    
    divisors = make_divisors(a)

    ng = False
    for d in divisors:
        if d==a: continue
        if d in setA:
            ng = True
            
    if not ng:
        score += 1
    # print(a, divisors)
print(score)

Submission status: Time Limit Exceeded

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

setA = set(A)
from collections import defaultdict
cnt = defaultdict(int)

for a in A:
    cnt[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]

score = 0
for a in A:
    divisors = make_divisors(a)
    ng = False
    for d in divisors:
        if d==a:
            if cnt[d] > 1:
                ng = True

        elif d in setA:
            ng = True
    if not ng:
        score += 1
    # print(a, divisors)
print(score)

Submission status: Time Limit Exceeded

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

flag = 1 
cnt = 0 

for i in range(N):
        if i + 1 > len(A):
                break
        flag = 1 
        for j in reversed(range(i + 1, len(A))):
                if A[j] == A[i]:
                        flag = -1
                if A[j] % A[i] == 0:
                        del A[j]
        if flag == -1: 
                cnt += 1

print(len(A) - cnt)

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0 

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

print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit, int64

@njit(int64(int64,int64[:],int64[:]))
def solve(N, A, nums):
    for ind, i in enumerate(A[:-1]):
        if nums[i-1] == 1:
            nums[A[A%i == 0] - 1] = 0
            nums[i-1] = 1
            if ind < N and A[ind+1] == i:
                nums[i-1] = 0

    return (len(nums[nums>0]))

N = int(input())
A = np.sort(np.array(list(map(int, input().split())),dtype=np.int64))
np.append(A,0)
nums = np.full(A.max()+1, 0, dtype=np.int64)
nums[A-1] = 1 #0-indexed
print(solve(N, A,nums))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit, int64

@jit(int64(int64,int64[:],int64[:]))
def solve(N, A, nums):
    for ind, i in enumerate(A[:-1]):
        if nums[i-1] == 1:
            nums[A[A%i == 0] - 1] = 0
            nums[i-1] = 1
            if ind < N and A[ind+1] == i:
                nums[i-1] = 0

    return (len(nums[nums>0]))

N = int(input())
A = np.sort(np.array(list(map(int, input().split())),dtype=np.int64))
np.append(A,0)
nums = np.full(A.max()+1, 0, dtype=np.int64)
nums[A-1] = 1 #0-indexed
print(solve(N, A,nums))

Submission status: Time Limit Exceeded

Solution code:
import sys


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def main():
    n = int(input())
    aa = input_ints()
    aa.sort()
    rr = [True] * n
    for i in range(0, n-1):
        if aa[i] == aa[i+1]:
            rr[i] = False
            rr[i+1] = False

    for i in range(0, n):
        for j in range(0, i):
            if aa[i] % aa[j] == 0:
                rr[i] = False
                break
    
    print(len([r for r in rr if r]))


main()

Submission status: Time Limit Exceeded

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

out=[]
i =0
while i < N:
    out.append(i)
    for j,a in enumerate(A):
        if i!=j and A[i]%a==0:
            out.pop()
            break
    i += 1
print(len(out))

Submission status: Time Limit Exceeded

Solution code:
# D - Not Divisible
N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [1 for _ in range(N)]
num_list.sort()
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list[i] = -1
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list[i] = -1
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list[N-1] = -1
        break
print(ind_list.count(1))

Submission status: Time Limit Exceeded

Solution code:
# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [1 for _ in range(N)]
num_list = aline_mintomax(num_list, N)
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list[i] = -1
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list[i] = -1
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list[N-1] = -1
        break
print(ind_list.count(1))

Submission status: Time Limit Exceeded

Solution code:
# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [i for i in range(N)]
num_list = aline_mintomax(num_list, N)
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list.remove(i)
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list.remove(i)
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list.remove(N-1)
        break
print(len(ind_list))

Submission status: Time Limit Exceeded

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

a.sort()

b=[]
c=[]

while True:    
    same = 0
    i = a.pop(0)
    if i in a:
        same = 1
    for j in a:
        if j%i != 0:
            b.append(j)
    if same ==0:
        c.append(i)
    if len(b) == 0:
        break
    a = b
print(len(c))

Submission status: Time Limit Exceeded

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

a.sort()

b=[]


while True:    
    same = 0
    i = a.pop(0)
    if i in a:
        same = 1
    a = [x for x in a if x%i != 0]
    if same ==0:
        b.append(i)
    if len(a) == 0:
        break

print(len(b))

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)


count = 0
# i<n-1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
            count += 1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(n-1, i, -1):
            if a[i] % a[j] == 0:
                break
            if j == i+1:
                count += 1

# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)


count = 0
# i<n-1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
            count += 1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(i+1, n):
            if a[j] != a[j-1]:
                if a[i] % a[j] == 0:
                    break
                if j == n-1:
                    count += 1

# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [0] * (10**6 + 1)

multi = 0
count = 0
for l in range(n):
    for m in range(1, 10**6 + 1):
        multi = a[l] * m
        if multi > 10**6:
            break
        else:
            b[multi] += 1

c = 0
for i in range(n):
    c = int(a[i])
    if b[c] == 1:
        count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=["True"]*(max(a)+1)
dp[0]="False"
a.sort()
seen=set()
pre=0
for x in a:
    if x==pre:
        if x in seen:
            seen.remove(x)
        continue
    if dp[x]=="True":
        seen.add(x)
    pre=x
    i=1
    while x*i<=max(a):
        if dp[x*i]=="True":
            dp[x*i]="False"
        i+=1
print(len(seen))

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)


count = 0
# i<n-1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
            count += 1
"""
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        for j in range(i+1, n):
            if a[i] % a[j] == 0:
                break
            if j == n-1:
                count += 1

# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=["True"]*(max(a)+1)
dp[0]="False"
a.sort()
seen=set()
pre=0
for x in a:
    if x==pre:
        if x in seen:
            seen.remove(x)
        continue
    if dp[x]=="True":
        seen.add(x)
    pre=x    
    i=1
    while x*i<=max(a):
        dp[x*i]="False"
        i+=1
print(len(seen))

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)

count = 0
# i<n-1
for i in range(n-1):
    if a[i] != a[i+1] and a[i] != a[i-1]:
        if all([a[i] % a[j] != 0 for j in range(i + 1, n)]):
            count += 1
# i==n-1
if a[n-2] != a[n-1]:
    count += 1

if n != 1:
    print(count)
elif n == 1:
    print(1)

Submission status: Time Limit Exceeded

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

num=0
for i in range(n):
    count=0
    for j in range (n):
        if a[i]%a[j]==0:
            count+=1
        
    if count==1:
            num+=1

print(num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(N, A, nums):
    for ind, i in enumerate(A[:-1]):
        if nums[i-1] == True:
            nums[A[A%i == 0] - 1] = False
            nums[i-1] = True
            if ind < N and A[ind+1] == i:
                nums[i-1] = False

    print(len(nums[nums>0]))

N = int(input())
A = np.sort(np.array(list(map(int, input().split()))))
np.append(A,0)
nums = np.full(A.max()+1, False, dtype=np.bool_)
nums[A-1] = True #0-indexed
solve(N, A,nums)

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=list(map(int,input().split()))
c=max(b)+1
d=[]
ans=0
for i in range(a):
  e=0
  while c-e>b[i]:
    e+=b[i]
    d+=[e]
for i in b:
    if d.count(i)==1:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    from collections import Counter
    c = Counter(A)

    for a in set(A):
        v = 2*a
        while v <= 10**6:
            c[v] += 1
            v += a

    ans = 0
    for a in A:
        if c[a] == 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()))
A.sort()
# Max=int(A[-1]**0.5)
flag=[1]*N

for i in range(N):
    if flag[i]==0:
        continue
    # if A[i]>Max:
    #     break
    for j in range(i+1,N):
        if A[j]%A[i]==0:
            flag[j]=0

for i in range(N-1):
    if A[i]==A[i+1]:
        flag[i],flag[i+1]=0,0

print(sum(flag))