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:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    max_a = max(a)
    arr = [1] * (max_a + 1)

    for num in a:
        if a.count(num) > 1:
            arr[num] = 0
        for i in range(num*2, max_a+1, num):
            arr[i] = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from sys import exit
N = int(input())

#例外処理
if N == 1:
  print(1)
  exit()

#入力
A = list(map(int, input().split()))

#重複抽出
ban = {x for x in set(A) if A.count(x) > 1}

#ソート、初期値
D = deque(sorted(list(set(A))))
ans = 0

#最小値の倍数の存在を1ループで除く
while D:
  #最小値取り出し
  ini = D.popleft()
  
  #重複でなければ最小値は題意を満たす
  if not ini in ban:
    ans += 1
    
  #最後の1つの処理
  if len(D) == 0:
    break
    
  #倍数判定
  for i in range(len(D)):
    d = D.popleft()
    
    #倍数でなければ戻す
    if d % ini != 0:
      D.append(d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def make_divisors(n):
    l_divs, u_divs = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            l_divs.append(i)
            if i != n // i:
                u_divs.append(n // i)
        i += 1
    return l_divs + u_divs[::-1]


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    aset = list(set(A))
    aset.sort()

    past = set()
    ans = 0
    ansset = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in past:
                break
        else:
            ansset.add(a)
            ans += 1

        past.add(a)

    c = collections.Counter(A)
    for k in c.keys():
        if c[k] > 1 and k in ansset:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  a=sorted(map(int,input().split()))
  #maxa=a[-1]+1
  af=[False]*n
  #tf=[False]*maxa
  r=0
  n-=1
  for i in range(n):
    a_i=a[i]
    if af[i] ==False:
      #print(a_i)
      if a_i < a[i+1]:
        r+=1
      for j in range(i+1,n+1):
        #print(a[j])
        if af[j] ==False and a[j] % a_i == 0:
          #print(str(a_i)+"aj:"+str(a[j]))
          af[j]=True
  if af[-1] ==False:
    r+=1
  print(r)
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [0]*(max(A))

for i in A:
    B[i-1] += 1

ans = 0
for i in range(1,max(A)+1):
    if B[i-1] == 0:
        continue
    if B[i-1] == 1:
        ans += 1
    for j in range(2 * i,max(A)+1,i):
        B[j-1] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[1]*n
    a.sort()
    ans=0
    for i in range(n):
        if b[i]!=-1:
            for j in range(i+1,n):
                if a[j]%a[i]==0:
                    b[j]=0
                    if a[j]==a[i]:
                        b[i]=0
    print(sum(b))
resolve()

Submission status: Time Limit Exceeded

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

# 0 ~ 10**6
A_list = [True for i in range(10**6+1)]

# aのリストを作成
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# aのリストの重複削除
for i in a_l:
	if(a_l.count(i) != 1):
		A_list[i] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in range(len(a_l)):
	if(A_list[a_l[i]]):
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;

    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 2
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
#n = 2 * 10**5
#a = [i for i in range(1, n+1)]

a.sort()
def Eratosthenes(x):
    c = collections.Counter(x)
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in range(1, nmax+1):
        if c[i] > 1:
            is_prime[i] = False
    for i in range(1, nmax+1):
        if is_prime[i] == True and i in a:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Time Limit Exceeded

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

# 0 ~ 10**6
A_list = [True for i in range(10**6+1)]

# aのリストを作成
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in range(len(a_l)):
	if(a_l.count(a_l[i]) != 1):
		continue
	if(A_list[a_l[i]]):
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

a.sort()
dp = [True] * (max(a) + 1)
ans = 0

for i,num in enumerate(a):
    if dp[num-1]:
        j= 2 * num
        while j <= max(a):
            dp[j-1] = False
            j += num
        if not i+1==len(a):
            if a[i]==a[i+1]:
                dp[num-1] = False

for k in a:
    if dp[k-1]:
        ans += 1

#print(dp)
print(ans)

Submission status: Time Limit Exceeded

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

output_list = []
A_list = sorted(A_list)
# print(A_list)
A_len = len(A_list)
while True:
  n = A_list[0]
  if len(A_list) > 1 and A_list[1] == n:
    pass
  else:
    output_list.append(n)
  A_list = [i for i in A_list if i % n != 0]
  # print(A_list)
  A_len = len(A_list)
  if A_len == 0:
    break
  
# print(output_list)
print(len(output_list))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう
remove_list = []

kouho = [x for x in set(A) if A.count(x) == 1]

#target = kouho[:]
if kouho != []:
    maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)
#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))
print(len(kouho))

Submission status: Time Limit Exceeded

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

def divisors(n):
    lst = []; i = 1
    while i ** 2 <= n:
        q, r = divmod(n, i)
        if r == 0:
            lst.append(i)
            if i != q: lst.append(q)
        i += 1
    return lst

N = int(input())
*A, = map(int, input().split())
A = sorted(A)
cnt = [0] * (10**6 + 1)
for a in A: cnt[a] += 1
ans = 0
for a in A:
    if cnt[a] > 1: continue
    for i in divisors(a):
        if i == a: continue
        if cnt[i] >= 1: break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
dp = [True] * N

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

Submission status: Time Limit Exceeded

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

dellist = []
# A[0]は最小なので同じ数字を除いてそれよりも大きい他の数では割り切れない。
i = 0
while(i < len(A)):
    j = i+1
    poplist = []
    while(j < len(A)):
        if A[j]%A[i] == 0: # 割り切れちゃった場合
            # A[j]をあとで消すために控える
            poplist.append(j)
            # A[i]とA[j]が同じ数字なら、最後にA[i]も消す必要があるので、
            # A[i]を削除リストに入れる
            if A[i]  == A[j]:
                dellist.append(A[i])
                
        j += 1
        
    # poplistにあるA[]を消す
    # 前から消していくと順番が狂うので、後ろから消す。参考↓
    # https://gammasoft.jp/blog/remove-multiple-elements-from-python-list/
    for k in sorted(poplist, reverse=True):
        A.pop(k)
    # A[i]で割り切れるものは探しきって、次のA[i+1]は割り切れないもの。
    # 次はA[i+1]について考える
    i += 1

# remove は、指定した要素がlistに含まれていないとエラーを吐くみたいなので、
# 重複を排除する
dellist = list(set(dellist))
    
for i in dellist:
    A.remove(i)

# print(A)
print(len(A))
# print(dellist)

Submission status: Time Limit Exceeded

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

l = sorted(a)
dp = [True] * (max(l) + 1)
ans = 0

for i,num in enumerate(l):
    if dp[num-1]:
        j= 2 * num
        while j <= max(l):
            dp[j-1] = False
            j += num
        if not i+1==len(l):
            if l[i]==l[i+1]:
                dp[num-1] = False

for k in l:
    if dp[k-1]:
        ans += 1

#print(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;
        continue

    if a[i] < 2 * 100:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 2
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;
        continue

    if a[i] < 2 * 10:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:   
        times = 2
        while a[i] * times <= a[-1]:
            r = bisect.bisect_left(a, a[i] * times + 1)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
#n = 2 * 10**5
#a = [i for i in range(1, n+1)]

a.sort()
def Eratosthenes(x):
    c = collections.Counter(x)
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in range(1, nmax+1):
        if c[i] > 1:
            continue
        if is_prime[i] == True and i in a:
            cnt += 1
    print(cnt)

Eratosthenes(a)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ok = [0]*(max(a)+1)
a.sort()

for i in range(n):
    ok[a[i]] += 1
    if ok[a[i]] == 1:
        for g in range(2*a[i], max(a)+1, a[i]):
            ok[g] += 2


print(ok.count(1))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう
remove_list = []

kouho = [x for x in set(A) if A.count(x) == 1]
#target = kouho[:]
if kouho != []:
    maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        if buf in kouho:
            remove_list.append(buf)
            #print(A[i]*n)
#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))
print(len(kouho))

Submission status: Time Limit Exceeded

Solution code:
#d
n = int(input())
a = list(map(int, input().split()))
a_l = sorted(a)
count = 0
for i in range(len(a_l)):
    flag = 0
    if a_l.count(a_l[i])>1:
        continue
    for j in range(i):
        if a_l[i] % a_l[j] == 0:
            flag = 1
            break
        if a_l[i] < 2*a_l[j]:
            break
    if flag == 0:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

n = int(input())

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

a.sort()

dp = [True] * n

for i in range(len(a) - 1):
    if dp[i] == True:
        for j in range(1, n - i):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False
        
        if a[i] == a[i + 1]:
            dp[i] = False

print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
        ok[i+1] = 1;
        continue
    times = 2
    while a[i] * times <= a[-1]:
        r = bisect.bisect_left(a, a[i] * times + 1)
        l = bisect.bisect_left(a, a[i] * times)
        if r != l:
            for idx in range(l, r):
                ok[idx] = 1
        times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = sorted(list(map(int,input().split())))
count = N
for i in range(N):
	for j in range(min(N,i+2)):
		if a[i]%a[j] == 0 and i!= j:
			count = count -1
			break
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
old_idx = 0
for i in range(len(data)):
  p = data[i]
  #for j in range(old_idx+1, p):
  #  prime_bool[j] = False
  #old_idx = p
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)

Submission status: Time Limit Exceeded

Solution code:
import sys


def Sieve(N, AList):
    AList.sort(key = lambda x: x[0])

    N_NotDivisible = 0
    index = 0
    while( index < N ):
        if( AList[index][1]==True):
            if(index ==N-1):
                N_NotDivisible += 1
                break
            elif(AList[index][0] != AList[index+1][0]):
                N_NotDivisible += 1
            else:
                AList[index][1]= False
            for i in range(index+1, N, 1):
                if(AList[i][1]==False or AList[i][0] % AList[index][0]==0):
                    AList[i][1]=False

        index += 1
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [ [0, True] for i in range(N) ]
    for i in range(N):
        AList[i][0] = int(AList_str[i])

    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
c = collections.Counter(a)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
old_idx = 0
for i in range(len(data)):
  p = data[i]
  for j in range(old_idx+1, p):
    prime_bool[j] = False
  old_idx = p
  if prime_bool[p]:
    #print(p)
    k = 2
    while k*p <= max(a):
      prime_bool[k*p] = False
      k += 1

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] > 1:
      count += 1
print(prime_bool.count(True) - count)
#print(prime_bool)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,10**6+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,max(A)+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
U = [0]*(10**6+1)
for e in A:
    U[e] += 1
ans = 0
for k in range(1,max(A)+1):
    if U[k] == 1:
        ans += 1
    if U[k] > 0:
        for l in range(2*k,max(A)+1,k):
            if U[l] > 0:
                U[l] += 1
print(ans)

Submission status: Time Limit Exceeded

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

#print(a)
print(a.count(True))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

cnt = Counter(A) 

A = list(set(A))
A.sort()


C = [0]*(10**6+1)
ans = 0

for a in A:
    if cnt[a] == 1 and C[a] == 0:
        ans += 1

    i = 1
    while True:
        if a*i > 10**6:
            break
        C[a*i] = 1
        i += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
 
input()
c = Counter(map(int, input().split()))
r = int(c[1] == 1)
if c[1] == 0:
  for k, v in c.items():
    if v == 1:
      i = 2
      while i * i <= k and (k % i or i not in c and k // i not in c):
        i += 1
      if i * i > k:
        r += 1
print(r)

Submission status: Time Limit Exceeded

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def enum_duplicate_num(L):
        cnt = Counter(L)
        buf = set()
        for num in L:
            if cnt[num] > 1:
                buf.add(num)
        return buf

    def fill_mul_false(num, table):
        for ind in range(num*2, 10**6+1, num):
            table[ind] = False
    
    
    n = ii()
    command = lmi()
    dup_num_set = enum_duplicate_num(command)
    table = [False] * (10 ** 6 + 1)
    for num in command:
        table[num] = True
    for num in command:
        if table[num]:
            fill_mul_false(num, table)
    for num in dup_num_set:
        table[num] = False
    
    print(table.count(True))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(map(int, input().split()))
a = list(filter(lambda x: a.count(x) == 1, a))
if a == []:
    print(0)
else:
    a_st = set(a)
    dp = [True if i in a_st else False for i in range(a[-1] + 1)]
    # print(dp)
    for i in range(1, a[-1] + 1):
        if not dp[i]:
            continue
        for j in range(2, (a[-1] // i + 2)):
            if i * j <= a[-1]:
                dp[i * j] = False
    # print(dp)
    print(dp.count(True))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(hoge) for hoge in input().split()]
A.sort()
dp = [False] * (max(A) + 1)
ans = 0
prev = -1
for a in A:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
        if a != prev:
            ans += 1
        else:
            dp[a] = True
            ans -= 1
    prev = a
print(ans)

Submission status: Time Limit Exceeded

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

ans_list = [[1, 0] for i in range(1000001)]
for i in range(N):
    now = A[i]
    if ans_list[now][1] >= 2:
        continue
    elif ans_list[now][1] == 1:
        ans_list[now][1] = 2
    else:
        ans_list[now][1] = 1
    for j in range(2*now, 1000001, now):
        ans_list[j][0] = 0

count = 0
for i in range(N):
    now = A[i]
    if ans_list[now][0] == 1 and ans_list[now][1] == 1:
        count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

a.sort()

dp = [True] * n

for i in range(len(a) - 1):
    if dp[i] == True:
        for j in range(1, n - i):
            if dp[i + j] == True:
                if a[i + j] % a[i] == 0:
                    dp[i + j] = False
        
        if a[i] == a[i + 1]:
            dp[i] = False

print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
not_divisible = [True] * (max(A)+1)

counter = 0
for i in range(N):
    target = A[i]

    if not_divisible[target]:
        for j in range(target, max(A)+1, target):
            not_divisible[j] = False

        if i < N-1 and A[i] == A[i+1]:
            continue


        counter += 1

print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    w = [0] * (10 ** 6 + 1)
    for a in A:
        w[a] += 1
    for a in A:
        for b in range(a * 2, 10 ** 6 + 1, a):
            w[b] = 0
        if w[a] >= 2:
            w[a] = 0
    print(sum(w))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = sorted(A)#わるほう

kouho = [x for x in set(A) if A.count(x) == 1]
#target = kouho[:]
if kouho != []:
    maxA = max(kouho)

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        if buf in kouho:
            kouho.remove(buf)
            #print(A[i]*n)
#target = kouho[:]

print(len(kouho))