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:
from sys import stdin

def main():

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

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

    a.sort()

    # bにチェックする数を追加していく
    b = []
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        flag = True
        for j in b:
            if a[i] % j == 0:
                flag = False
                break

        if flag:
            b.append(a[i])
            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
aL = sorted(list(map(int, input().split(" "))))
# aL = sorted(list(set(aLP)))

dp = [False for _ in range(1000001)]

ans = 0
for a in aL:
    if dp[a] or aL.count(a) > 1:
        continue
    ans += 1

    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  N = int(input())
  a = np.array([int(x) for x in input().split()])

  M = int(1000001)
  cnt = np.zeros((M))
  for i, x in enumerate(a):
    if(cnt[x] != 0):
      cnt[x] = 2
      continue
    for j in range(x, M, x):
        cnt[j] += 1
  ans = 0
  for i, x in enumerate(a):
    if(cnt[x] == 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()))
check=[0 for i in range(10**6+1)]
for i in a:
    check[i]+=1
    for j in range(i*2, 10**6+1,i):
        check[j]+=2
ans=0
for g in list(set(a)):
    if check[g]==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N = int(input())
a = np.array([int(x) for x in input().split()])
 
M = int(1000001)
cnt = np.zeros((M))
for i, x in enumerate(a):
  if(cnt[x] != 0):
    cnt[x] = 2
    continue
  for j in range(x, M, x):
      cnt[j] += 1
ans = 0
for i, x in enumerate(a):
  if(cnt[x] == 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N = int(input())
a = np.array([int(x) for x in input().split()])
 
M = int(1000001)
cnt = np.zeros((M))
for i in range(N):
  if(cnt[a[i]] != 0):
    cnt[a[i]] = 2
    continue
  for j in range(a[i], M, a[i]):
      cnt[j] += 1
ans = 0
for i in range(N):
  if(cnt[a[i]] == 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
N = int(input())
a = np.array([int(x) for x in input().split()])
 
M = int(1000005)
cnt = np.zeros((M))
for i in range(N):
  if(cnt[a[i]] != 0):
    cnt[a[i]] = 2
    continue
  for j in range(a[i], M, a[i]):
      cnt[j] += 1
ans = 0
for i in range(N):
  if(cnt[a[i]] == 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
check=[0 for i in range(10**6+1)]
for i in range(n):
    diff=a[i]
    check[diff]+=1
    for j in range(diff*2, 10**6+1, diff):
        check[j]+=2
ans=0
for g in a:
    if check[g]==1:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
a = np.array([int(x) for x in input().split()])

M = int(1000000+1)
cnt = np.zeros((M))
for i in range(N):
  if(cnt[a[i]] == 1):
    cnt[a[i]] = 2
    continue
  for j in range(a[i], M, a[i]):
      cnt[j] += 1
ans = 0
for i in range(N):
  if(cnt[a[i]] == 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
a = np.array([int(x) for x in input().split()])

M = int(1000000+1)
cnt = np.zeros((M))
for i, x in enumerate(a):
  if(cnt[x] == 1):
    cnt[x] = 2
    continue
  for j in range(x, M, x):
      cnt[j] += 1
ans = 0
for i, x in enumerate(a):
  if(cnt[x] == 1):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = [int(i) for i in input().split()]
count = 0
for i in a_list:
    flag_list = [i % j for j in a_list]
    if flag_list.count(0) == 1 :
        count += 1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
 
N = int(stdin.readline().strip())
A = [int(x) for x in stdin.readline().strip().split(" ")]

sum_num = 0

for i in range(len(A)):
    tmp = [A[i]] * N
    tmp = [x % y for (x, y) in zip(tmp, A)]
    tmp[i] = 1
    if 0 not in tmp:
        sum_num += 1

print(sum_num)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
 
N = int(stdin.readline().strip())
A = [int(x) for x in stdin.readline().strip().split(" ")]

sum_num = 0

for i in range(len(A)):
    flag = 0
    for j in range(len(A)):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            flag = 1
            break
    if flag == 0:
        sum_num += 1
            

print(sum_num)

Submission status: Time Limit Exceeded

Solution code:
#5
#24 11 8 3 16

N = int(input())
num = list(map(int, input().split()))
divz = [0]*N

num.sort()

count = 0
for i, n in enumerate(num):
    if divz[i] == 0:
        for k in range(i+1, N):
            if divz[k] == 0:
                if num[k] == num[i]:
                    divz[i] = 1
                if num[k] % num[i] == 0:
                    divz[k] = 1
        if divz[i] == 0: count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def main():

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

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

    a.sort()

    # bにチェックする数を追加していく
    b = []
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        flag = True
        for j in b:
            if j * 2 > a[i]:
                break
            if a[i] % j == 0:
                flag = False
                break

        if flag:
            b.append(a[i])
            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for j,a in enumerate(A):
  flag = True
  for i in range(len(A)):
    if i==j:
      pass
    elif a % A[i] == 0:
      flag = False
  if flag:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = int(input())
ar = list(map(int,input().split(" ")))
ar.sort()
br = [i for i in range(a)]
count = 0
ch = 0
for r in br:
    for i in range(r+1,a):
        if ar[i] == ar[r]:
            ch += 1
            if i in br:
                br.remove(i)
        if ar[i] % ar[r] == 0:
            if i in br:
                br.remove(i)
    if ch >= 1:
        ch = 0
        if r in br:
            br.remove(r)
print(len(br))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    dp = [True for i in range(a[-1] + 1)]
    prev = -1
    ans = 0
    for i in a:
        if prev == i:
            dp[i] = False
            continue
        zzz = i * 2
        while zzz <= a[-1]:
            if zzz in a:
                dp[zzz] = False
            zzz += i

        prev = i

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#5
#24 11 8 3 16

N = int(input())
num = list(map(int, input().split()))
divz = [0]*N

num.sort()

count = 0
for i, n in enumerate(num):
    for k in range(i):
            if num[i] % num[k] == 0:
                divz[i] = 1
                break
    if divz[i] == 0 and (((i < N-1) and num[i] != num[i+1]) or (i == N-1)):
        count += 1

print(count)

Submission status: Time Limit Exceeded

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

num = max(l)+1
rcd = [0 for _ in range(num)]

for i in range(1, num):
    for j in l:
        if i % j == 0:
            rcd[i] += 1
            if rcd[i] >= 2:
                break
        else:
            continue

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#5
#24 11 8 3 16

N = int(input())
num = list(map(int, input().split()))
divz = [0]*N

for i, n in enumerate(num):
    for k in range(N):
        if k != i:
            if num[k] % num[i] == 0:
                divz[k] += 1

            if num[i] % num[k] == 0:
                divz[i] += 1

count = 0
for k in range(N):
    if divz[k] == 0:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
S = list(set(A))
S.sort(reverse=True)
ret = 0
for i in range(len(S)):
    A_ = A.copy()
    A_.remove(S[i])
    if S[i] not in A_:
        if i == len(S) - 1:
            ret += 1
        else:
            for j in range(len(S)-1, i, -1):
                if S[i] % S[j] == 0:
                    break
                elif S[j] > S[i] // 2:
                    ret += 1
                    break
                elif j == i + 1:
                    ret += 1
    
    
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    num_tmp = [0]*(A[-1]+1)

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,max(A)+1,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()

Submission status: Time Limit Exceeded

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

a.sort()

ma = max(a)
f = [1] * (ma + 1)

ans = 0

for i in a:
    if f[i]:
        if a.count(i) == 1:
            ans += 1
        for j in range(i, min(ma + i, ma + 1), i):
            f[j] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    num_tmp = [0]*(max(A)+1)

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,max(A)+1,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()

Submission status: Time Limit Exceeded

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

for a in A:
    num_tmp[a] += 1
    if num_tmp[a] == 1:
        for i in range(2*a,max(A)+1,a):
            num_tmp[i] = 2

print(num_tmp.count(1))

Submission status: Time Limit Exceeded

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

for a in A:
    num_tmp[a] += 1
    if num_tmp[a] == 1:
        for i in range(2*a,max(A)+1,a):
            num_tmp[i] = 2

ans = 0
for a in A:
    if num_tmp[a] == 1:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    if is_ans[a] == 0:
        b = 2*a
        while b < ans_len:
            is_ans[b] += 1
            b += a

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    b = 2*a
    while b < ans_len:
        if is_ans[b] == 0:
            is_ans[b] += 1
        b += a

ans = 0
for a in a_list:
    # print(a, a_list.count(a), is_ans[a])
    if a_list.count(a) == 1:
        ans += (is_ans[a] == 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
ans_len = 10**6+10
is_ans = [0]*(ans_len)

for a in a_list:
    b = a
    while b < ans_len:
        # if is_ans[b] == 0:
        is_ans[b] += 1
        b += a

ans = 0
for a in a_list:
    ans += (is_ans[a] == 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#170D
def main():
    import sys, random
    from collections import Counter
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    #print(random.randint(1, 10**6))
    #A = [random.randint(1, 10**6) for _ in range(2*(10**3))]
    B = Counter(A)
    #print(B)
    A = list(set(A))
    A.sort()
    #print(A)
    def era(A):
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[j] % A[i] ==0:
                    A.pop(j)
    
    era(A)
    #print(A)
 
    
    for i in range(len(A)-1, -1, -1):
        if B[A[i]]>=2:
            A.pop(i)
    #print(dp)
    print(len(A))
    
 
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#170D
def main():
    import sys, random
    from collections import Counter
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    #print(random.randint(1, 10**6))
    #A = [random.randint(1, 10**6) for _ in range(2*(10**3))]
    B = Counter(A)
    #print(B)
    A = list(set(A))
    A.sort()
    #print(A)
    def era(A):
        for i in range(len(A)):
            for j in range(len(A)-1, i, -1):
                if A[j] % A[i] ==0:
                    A.pop(j)
    
    era(A)
    #print(A)

    
    for i in range(len(A)-1, -1, -1):
        if B[A[i]]>=2:
            A.pop(i)
    #print(dp)
    print(len(A))
    


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1):
        tmp = num * i
        if dp[tmp]: dp[tmp] = 0

# カウンター
cnt = col.Counter(a)

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

# カウンター
cnt = col.Counter(a)

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections as col

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

# カウンター
cnt = [0 for i in range(amax+1)]
for num in a:
    cnt[num] += 1

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for num in a:
    if dp[num] and cnt[num]==1: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

# カウンター
cnt = [0 for i in range(amax+1)]
for num in a:
    cnt[num] += 1

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for num in a:
    if dp[num] and cnt[num]==1: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

cnt = col.Counter(a)

ans = 0
for num in a:
    if dp[num] and cnt[num]==1: ans += 1

print(ans)

Submission status: Time Limit Exceeded

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



f=[True]*(max(A)+1)
chk=[0]*(max(A)+1)

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

for a in A:
    cnt=2
    while a*cnt<=max(A):
        f[a*cnt]=False
        cnt+=1
ans=0
for a in A:
    if f[a]==True and chk[a]==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
from operator import add
import sys
def calc_double(n,i):
    return float(n/i)

listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N=listA[0]
lis_0=[0]*N[0]
lis=listA[1]
for idx1,i in enumerate(lis):
    lis_=[]
    for val in lis:
      lis_.append(calc_double(val,i))
    for idx,num in enumerate(lis_):
        if idx!=idx1:
            if num.is_integer(): lis_[idx]=1
            else: lis_[idx]=0
        else:lis_[idx]=0
    lis_0 = list(map(add, lis_, lis_0))
        
print(lis_0.count(0))

Submission status: Time Limit Exceeded

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

c = 0

for i in range(n):
	for j in range(n):
		if i != j:
			if a[i]%a[j] == 0:
				c+=1
				break


print(n-c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from operator import add
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N=listA[0]
lis_0=[0]*N[0]
lis=listA[1]
arr=np.array(lis)
for idx1,i in enumerate(lis):
    arr_=arr/i
    lis_=arr_.tolist()
    
    for idx,num in enumerate(lis_):
        if idx!=idx1:
            if num.is_integer(): lis_[idx]=1
            else: lis_[idx]=0
        else:lis_[idx]=0
    lis_0 = list(map(add, lis_, lis_0))
        
print(lis_0.count(0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from operator import add
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;
N=listA[0]
lis_0=[0]*N[0]
lis=listA[1]
for idx1,i in enumerate(lis):
    arr=np.array(lis)
    arr_=arr/i
    lis_=arr_.tolist()
    
    for idx,num in enumerate(lis_):
        if idx!=idx1:
            if num.is_integer(): lis_[idx]=1
            else: lis_[idx]=0
        else:lis_[idx]=0
    lis_0 = list(map(add, lis_, lis_0))
        
print(lis_0.count(0))

Submission status: Time Limit Exceeded

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
for i in range(0,n):
  flag=0
  for j in range(0,n):
    if i==j:
      pass
    else:
      if lst[i]%lst[j]==0:
        flag=1
        j=n
        break

  if flag==0:
    c = c+1
        
print(c)

Submission status: Time Limit Exceeded

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
for i in range(0,n):
  flag=0
  for j in range(0,n):
    if i==j:
      pass
    else:
      if lst[i]%lst[j]==0:
        flag=1
        break
      else:
        pass
  if flag==0:
    c = c+1
        
print(c)

Submission status: Time Limit Exceeded

Solution code:
lst=[]
c=0
flag=0
n = int(input())
str = input()
lst = str.split(' ')
for i in range(0,n):
  lst[i] = int(lst[i])
for i in range(0,n):
  flag=0
  for j in range(0,n):
    if i==j:
      pass
    else:
      if lst[i]%lst[j]==0:
        flag=1
      else:
        pass
  if flag==0:
    c = c+1
        
print(c)

Submission status: Time Limit Exceeded

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

flag = [True] * N

for i in range(len(A_array)):
    target_array = [val % A_array[i] for val in A_array]
    for index in range(len(target_array)):
      if i == index or flag[index] == False:
        continue
      if target_array[index] == 0:
        flag[index] = False

print(flag.count(True))

Submission status: Time Limit Exceeded

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

flag = [True] * N

for i, ai in enumerate(zip(A_array, flag)):
    target_array = [val % ai[0] for val in A_array]
    for index, val in enumerate(target_array):
      if i == index or flag[index] == False:
        continue
      if val == 0:
        flag[index] = False

print(flag.count(True))

Submission status: Time Limit Exceeded

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

flag = [True] * N

for i, ai in enumerate(A_array):
    target_array = [val % ai for val in A_array]
    for index, val in enumerate(target_array):
      if i == index:
        continue
      if val == 0:
        flag[index] = False
print(flag.count(True))

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))
def prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:return False
    return True

n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    #l.sort()
    c=Counter(l)
    ans=0
    for k,v in c.items():
        if v>1:continue
        else:
            f=True
            ys=[]
            for i in range(2, int(math.sqrt(k)) + 1):
                if k % i == 0 and (i in c or k//i in c):
                    f=False
                    break
            if f==True:ans+=1

    print(ans)

Submission status: Time Limit Exceeded

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

ans = N

for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      if A[i]%A[j] == 0:
        ans -= 1
        break
        
print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 

n = int(input())
a = sorted(map(int, input().split()))
adict = Counter(a)

for i in a:
    if i in adict:
        tmp = set([])
        for j in list(adict):
            if j % i == 0 and j != i:
                del adict[j]
print(list(adict.values()).count(1))

Submission status: Time Limit Exceeded

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

count = 0
while count<len(c):
  d = c[count]
  if d in c[count+1:len(c)]:
    s = count
    while d in c:
      c.pop(s)
    continue
  f = 1
  while f<len(c):
    if f == count:
      f+=1
      continue
    if c[f]%c[count]==0:
      c.pop(f)
      continue
    f+=1
  count+=1
print(len(c))

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a=[i for i in a if a.count(i)==1]
a.sort()
b=0
while a:
    b+=1
    a=[i for i in a[1:] if i%a[0]!=0]
print(b)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*(max(a)+1)
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,max(a)+1,i):
        b[j]+=1
ans=0
for i in a:
    ans+=(1 if b[i]==1 else 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*(max(a)+1)
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,max(a)+1,i):
        b[j]+=1
ans=0
for i in a:
    ans+=(1 if b[i]==1 else 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a=[i for i in a if a.count(i)==1]
a.sort()
b=[]
while a:
    b.append(a[0])
    a=[i for i in a if i%a[0]!=0]
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
b=[0]*(max(a)+1)
a.sort()
for i in a:
    if b[i]!=0:
        b[i]+=1
        continue
    else:
        b[i]+=1
    for j in range(2*i,max(a)+1,i):
        b[j]+=1
ans=0
for i in a:
    ans+=(1 if b[i]==1 else 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,Counter
import bisect
n,*a = map(int,open(0).read().split())
c = Counter(a)
c = sorted(c.items())
a = deque(c)
p_set = set()
ans,r = 0,0
while a:
    f,count = a.popleft()
    z = []
    for u in range(len(a)):
        if a[u][0]%f != 0:
            z.append(a[u])
    a = deque(z[:])
    if count != 1:
        r += 1
    p_set.add(f)
print(len(p_set)-r)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,Counter
n,*a = map(int,open(0).read().split())
c = Counter(a)
c = sorted(c.items())
a = deque(c)
p_set = set()
ans = 0
while a:
    f,count = a.popleft()
    if count == 1:
        for ff in p_set:
            if f%ff == 0: 
                break
        else:
            ans += 1
    p_set.add(f)
print(ans)

Submission status: Time Limit Exceeded

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

MAX = 1000001
dp = [True for _ in range(MAX)]
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = Counter(a)
ans = 0
for v in a:
   if cnt[v] <= 1 and dp[v]:
      ans += 1
   m = v
   while m < MAX:
      dp[m] = False
      m += v
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(input().split())
a = [int(i) for i in a]
l=[True]*n
sort = sorted(a)


for i in range(n):
  #print(sort[i], l)
  if l[i:] == [False]*len(sort[i:]):
    break
  if l[i] == False:
    continue
  
  for ii in range (i+1,n):
    #print(sort[ii])
    if sort[ii] == sort[i]:
      #print("重複")
      l[i] = False
      l[ii] = False
      continue
    if sort[ii] % sort[i] == 0:
      #print("割り切れる")
      l[ii] = False


print(len([x for x in l if x]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
M=10**6+1
cnt=[True]*M
dep=[x for x in set(A) if A.count(x) >= 2]

for i in A:
    if cnt[i]==False:
        continue
    for j in range(2*i,M,i):
        #print(i,M,j)
        cnt[j]=False
ans=0
for i in set(A):
    if i in dep:
      continue
    if cnt[i]:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A_list=list(map(int,input().split()))
A_list.sort()
ans=len(A_list)
for i in range(len(A_list)):
    if i< len(A_list)-1:
        if A_list[i]==A_list[i+1]:
            ans-=1
        else :
            for j in range(i):
                if A_list[i]%A_list[j]==0:
                    ans-=1
                    break
    else :
        for j in range(i):
            if A_list[i]%A_list[j]==0:
                ans-=1
                break
print(ans)