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=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        j=1
        while 1:
            j+=1
            if i*j>max:
                break
            dp[i*j]=True
for i in a:
    if a.count(i)>1:
        dp[i]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
a=sorted(list(map(int,input().split())))
 
c=[1 for i in range(10**6+1)]
d = Counter(a)
s = list(set(a))
count = 0
for x in s:
  t = x * 2
  while t <= 10 ** 6:
    c[t] = 0
    t += x

for x in a:
  if d[x] == 1 and c[x] == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=set(A)
A.sort()
ans=[1]*max(A)
for i in range(len(A)):
  if ans[A[i]-1]!=0:
    if i>0 and A[i]==A[i-1]:
      ans[A[i]-1]=0
    for j in range(A[i]*2,max(A)+1,A[i]):
      ans[j-1]=0
k=0
for i in A:
  if ans[i-1]==1:
    k+=1
print(k)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a_s = set(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        for j in range(i, max(a)+1, i):
            s.add(j)
        ans += 1

print(ans - len(same_s))

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
a.sort()

div = [True] * (max(a) + 1)
used = defaultdict(int)
for n in a:
    if used[n] > 0:
        div[n] = False
        continue
    used[n] += 1
    if not div[n]:
        continue
    i = 2
    while n * i <= max(a):
        div[n * i] = False
        i += 1

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

print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

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


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    

    n = int(lines[0])
    a = [int(e) for e in lines[1].split(' ')]

    return (n, a)


def solve(n, a):

    if n == 1:
        return 1
    
    count_dict = dict()
    for i in range(n):
        cnt = count_dict.get(a[i], 0)
        cnt = cnt + 1
        count_dict[a[i]] = cnt
    
    b = list(count_dict.keys())
    b.sort()

    tmp = dict([(k, True) for k in b])
    for i in range(len(b)):
        for j in range(i+1, len(b)):
            if b[j] % b[i] == 0:
                tmp[b[j]] = False
    tmp2 = dict([(k, v) for k, v in tmp.items() if v])
    result = tmp2.keys()

    result_2 = []    
    removed = set([k for k, v in count_dict.items() if v > 1])
    for r in result:
        if r in removed:
            pass
        else:
            result_2.append(r)
    
    len_result = len(result_2)

    return len_result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':
  
    main()

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(a[i], max(a)+1, a[i]):
            if g != a[i]:
                ok[g] += 2


print(ok.count(1))

Submission status: Time Limit Exceeded

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

dp = [True] * (A[-1] + 1)
for a in A:
    n = 2
    while n * a <= A[-1]:
        dp[n * a] = False
        n += 1

score = 0
for a in A:
    score += dp[a] * (A.count(a) == 1)
    
print(score)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
for i in range(N-1):
    for j in range(i+1,N):
        if A[j] %A[i] ==0:
            count.add(A[j])
ans =len(A_set - count)
print(ans)

Submission status: Time Limit Exceeded

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

B = [0]*(max(A)+1)

for i in A:
  B[i]+=1
  if B[i] == 1:
    for j in range(i*2, max(A)+1, i):
      B[j]+=100
print(B.count(1))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
A.sort()
ans = 0
while A:
    tmp = A[0]
    if len(A) > 1:
        if tmp not in A[1:]:
            ans += 1
        A = [a for a in A[1:] if a % tmp != 0]
    else:
        ans += 1
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)
d = defaultdict(int)
for i in a:
    d[i] += 1

u = []
for i, v in d.items():
    if v == 1:
        u.append(i)

for i in a:
    for j in range(i * 2, 10 ** 6 + 1, i):
        anstable[j] += 1

cnt = 0
for i in u:
    if anstable[i] == 0:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import bisect

def sortedexist(list,x):
    if bisect.bisect_left == bisect.bisect_right:
        return False
    else:
        return True

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

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
a = sorted(list(map(int, input().split())))
memo = ['Yes'] * n
ans = 0
max = a[-1]

for i, a_i in enumerate(a):
    if memo[i] == 'No':
        continue
    for j in range(i+1, n):
        if a[j] % a_i == 0:
            memo[j] = 'No'
    if i != n-1 and a_i == a[i+1]:
        continue
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
a.sort()
max=a[-1]
dp=[False for _ in range(max+1)]

for i in a:
    if dp[i]==False:
        for j in range(2,max+1):
            if i*j>max:
                break
            dp[i*j]=True
for i in a:
    if a.count(i)>1:
        dp[i]=True
cnt=0
for i in a:
    if dp[i]==False:
        cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
cola = collections.Counter(a)
mult = [True] * (10**6+1)
seta = set(a)

for s in seta:
  tmp = s * 2
  while tmp <= 10 ** 6:
    mult[tmp] = False
    tmp += s
  
ans = 0
for s in seta:
  if cola[s] == 1 and mult[s] == True:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for num in a:
    if cands[num-1] >= 2:
        continue
    for i in range(num, max(a)+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==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()))
dp = [1] * (max(a)+9)
for num in a:
    for i in range(num*2, max(a) + 9, num):
        dp[i] = 0
ans = 0
count = Counter(a)
for num in a:
    if count[num] == 1:
        ans += dp[num]
print(ans)

Submission status: Time Limit Exceeded

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


A.sort()
n = len(A)
B = [-1] * n

for i in range(n):
    if B[i] == 0:
        continue
    for j in range(n-i-1):
        j += 1
        if B[i+j] == 0:
            continue
        if A[i] == A[i+j]:
            B[i] = 0
            B[i+j] = 0
        if A[i+j] % A[i] == 0:
            B[i+j] = 0

print(B.count(-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A =sorted(A)
C = Counter(A)
S=set(A)

use=[True]*N
ans=0
for i in range(N):
    if use[i]:
        if C[A[i]]==1:
            ans+=1
        for j in range(i,N):
            if A[j]%A[i]==0:
                use[j]=False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c = Counter(A)
dp = [True] * (10**6+1)

for k, v in c.items():
  t = k*2
  while t <= 10**6:
    dp[t] = False
    t += k
    
ans = 0
for a in A:
  if c[a] == 1 and dp[a]:
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
cola = collections.Counter(a)
mult = [1] * (10**6+1)
seta = set(a)

for s in seta:
  tmp = s * 2
  while tmp <= 10 ** 6:
    mult[tmp] = 0
    tmp += s
  
ans = 0
for s in seta:
  if cola[s] == 1 and mult[s] == 1:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import bisect

def sortedexist(list,x):
    if bisect.bisect_left == bisect.bisect_right:
        return False
    else:
        return True

N = int(input())
A = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
dp = [False] * (max(A) + 1)
S = list(C.keys())
S.sort()
for a in S:
    if dp[a] == False:
        for j in range(2,1 + (max(A) // a)):
            dp[a*j] = True
    if C[a] > 1:
        dp[a] = True
print(sum([dp[a] == False for a in A ]))

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]
    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:
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = sorted(list(set(A)))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)

Submission status: Time Limit Exceeded

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

if N == 1:
    print(1)
    exit()
    
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > 10**6:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i in range(N)])
#A = list(set(A))
A = sorted(A)#わるほう

kouho = [x for x in set(A) if A.count(x) == 1]
target = list(kouho.copy())
            
for i in range(len(A)):
    if target == []:
        break
    maxN = int(max(target)/A[i])
    for n in range(2,maxN+1):
        if A[i]*n in kouho:
            kouho.remove(A[i]*n)
            #print(A[i]*n)
target = list(kouho.copy())
        
print(len(target))

Submission status: Time Limit Exceeded

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

ans = 0
for num in a:
    for i in range(num, max(a)+1, num):
        cands[i-1] += 1
        
for num in a:
    if cands[num-1]==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n=int(input().rstrip())
    a=[int(i) for i in input().split()]
    maxn=10**6+1
    dp=[True]*(maxn)
    cnt=[0]*(maxn)
    ans=0
    for i in a:
        if dp[i]:
            cnt[i]+=1
            for j in range(i*2,maxn,i):
                dp[j]=False

    for i in a:
        if dp[i] and cnt[i]==1:
            #print(i)
            ans+=1
    print(ans)

if __name__=="__main__":main()

Submission status: Time Limit Exceeded

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

if N == 1:
    print(1)
    exit()
    
A = sorted(A)
check_list = [0] * (10**6 + 1)

cnt = 0
for i in range(len(A)):
    tmp = A[i]
    while True:
        if tmp > 10**6:
            break
        check_list[tmp] += 1
        tmp += A[i]

for a in A:
    if check_list[a] == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
work=[]
while l:
    if len(l)==1 or l[1]!=l[0]:work.append(l[0])
    l=[x for x in l[1:] if x%l[0]!=0]
print(len(work))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c = Counter(A)
dp = [True] * (10**6+1)

for k, _ in c.items():
  t = k*2
  while t <= 10**6:
    dp[t] = False
    t += k
    
ans = 0
for a in A:
  if c[a] == 1 and dp[a]:
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
A_list = list(map(int, input().split()))
ans_list =np.ones(N)
A_list = np.array(A_list)

for i in range(N-1):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
            if (A_list[j] %  A_list[i] == 0):
                ans_list[j] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[j] = 0
print(int(np.sum(ans_list)))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    #if count[a] > 1:
    #  continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  #print(count[:100])
  return ans
  
  
  
print(main(np.array(A, np.int32)))

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = [int(i) for i in input().split()]
cola = collections.Counter(a)
mult = [1] * (10**6+1)

for s in set(a):
  tmp = s * 2
  while tmp <= 10 ** 6:
    mult[tmp] = 0
    tmp += s
  
ans = 0
for s in set(a):
  if cola[s] == 1 and mult[s] == 1:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def d170(n,a):
    count=0
    sa=sorted(list(set(a)))
    t=set([x for x in set(a) if a.count(x)>1])
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(len(sa)) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        return len(set(sa)-t)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))

Submission status: Time Limit Exceeded

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

ans=0
dp=[True]*(max(A)+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i==N-1:
        ans+=1
    elif i<N-1 and A[i+1]!=A[i]:
        ans+=1
    for j in range(1,max(A)//A[i]+1):
        dp[A[i]*j]=False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=list(map(int,input().split()))
    SUGOI=[False]*(10**6+1)
    for a in A:
        for j in range(2*a,10**6+1,a):
            SUGOI[j]=True
    cnt=0
    for a in A:
        if A.count(a)==1 and SUGOI[a]==False:
            cnt+=1
    print(cnt)
    
    
if __name__=="__main__":
    main()

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()
ans=0
for x in a:
    if dp[x]=="False":
        ans+=1
        continue
    if x in seen:
        dp[x]="False"
        ans+=2
        continue
    i=2
    seen.add(x)
    while x*i<=max(a):
        dp[x*i]="False"
        i+=1
print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter
n = int(input())
A = np.array(list(map(int, input().split())))
C = Counter(A)
A = np.sort(A)
c = 0
while len(A) > 0:
    ai = A[0]
    AL = A[1:]
    if C[ai] == 1:
        c += 1
    mask = AL % ai != 0
    A = AL[mask]
print(c)

Submission status: Time Limit Exceeded

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

counter = [0 for _ in range(n)]
for num in a:
    div = np.array(a) % num
    for j, index in enumerate(div):
        if index == 0:
            counter[j] += 1
print(counter.count(1))

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

A.sort()

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

ans = len(list(filter(lambda x: x == 1, dp)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import bisect

def sortedexist(list,x):
    if bisect.bisect_left == bisect.bisect_right:
        return False
    else:
        return True

N = int(input())
A = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
done = dict()
for a in A:
    done[a] = False
dp = [False] * (max(A) + 1)

for a in A:
    if done[a]:
        dp[a] = True
    elif dp[a] == False:
        for j in range(2,1 + (max(A) // a)):

            dp[a*j] = True
        done[a] = True
print(sum([dp[a] == False for a in A ]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
# a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(1)
    exit()

for i in a:
    if i in dic:
        dic[i] += 1
        continue
    dic[i] = 0
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and dic[i] == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  not_divisible_list = [True]*N
  A = [int(x) for x in input().split(" ")]
  A.sort()

  for i, a_t in enumerate(A):
    if not_divisible_list[i] == False:
      continue
    for j, a in enumerate(A[i+1:]):
      if a_t==a:
        not_divisible_list[i] = False
      if a%a_t==0:
        not_divisible_list[i+1+j] = False
  print(sum(not_divisible_list))

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

count = 0
ans = np.array([np.array(a) % a[0]])
for i in range(1, n):
    ans = np.insert(ans, i, np.array(a) % a[i], axis=0)

count = 0
for i in range(n):
    if np.count_nonzero(ans.T[i] == 0) == 1:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import math

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

count = 0
flag = 0
for a in A:
    B = A.copy()
    B.remove(a)
    for b in B:
        if a % b == 0 and a >= b:
            break
    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
good_i = 0
bad_vals = []

for i in range(N):
    if A[i] in bad_vals:
        continue
    for j in range(N):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            bad_vals.append(A[i])
            break
    else:
        good_i += 1

print(good_i)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = list(map(int,input().split()))
U = [0]*(max(A)+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())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
    res = 0
    for j in range(n):
        if i!=j:
            if a[i]%a[j]==0:
                res += 1
    if res==0:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#D
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
count = 0
K = sorted(A,reverse = True)
for p in range(N):
    if len(A) == 0:
        break
    else:
        pass
    i = A[0]
    for j in A[1:]:
        if i%j == 0:
            count = count-1
            break
        else:
            pass
    A = [x for x in A if x != i]
    count = count+1
print(count)

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[:0:-1]

N = int(input())
As = list(map(int, input().split()))
st = set(As)
Fs = [0]*N
 
As.sort()
if N == 1:
  print(1)
  exit()
else:
  rlt = 1
  
for i in range(1,N):
  if As[i] == As[i-1]:
    Fs[i] = 1
    if Fs[i-1] == 0:
      rlt -= 1
    continue
  ls =  make_divisors(As[i])
  for l in ls:
    flag = 0
    if l in st:
      Fs[i] = 1
      flag = 1
      break
  if flag == 0:
    rlt += 1
    
print(rlt)

Submission status: Time Limit Exceeded

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

a_sorted = sorted(a)
divisible_list = [True] * n

for i in range(n-1):
    if not divisible_list[i]:
        continue
    for j in range(i+1, n):
        if a_sorted[j] == a_sorted[i]:
            divisible_list[i] = False
            tmp = j
            while True:
                if tmp < n and a_sorted[tmp] == a_sorted[i]:
                    divisible_list[j] = False
                    tmp += 1
                else:
                    break

        elif a_sorted[j] % a_sorted[i] == 0:
            divisible_list[j] = False
print(sum(divisible_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True for _ in range(10**6 + 5)]
dic = {}
if len(a) == 1:
    print(1)
    exit()

for i in a:
    if i in dic:
        dic[i] += 1
        continue
    dic[i] = 0
    now = 2 * i
    while (10**6 + 3 > now):
        check[now] = False
        now += i

ans = 0
for i in a:
    if check[i] and dic[i] == 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

#K = int(input())
#S = input()

##一次元配列の初期化
#a=[0]*5
#[i for i in range(100) if i%2==1] #奇数のみ
##二次元配列の初期化
#mod = np.array([[-1 for i in range(N)] for i in range(N)])
#A = list(set(A))
A = sorted(A)#わるほう

kouho = list(A.copy())#わられるほう
target = sorted(list(set(A)))

kouho = [x for x in set(A) if A.count(x) == 1]
target = [x for x in set(A) if A.count(x) == 1]
            
for i in range(len(A)):
    if target == []:
        break
    maxN = int(max(target)/A[i])
    for n in range(2,maxN+1):
        if A[i]*n in kouho:
            kouho.remove(A[i]*n)
            #print(A[i]*n)
    target = list(kouho.copy())
        
print(len(target))

Submission status: Time Limit Exceeded

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
aa=[]

while True:
    aa.append(a[0])
    a2=[]
    for i in range(1,len(a)):
        if a[i]%a[0]!=0:
            a2.append(a[i])
#    a=a2.copy()
    if len(a2)==0:
        break

    aa.append(a2[0])
    a=[]
    for i in range(1,len(a2)):
        if a2[i]%a2[0]!=0:
            a.append(a2[i])
#    a=a2.copy()
    if len(a)==0:
        break

aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

Submission status: Time Limit Exceeded

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

    div_list = []
    a.sort()

    for i in a :
        if a.count(i) >= 2 :
            a = [x for x in a if x != i]

    for i in a :
        if(len(a)) == 0 :
            print(0)
            return None

        div_list.append(i)

        times = 1
        while i*times <= a[-1] :
            if i*times in a and i*times != i:
                a.remove(i*times)

            times += 1

    print(len(div_list))



if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-06-14 21:50:10 +0900
# LastModified: 2020-06-14 23:05:46 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    ans = [1]*n
    for i in range(n):
#        print(ans)
        if ans[i]==0:
            continue
        for j in range(n):
            if i==j:
                continue
            if a[i]==a[j]:
                ans[i]=0
            if a[j]%a[i]==0:
                ans[j]=0
            
    print(sum(ans))



if __name__ == "__main__":
    main()

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:
        if k % i == 0 and  (i in c or k // i in c):
          break
        i += 1
      else:
        r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = sorted(LI())
ans = 0
cnt = Counter(A)
B = [0] * (10 ** 6 + 1)
for a in A:
    if B[a] == 0 and cnt[a] == 1:
        ans += 1
    for i in range(a * 2, 10 ** 6 + 1, a):
        B[i] = 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
i = 0
while a:
    if a.count(a[0]) == 1:
        i+=1
    a = list(filter(lambda x: x%a[0] >0,a))
print(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = [int(x) for x in input().split()] # スペース区切り入力
  count = 0
  check = [0] * N
  
  for i in range(N):
    for j in range(N):
      # print(j)
      if j == i:
        check[j] = 1
      else:
        check[j] = A[i] % A[j]
    if 0 in check:
      continue
    else:
      count += 1

  print(count)
          

if __name__ == '__main__':
  main()