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 sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [0] * (max(a) + 1)
for x in a:
  # 重複
  if ans[x] != 0:
    ans[x] = 2
    continue
  for j in range(x, max(a)+1, x):
    ans[j] += 1

count = 0
for x in a:
  if ans[x] == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [0] * (max(a) + 1)
for i in range(n):
  # 重複
  if ans[a[i]] != 0:
    ans[a[i]] = 2
    continue
  for j in range(a[i], max(a)+1, a[i]):
    ans[j] += 1

count = 0
for x in a:
  if ans[x] == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

ans = [True] * n
for i in range(n):
  if ans[i] is False:
    continue
  for j in range(i+1, n):
    if a[j] % a[i] == 0:
      ans[j] = False
    if a[j] == a[i]:
      ans[i], ans[j] = False, False
 
print(ans.count(True))

Submission status: Time Limit Exceeded

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

ans = N

for i in range(N):
    j = 0
    while True:
        if j == N or A[j] > A[i]:break
        if i != j and A[i] % A[j] == 0:
            ans -= 1
            break
        j += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    D = [True] * n
    ans = 0

    for i, a in enumerate(A):
        if not D[i]:
            continue
        if i == n-1:
            ans += 1
            break
        if a != A[i+1]:
            ans += 1

        for j, aj in enumerate(A[i+1:]):
            if aj % a == 0:
                D[i+j+1] = False

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    q_prev = A
    q_next = []

    while len(q_prev) > 1:
        a = q_prev[0]
        if a != q_prev[1]:
            ans += 1

        for ai in q_prev:
            if ai % a != 0:
                q_next.append(ai)

        q_prev, q_next = q_next, []

    print(ans + len(q_prev))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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

            if i < j:
                ans += 1
                break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    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:
                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()))
A=sorted(A)
ans=0
length=N
while A:
    notdivisible=[]
    flag=True
    num=0
    for i in range(length-1):
        if A[i+1]%A[0]!=0:
            notdivisible.append(A[i+1])
            num+=1
        elif A[i+1]==A[0]:
            flag=False
    if flag:
        ans+=1
    A=notdivisible
    length=num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=sorted(A)
ans=0
while A:
    notdivisible=[]
    flag=True
    for i in range(len(A)-1):
        if A[i+1]%A[0]!=0:
            notdivisible.append(A[i+1])
        elif A[i+1]==A[0]:
            flag=False
    if flag:
        ans+=1
    A=notdivisible
print(ans)

Submission status: Time Limit Exceeded

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

lst = sorted(lst)
bol = [True]*n
s=0
for i in range(n-1):
  if bol[i] == True:
    bol[i] = False
    if lst[i] != lst[i+1]:
      s += 1
    
    for j in range(i+1,n):
      if bol[j] == True and lst[j] % lst[i] == 0:
        bol[j] = False

if bol[n-1] == True:
  s += 1
  
print(s)

Submission status: Time Limit Exceeded

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

lst = sorted(lst)
bol = [True]*n
s=0
for i in range(n-1):
  if bol[i] == True:
    if lst[i] != lst[i+1]:
      s += 1
    
    for j in range(i+1,n):
      if bol[j] == True and lst[j] % lst[i] == 0:
        bol[j] = False

if bol[n-1] == True:
  s += 1
  
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
prime_list = sorted(A)
sum = 0
while len(prime_list) != 0:
    count = 0
    min_A = prime_list[0]
    prime_list_ori = prime_list.copy()
    for i in range(len(prime_list_ori)):
        if ((prime_list_ori[i] % min_A) == 0):
            prime_list.remove(prime_list_ori[i])
            if (prime_list_ori[i] == min_A):
                count += 1
    if count == 1:
        sum += 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
prime_list = A.copy()
sum = 0
while len(prime_list) != 0:
    count = 0
    min_A = min(prime_list)
    prime_list_ori = prime_list.copy()
    for i in range(len(prime_list_ori)):
        if ((prime_list_ori[i] % min_A) == 0):
            prime_list.remove(prime_list_ori[i])
            if (prime_list_ori[i] == min_A):
                count += 1
    if count == 1:
        sum += 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
ans = 0
numset = set(a)
maxval = 10**6
dp = [0]*(maxval+1)
for i in range(n):
    if dp[a[i]] == 0 and (i == n-1 or a[i] != a[i+1]):
        ans += 1
    j = a[i]
    while j <= maxval:
        dp[j] += 1
        j += a[i]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
ans = 0
seen = set()
for i in range(n):
    for j in range(1,math.floor(math.sqrt(a[i]))+1):
        if a[i]%j == 0:
            x,y = j,a[i]//j
            if x in seen or y in seen:
                break
    else:
        ans += 1 if i == n-1 or a[i] != a[i+1] else 0
    seen.add(a[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,0]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)

    def s(d,y):
        global m
        global i
        global f
        if d==m-1:
            p=y
            if p!=i and z[p]>=1:
                f=1
        else:
            for j in range(w[d+1][1]+1):
                s(d+1,y*(w[d+1][0]**j))

    s(0,1)
    if f==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    if i%2==0:
        j=2
    else:
        j=3
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=2:
        f=1
    if i!=1 and z[1]==1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1

        if i%2==0:      
            j+=1
        else:
            j+=2
    if f==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！

n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1
for i in a:
    j=2
    f=0
    if z[i]>=2:
        f=1
    if z[1]>=2:
        f=1
    if i!=1 and z[1]==1:
        f=1
    while j*j<=i:
        if i%j==0:
            if z[j]>=1 or z[i//j]>=1:
                f=1
        j+=1
    if f==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#import numpy as np
def main():
    n, *a = map(int, read().split())

    if 1 in a:
        count1 = a.count(1)
        if count1 == 1:
            print(1)
            sys.exit()
        else:
            print(0)
            sys.exit()
    a.sort()
    res = [1] * n
    for i1 in range(n):
        ae = a[i1]
        for i2 in range(i1+1, n):
            if a[i2] == ae:
                res[i1] = 0
                res[i2] = 0
            elif a[i2] % ae == 0:
                res[i2] = 0
    print(sum(res))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
div = []
for i in nums:
  cnt[i] = cnt.get(i,0) + 1
  flag = 0
  for j in div:
    if i%j == 0:
      flag = 1
      break
  if flag == 0: 
    div.append(i)
    
for i in div:
  if cnt[i] == 1:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
unique = []
dupes = {}
for i in range(len(nums)):
  flag = 0
  for j in range(len(unique)):
    if i==j:
      continue
    if nums[i]%unique[j] == 0:
      if nums[i] == unique[j]:
        dupes[nums[i]] = 1
      flag = 1
      break
  if flag == 0:
    unique.append(nums[i])
for i in unique:
  if i in dupes:
    unique.remove(i)
print(len(unique))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
unique = []
for i in range(len(nums)):
  flag = 0
  for j in range(len(nums)):
    if i==j:
      continue
    if nums[i]%nums[j] == 0:
      flag = 1
      break
  if flag ==0:
    unique.append(nums[i])
print(len(unique))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
unique = []
for i in range(len(nums)):
  flag = 0
  for j in range(len(nums)):
    if i==j:
      continue
    if nums[i]%nums[j] == 0:
      flag = 1
  if flag ==0:
    unique.append(nums[i])
print(len(unique))

Submission status: Time Limit Exceeded

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
#print(A)
i=0
#M = min(max(A),10**6+1)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <10**6+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]

#print(A)

for e in A:
    if A.count(e)==1:
        Cs[e] = 1
#print(Cs[:30])
for e in A:
    i = 2
    while e*i < 10**6+1:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
res = 0
Ab = [True] * N
cnt = 0
for i in range(N):
    if Ab[i]:
        for j in range(i+1,N):
            if Ab[j] :
                if A[j] % A[i] == 0:
                     Ab[j] = False
                     if A[i] == A[j]:
                        Ab[i] = False
print(Ab.count(True))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

m = [0]*(10**6 + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    tmp = i 
    for j in range(i,10**6+1,i):
        m[j]+=1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

m = [0]*(10**6 + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    tmp = i 
    while tmp <= 10**6:
        m[tmp] += 1
        tmp += i
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
n = int(input())
a = np.array(list(map(int,input().split())),np.int32)

@njit(cache=True)
def solve():
    m = np.zeros(10**6 + 1)
    for i in a:
        if m[i] == 1:
            m[i] = 2
            continue
        m[::i] += 1
    ans = 0
    for i in a:
        if m[i] == 1:
            ans += 1
    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
n = int(input())
a = np.array(list(map(int,input().split())),np.int32)

@njit
def solve():
    m = np.zeros(10**6 + 1)
    for i in a:
        if m[i] == 1:
            m[i] = 2
            continue
        m[::i] += 1
    ans = 0
    for i in a:
        if m[i] == 1:
            ans += 1
    print(ans)

solve()

Submission status: Time Limit Exceeded

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

m = np.zeros(10**6 + 1,np.int32)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    m[::i] += 1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

m = np.zeros(10**6 + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    m[::i] += 1
    '''
    while tmp <= 10**6:
        m[tmp] += 1
        tmp += i
    '''
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


m = [0]*(10**6 + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    tmp = i 
    while tmp <= 10**6:
        m[tmp] += 1
        tmp += i
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
p=[0]*(10**6+1)
for i in range(n):
    if p[a[i]]==0:
        j=2
        while a[i]*j<=10**6:
            p[a[i]*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
p=[0]*(10**6+1)
for i in a:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

A.sort()

ans = 0

pre = -1

while A:
    maxim = A.pop()
    if maxim == pre:continue

    for item in A:
        if maxim % item == 0:
            ans -= 1
            break
    ans += 1
    pre = maxim

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)

ans = 0

pre = -1

while A:
    maxim = A.pop()
    if maxim == pre:continue

    for item in A:
        if maxim % item == 0:
            ans -= 1
            break
    ans += 1
    pre = maxim

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    a=list(map(int, input().split()))
    a.sort()
    arr=[0]*(10**6+1)
    flag=[True]*(10**6+1)
    ans=0
    for i in range(n):
        if flag[a[i]]:
            arr[a[i]]+=1
            for j in range(a[i]*2,10**6+1,a[i]):
                flag[j]=False
    print(arr.count(1))
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:


def main():
    n = int(input().strip())
    l = list(map(int, input().split()))

    l = sorted(l)
    flg = [1 for i in range(n)]

    if n == 1:
        print(1)
        exit()

    for i in range(n):
        if not flg[i]:
            if l[i-1] == l[i]:
                flg[i-1] = 0
            continue
        for j in range(1, n-i):
            if l[i+j] % l[i] == 0 and flg[i+j]:
                flg[i+j] = 0

    print(sum(flg))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    l = sorted(l)
    flg = [1 for i in range(n)]

    if n == 1:
        print(1)
        exit()

    for i in range(n):
        if not flg[i]:
            if l[i-1] == l[i]:
                flg[i-1] = 0
            continue
        for j in range(n-i-1):
            if l[i+1+j] % l[i] == 0 and flg[i+1+j]:
                flg[i+1+j] = 0

    print(sum(flg))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


anser = 0
for i in range(N):
    mod_list = [A[i]%x for x in A]
    mod_list.pop(i)
    if not 0 in mod_list:
        anser+= 1
print(anser)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split(" ")]
b = collections.Counter(a)
a_ = sorted(list(set(a)), reverse=True)
c = 1 if b[a_[-1]] == 1 else 0
for i in range(len(a_)-1):
    t = a_[i]
    if b[t] != 1:
        continue
    flag = 0
    for j in a_[i+1:]:
        if t%j == 0:
            flag = 1
            break
    if flag == 0:
        c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    import collections
    counter = collections.Counter(A)
    dp = [True for _ in range(max(A)+1)]
    for a in A:
        if counter[a] > 1:
            dp[a] = False
        for j in range(a+a, max(A)+1, a):
            dp[j] = False
    #print(dp)
    print(sum(1 for a in A if dp[a]))

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    import collections
    counter = collections.Counter(A)
    dp = [True for _ in range(max(A)+1)]
    ans = 0
    for a in A:
        if dp[a]:
            for j in range(max(A)//a+1):
                dp[a*j] = False
            if counter[a] == 1:
                ans += 1
    print(ans)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    dp = [True for _ in range(max(A)+1)]
    counts = [0 for _ in range(max(A)+1)]
    for a in A:
        counts[a] += 1
        if dp[a] and counts[a] == 1:
            for j in range(a*2, max(A)+1, a):
                dp[j] = False
    cnt = 0
    #print(dp)
    for a in A:
        if dp[a] and counts[a] == 1:
            cnt += 1
    print(cnt)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    dp = [True for _ in range(max(A)+1)]
    counts = [0 for _ in range(max(A)+1)]
    for a in A:
        if dp[a]:
            counts[a] += 1
            i = 2
            v = a * i
            while v <= max(A):
                dp[v] = False
                i += 1
                v = a * i
    cnt = 0
    for a in A:
        if dp[a] and counts[a] == 1:
            cnt += 1
    print(cnt)

if '__main__' == __name__:
    resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

A = max(a)

cnt = [0]*(A+1)
uq = []

for i in a:
    cnt[i] += 1

for i in range(A+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*((10**6)+1)
cnt1 = 0


a = list(set(a))

for i in a:
    for j in range(2,A+1):
        if i*j<=A+1:
            cnt[i*j] = 1

for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Time Limit Exceeded

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

a.sort()

cnt = [0]*(a[-1]+1)
uq = []

for i in a:
    cnt[i] += 1

for i in range(a[-1]+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*(a[-1]+1)
cnt1 = 0


a = list(set(a))



for i in a:
    for j in range(2, a[-1]+1):
        if i*j <= a[-1]:
            cnt[i*j] = 1


for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

B = Counter(A)
Key = list(B.keys())
Key.sort()

M = 10 ** 6
table = [1] * (M + 1)
cnt = 0
for k in Key:
    if B[k] == 1 and table[k] == 1:
        cnt += 1
    
    for i in range(M):
        if k * i > M:
            break
        else:
            table[k * i] = 0
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
INF = 10**6+1
lis = [1]*INF
exist = [0]*INF
for i in range(N):
    a = A[i]
    exist[a] += 1
    if lis[a]:
        q = 2
        while a*q < INF:
            lis[a*q] = 0
            q += 1
cnt = 0
for a in A:
    if lis[a] and exist[a] == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

divisible = [False for _ in range(int(1e6+1))]
cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
    if divisible[a] == False:
        for i in range(a+a, len(divisible), a):
            divisible[i] = True
ans = 0
for a in A:
    if divisible[a] is False and cnt[a] <= 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

divisible = [False for _ in range(int(1e6+1))]
cnt = defaultdict(int)

for a in A:
    cnt[a] += 1
    if divisible[a] == False:
        for i in range(a+a, len(divisible), a):
            divisible[i] = True
ans = 0
for a in A:
    if divisible[a] is False and cnt[a] <= 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
M = 10 ** 6
A = list(map(int, input().split()))
B = [0] * (M + 1)
for a in A:
    B[a] +=1
C = [1] * (M + 1)
for i in A:
    for j in range(i, M + 1, i):
        if i == j:
            if B[i] > 1:
                C[i] = 0
        else:
            C[j] = 0
A = set(A)
ans = 0
for a in A:
    if C[a]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

is_divided = [0]*n

for i in range(n):
  if is_divided[i]:
    continue
  for j in range(n):
    if j == i:
      continue
    if a[j]%a[i] == 0:
      is_divided[j] = 1
      if a[j] == a[i]:
        is_divided[i] = 1
      
print(n-sum(is_divided))

Submission status: Time Limit Exceeded

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

a.sort()

divisors = {}

divisors[a[0]] = 1

for i in range(1,n):
  div_flag = False
  for div in divisors.keys():
    if a[i]%div == 0:
      div_flag = True
      if div%a[i] == 0:
        divisors[div] = 0
      break
  if div_flag:
    continue
  else:
    divisors[a[i]] = 1

ans = 0
for key in divisors.keys():
  ans += divisors[key]
print(ans)

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):
  judge = 0
  for j in range(N):
    if A[j] > A[i] and i != j:
      break
    if A[i] % A[j] == 0 and i != j:
      judge = 1
      break
  if judge == 0:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from operator import mul
from functools import reduce


n = int(input())
A = list(map(int, input().split()))
cnt_a = Counter(A)
memo = [1] * 1000001
for a in A:
    memo[a] = 1
A.sort()
for a in A:
    for i in range(a * 2, 1000001, a):
        memo[i] = -1
for l in cnt_a.keys():
    if cnt_a[l] >= 2:
        memo[l] = "daburi"
ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [True] * n
c = Counter(a)
for i in range(n):
    if b[i]:
        for j in range(i+1, n):
            if a[j] % a[i] == 0 and i != j:
                b[j] = False
ans = 0
for i in range(n):
    if b[i] and c[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = [0]*(10**6+1)

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

print(sum(cnt))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n = int(input())
A = list(map(int,input().split()))
#素朴な解法(むり)
ans = 0
for i in range(n):
    flg=False
    for j in range(n):
        if i!=j and A[i]%A[j]==0:
            flg=True
    if not flg:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import array

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

A.sort()
cnt = 0
for i in range(N):
    for j in range(N):
        if A[i] % A[j] == 0 and i != j:
            cnt += 1
            break
        if A[j] > A[i]: break

print (N-cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
readline = sys.stdin.buffer.readline


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

cnt = np.zeros(1000005)
for x in a:
    if cnt[x] != 0: 
        cnt[x] = 2
    else: 
        for i in range(x,1000005,x):
            cnt[i] += 1

ans = 0
for x in a:
    if cnt[x] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

lst.sort()

s = 1
while True:
  if len(lst) == 1:
    break
  a = []
  if lst[0] == lst[1]:
    s -= 1
  for k in range(1,len(lst)):
    if lst[k] % lst[0] != 0:
      a.append(lst[k])
  lst = a    
  if a == []:
    break
  s += 1
  
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst = list(map(int,input().split()))
lst.sort()
check = ['t']*n
s = 1
i = 0
while True:
  if i == n-1:
    break
  else:
    a = []
    if lst[i+1] == lst[i]:
        s -= 1
    for k in range(i+1,n):
      if check[k] == 'f':
        pass
      else:
        if lst[k] % lst[i] == 0:
          check[k] = 'f'
        else:
          a.append(k)
    
    if a == []:
      break
    i = a[0]
    s += 1
    

print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
n = int(input())
lst = list(map(int,input().split()))
arr = np.array(lst)
lst.sort()
check = ['t']*n
s = 1
i = 0
while True:
  if i == n-1:
    break
  else:
    a = []
    if lst[i+1] == lst[i]:
        s -= 1
    for k in range(i+1,n):
      if lst[k] % lst[i] == 0:
        check[k] = 'f'
      if check[k] == 't':
        a.append(k)
    
    if a == []:
      break
    i = a[0]
    s += 1
    

print(s)