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 numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

nums = [0]*(maxA+2)
A.sort()
sA = list(set(A))
cnt = 0 
ans = defaultdict(int)
for a in sA:
    # print('nums', nums)
    new = False
    if nums[a]==0:
        # print(a)
        cnt += 1
        ans[a] += 1
        new = True
    mlt = a
    nums[a] += 1
    while new and a + mlt < maxA+2:
        a += mlt
        # print(' a:', a)
        nums[a] += 1

for an in ans.keys():
    if A.count(an)>1:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

nums = [0]*(maxA+2)
A.sort()
cnt = 0 
ans = defaultdict(int)
for a in A:
    # print('nums', nums)
    new = False
    if nums[a]==0:
        # print(a)
        cnt += 1
        ans[a] += 1
        new = True
    mlt = a
    nums[a] += 1
    while new and a + mlt < maxA+2:
        a += mlt
        # print(' a:', a)
        nums[a] += 1

for an in ans.keys():
    if A.count(an)>1:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

nums = [0]*(maxA+2)
A.sort()
cnt = 0 
ans = []
for a in A:
    # print('nums', nums)
    if nums[a]==0:
        # print(a)
        cnt += 1
        ans.append(a)
    mlt = a
    nums[a] += 1
    while a + mlt < maxA+2:
        a += mlt
        # print(' a:', a)
        nums[a] += 1

for an in ans:
    if A.count(an)>1:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

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

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

A.sort()
Sum = 0

for i in range(N):

    if DP[A[i]] == 0:
        for j in range(1,10**6):
            if A[i]*j <= 10**6:
                DP[A[i]*j] = 1
            else:
                break
                
        if A.count(A[i]) == 1:
            Sum += 1

print(Sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    x = 0
    for b in A:
        if a%b == 0:
            x += 1
            if x == 2:
                break
    if x == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    x = 0
    for b in A:
        if a%b == 0:
            x += 1
    if x == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

sum=0
while A:
  if len(A)==1 or A[0]!=A[1]:
    sum+=1
  B=A.copy()
  for j in range(len(A)):
    if A[j]%A[0]==0:
      B.remove(A[j])
  A=B
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int,input().split(" "))))
ans = 0
dp = [True]*max(A)
for i in range(N-1):
  if dp[A[i]-1] == True:
    for j in range(1,max(A)//A[i]+1):
      dp[j*A[i]-1] = False
    if A[i] != A[i+1]:
      ans +=1
if dp[-1]:
  ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = 0
dp = [True]*max(A)
A.sort()
for i in range(N):
  if dp[A[i]-1] == True:
    if i > 0:
      if A[i] == A[i-1]:
        dp[A[i]-1] = False
        ans -= 1
        continue
      
    for j in range(2,max(A)//A[i]+1):
      dp[j*A[i]-1] = False
    ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = 0
dp = [True]*max(A)
A.sort()
for i in range(N):
  if dp[A[i]-1]:
    if i > 1:
      if A[i] == A[i-1]:
        dp[A[i]-1] = False
    for j in range(2,max(A)//A[i]+1):
      dp[j*A[i]-1] = False 

for i in A:
  if dp[i-1] == True:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = 0
dp = [True]*max(A)
A.sort()
for i in range(N):
  if dp[A[i]-1] == False:
    continue
  if i > 0:
    if A[i-1] == A[i]:
      dp[A[i]-1] = False
      continue
  for j in range(2,max(A)//A[i]+1):
    dp[j*A[i]-1] = False

for i in A:
  if dp[i-1] == True:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = 0
dp = [True]*max(A)
A.sort()
for i in range(N):
  if dp[A[i]-1] == False:
    continue
  if i > 0:
    if A[i-1] == A[i]:
      dp[A[i]-1] = False
  for j in range(2,max(A)//A[i]+1):
    dp[j*A[i]-1] = False

for i in A:
  if dp[i-1] == True:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split(" ")))
ans = 0
dp = [True]*max(A)
A.sort()
for i in range(N):
  for j in range(2,max(A)//A[i]+1):
    dp[j*A[i]-1] = False
  if i > 0:
    if A[i-1] == A[i]:
      dp[A[i]-1] = False
for i in A:
  if dp[i-1] == True:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import heapq
import math
import random
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500005)
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
rs = lambda: input().rstrip()

n = ri()
a = rl()
N = 1000000
f = [0] * (N + 10)
for v in a:
    f[v] += 1
for i in range(N, 0, -1):
    if f[i] == 0:
        continue
    j = i * 2
    while j <= N:
        f[j] += f[i]
        j += i
cnt = sum(f[i] == 1 for i in a)
print(cnt)

Submission status: Time Limit Exceeded

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

A.sort()
A.append([0])
ans = 0
for i in range(N):
    if A[i] != A[i + 1]:
        flag = True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a= list(map(int,input().split()))
#a = list(set(a))
a.sort
ind = [1] * len(a)

for i in range(len(a)):
  for j in range(len(a))[::-1]:
    if (i != j) & (ind[i] != 0) & (ind[j] != 0) & (a[j]%a[i] == 0):
      if a[i] == a[j]:
        ind[i] = 0
      ind[j] = 0

print(sum(ind))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def readline_from_stdin() -> str:
    return stdin.readline().rstrip



def gcd(a :int, b :int ) -> int:
    r = a % b
    while r > 0:
        a = b
        b = r
        r = a % b
    return b

if __name__ == '__main__':
    pass
    N = int(input())
    A = [int(i) for i in input().split()]

    c = 0
    for idx, iv in enumerate(A):
        cc = 0
        # for j in range(idx+1, N):
            # jv = A[j]
        for jdx, jv in enumerate(A):
            if idx == jdx:
                continue
            if iv % jv == 0:
                cc += 1
                break
        if cc == 0:
            c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

c=Counter(a)

def eratosthenes(lim):
  is_p=[1]*lim
  is_p[0]=1
  is_p[1]=1

  for i in a:
    if is_p[i]:
      for j in range(i*2,lim,i):
        is_p[j]=0

  return is_p

lim=10**6+5
is_p=eratosthenes(lim)

cnt=0
for i in a:
  if is_p[i]==1 and c[i]==1:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = [int(x) for x in input().split()]
a = []
c = 0
for i in range(n):
    t = 0
    for j in range(n):
        if i != j:
            if l[i] % l[j] == 0:
                break
            else:
                t += 1
    else:
        if t == n-1:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def resolve():
    readline=sys.stdin.readline
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    tb=[False]*(10**6 + 10)
    ans=0
    for i in range(n):
        flg=0
        x=arr[i]
        if tb[x]==False:
            flg=1
        if i < (n-1):
            if arr[i]==arr[i+1]:
                flg=0
        ans+=flg
        for j in range(x,10**6+5,x):
            tb[j]=True
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #a,b,c=map(int, readline().rstrip().split())
    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    tb=[0]*(10**6 + 10)
    ans=0
    for i in range(n):
        x=arr[i]
        for j in range(x,10**6+5,x):
            tb[j]+=1
    for i in range(n):
        x=arr[i]
        if tb[x]==1:
            ans+=1
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

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

AA = [0]*1000000

for i in range(N):
    ma = 1000000//A[i]
    for j in range(1,ma+1):
        AA[j*A[i]-1]+=1

ans = 0

for i in range(N):
    if AA[A[i]-1] == 1:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

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

AA = [0]*1000000

for i in range(N):
    j = 1
    while (j*A[i]<=1000000):
        AA[j*A[i]-1] += 1
        j += 1

ans = 0

for i in range(N):
    if AA[A[i]-1] == 1:
        ans += 1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC170

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

a.sort()
maxa = max(a)
dp = [True for _ in range(maxa+1)]

ans = 0
for ai in a:
    if dp[ai]:
        for i in range(0, maxa+1, ai):
            dp[i] = False
        if a.count(ai) == 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()))

dp = ['True'] * 1000000
seen = set()

A.sort()

for i in range(len(A)):
	if i in seen:
		continue
	else:
		seen.add(i)
	x = A[i]
	if x in A:
		for y in range(x + x, len(dp), x):
			dp[y] = False

c = defaultdict(int)
for elem in A:
	c[elem] += 1

A = [x for x in A if c[x] == 1]

ans = 0
for elem in A:
	if dp[elem]:
		ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
N = int(input())
A = defaultdict(int)
for i in input().split():
    A[int(i)] += 1
D = set()
S = []
for key in A.keys():
    if A[key] >= 2:
        D.add(key)
    S.append(key)
S = sorted(S)
Q = deque(S)
ans = 0
while Q:
    q = Q.popleft()
    if q not in D:
        ans += 1
    R = []
    while Q:
        M = Q.popleft()
        if M%q != 0:
            R.append(M)
    Q = deque(R)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
cnt_A = defaultdict(int)
for a in A:
    cnt_A[a] += 1
NG_list = []
for key in cnt_A.keys():
    if cnt_A[key] >= 2:
        NG_list.append(key)
NG_list = set(NG_list)
sort_A = sorted(A)
from collections import deque
Q = deque(sort_A)
ans = 0
while Q:
    M = Q.popleft()
    if M not in NG_list:
        ans += 1
    R = deque([])
    while Q:
        q = Q.popleft()
        if q%M != 0:
            R.append(q)
    Q = R
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = input()
alist = list(map(int,input().split()))
s = 0
i = 0
for x in alist:
  num = 0
  i += 1
  j = 0
  for y in alist:
    j += 1
    if i != j:
      if x % y == 0:
        break
      else:
        num += 1
  if num == int(N)-1:
    s += 1
print(s)

Submission status: Time Limit Exceeded

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

ok = [1 for i in range(len(A))]

for i in range(len(A)-1):
  for j in range(i+1, len(A)):
    if ok[j] == 0:
      continue
    if A[i] == A[j]:
      ok[i] = ok[j] = 0
      continue
    if A[j] % A[i] == 0:
      ok[j] = 0

print(sum(ok))

Submission status: Time Limit Exceeded

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

ok = [1 for i in range(len(A))]

for i in range(len(A)-1):
  for j in range(i+1, len(A)):
    if A[j] % A[i] == 0:
      ok[j] = 0
    if A[j] == A[i]:
      ok[i] = 0

print(sum(ok))

Submission status: Time Limit Exceeded

Solution code:
import array
import numpy as np

n = int(input())
arr = np.array(sorted(list(map(int,input().split()))))
brr = array.array('i',[1]*n)

for i in range(n):
    if brr[i]==0:
        continue
    else:
        for j in range(i+1,n):
            if arr[j]%arr[i]==0:
                brr[j]=0
    if i<n-1 and arr[i]==arr[i+1]:
        brr[i]=0

print(sum(brr))

Submission status: Time Limit Exceeded

Solution code:
import array

n = int(input())
arr = array.array('i',sorted(list(map(int,input().split()))))
brr = array.array('i',[1]*n)

for i in range(n):
    if brr[i]==1:
        for j in range(i+1,n):
            if arr[j]%arr[i]==0:
                brr[j]=0
    if i<n-1 and arr[i]==arr[i+1]:
        brr[i]=0

print(sum(brr))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()
brr = [1]*n

for i in range(n):
    if brr[i]==1:
        for j in range(i+1,n):
            if arr[j]%arr[i]==0:
                brr[j]=0
    if i<n-1 and arr[i]==arr[i+1]:
        brr[i]=0

print(sum(brr))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
M = 1000001
cnt = [0]*M
ans = 0
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
    for i in range(x,M,x):
        cnt[i] += 1
for x in A:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter

a = int(readline())
n = list(map(int,readline().split()))
c = Counter(n)
ss = set(n)

ans = 0
for m in ss:
  if c[m] >= 2:
    continue
  chk = set()
  t = int(m**0.5)
  for i in range(1,t+1):
      if m%i == 0:
          chk.add(i)
          chk.add(m//i)
  if chk & ss == {m}:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

N=II()
A=LI()
cnt=[0]*((10**6)+1)
for elem in A:
  cnt[elem]+=1
unique=[]
for i in range((10**6)+1):
  if cnt[i]==1:
    unique.append(i)
cnt=[0]*((10**6)+1)
for elem in A:
  for m in range(elem*2,10**6+1,elem):
    cnt[m]=1
ans=0
for i in unique:
  if cnt[i]==0:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
from collections import defaultdict

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

a.sort() # 4 の倍数消した後, 2 の倍数消したら, 例えば 6 が消せなかったり
d = defaultdict(int)
for x in a:
    d[x] += 1

for x in d:
    for j in list(range(2, N)):
        if x * j >= N or b[x * j] == 1: #debuged
            break
        else:
            b[x * j] = 1

ans = 0
for x in a:
    if b[x] == 1:
        continue
    else:
        if d[x] >= 2:
            continue
        else:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math
from collections import defaultdict

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

d = defaultdict(int)
for x in a:
    d[x] += 1

for x in d:
    for j in list(range(2, N)):
        if x * j >= N:
            break
        else:
            b[x * j] = 1

ans = 0
for x in a:
    if b[x] == 1:
        continue
    else:
        if d[x] >= 2:
            continue
        else:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N):
    if dp[A[i]-1] != 0:
        dp[A[i]-1] = 2
        continue
    else:
        for j in range(1, max(A)//A[i]+1):
            dp[A[i]*j-1] += 1

ans = 0
for i in range(N):
    if dp[A[i]-1] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

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

ng_count = 0

for a in A:
    # 自分は必ず割り切れる 他にいたら 0が2以上になるはず
    if np.count_nonzero(a % np_a == 0) > 1:
        ng_count += 1

print(N - ng_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

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

ng = []

for a in A:
    # 自分は必ず割り切れる 他にいたら 0が2以上になるはず
    if Counter(a % np_a)[0] > 1:
        ng.append(a)

print(N - len(ng))

Submission status: Time Limit Exceeded

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


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
is_a=[False for _ in range(n)]
ans=0

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

        if(i<n-1 and a[i]==a[i+1] and (i==0 or a[i]!=a[i-1])):
            ans-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin,stdout
LI=lambda:list(map(int,input().split()))
MAP=lambda:map(int,input().split())
IN=lambda:int(input())
S=lambda:input()
import math
from collections import Counter,defaultdict

d=defaultdict(int)
m=10**6+1
sieve=[-1]*m
n=IN()
a=sorted(LI())
for i in a:
    d[i]+=1
    for j in range(2*i,m,i):
        sieve[j]=1
ans=0
for i in a:
    if sieve[i]==-1 and d[i]==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for index_i, i in enumerate(A):
    ans += 1
    for index_j, j in enumerate(A):
        if index_i != index_j and i % j == 0: ans -= 1; break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# review series
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
divisible = [False for i in range(10**6+1)]
for x in A:
    cnt = 2*x
    while cnt <= 10**6:
        divisible[cnt] = True
        cnt += x
D = dict(Counter(A))
ans = 0
for key, value in D.items():
    if D[key] == 1 and divisible[key] == False:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

MAX_A = 10 ** 6
X = [0] * (MAX_A + 1)
for a in A:
    for i in range(a, MAX_A + 1, a):
        X[i] += 1

ans = len([a for a in A if X[a] == 1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = sorted(list(map(int, input().split())))
count = 0
dp = np.array([0] * max(A))
for a in A:
    if dp[a-1] != 0:
        dp[a-1] = 2
        continue
    dp[a-1:max(A)+1:a] += 1
for a in A:
    if dp[a-1] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
count = 0
dp = [0] * max(A)
for a in A:
    if dp[a-1] != 0:
        dp[a-1] = 2
        continue
    for i in range(a, max(A)+1, a):
        dp[i-1] += 1
    
for a in A:
    if dp[a-1] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

if original.count(A[0]) == 1:
    count += 1
while len(A) > 1:
    A = [j for j in A if j % A[0] != 0]
    if len(A) >= 1 and original.count(A[0]) == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

dp = [0] * max(A)

for a in A:
    if dp[a-1] != 0:
        dp[a-1] = 2
        continue
    for i in range(a, max(A)+1, a):
        dp[i-1] += 1
    
for a in A:
    if dp[a-1] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
count = 0
dp = [0 for _ in range(max(A))]
for a in A:
    if dp[a-1] != 0:
        dp[a-1] = 2
        continue
    for i in range(a, max(A)+1, a):
        dp[i-1] += 1
    
for a in A:
    if dp[a-1] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

dp = [0] * max(A)

for a in A:
    if dp[a-1] != 0:
        dp[a-1] = 2
        continue
    for i in range(a, max(A)+1, a):
        dp[i-1] += 1
for a in A:
    if dp[a-1] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def D():
    n = int(input())
    a = list(map(int, input().split()))
    result = 0
    for elm in a:
        if sum(map(lambda x: elm%x==0, a)) == 1:
            result += 1
    print(result)

D()

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
collect = collections.Counter(A)
A = sorted(list(set(A)))
count = 0

dp = [True] * max(A)

for a in A:
    for i in range(a, max(A)+1, a):
        if i != a:
            dp[i-1] = False
    if dp[a-1] and collect[a] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
collect = collections.Counter(A)
A = sorted(list(set(A)))
count = 0

if collect[A[0]] == 1:
    count += 1
while len(A) > 1:
    A = [j for j in A if j % A[0] != 0]
    if len(A) >= 1 and collect[A[0]] == 1:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N=int(input())
A=list(map(int,input().split()))
nmax=10**6
iscop=[True]*(nmax+1)
cnt=[0]*(nmax+1)

for a in A:
    cnt[a]+=1
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False
ans=0
for a in A:
    if cnt[a]<2 and iscop[a]:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N=int(input())
A=sorted(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)
cnt=[0]*(nmax+1)

for a in A:
    cnt[a]+=1
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False
ans=0
for a in A:
    if cnt[a]<2 and iscop[a]:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N=int(input())
A=sorted(list(map(int,input().split())))
nmax=10**6
iscop=[True]*(nmax+1)

for a in A:
    if iscop[a]==False:
        continue

    for j in range(2,nmax//a+1):
        iscop[j*a]=False

cnt=Counter(A)
ans=0
for k,v in cnt.items():
    if iscop[k] and v<2:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
data = stdin.readlines()

x = int(data[0].split()[0])
a = [int(s) for s in data[1].split()]
a = sorted(a, reverse = True)

counter = 0
for i in range(len(a)):
    for j in range(len(a)):
        if i != j and a[i] % a[j] == 0:
            break
    else:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

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

result = 0
stored = []
while len(As)!=0:
    item = As[-1]
    As = As[:-1]
    is_exist = False
    if item in stored:
        continue
    for A in As:
        if item%A==0:
            is_exist = True
            break
    if not is_exist:
        result+=1
    stored.append(item)
print(result)

Submission status: Time Limit Exceeded

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

result = 0
stored = []
while len(As)!=0:
    item = As[-1]
    As = As[:-1]
    is_exist = False
    if item in stored:
        continue
    for A in sorted(As):
        if item%A==0:
            is_exist = True
            break
    if not is_exist:
        result+=1
    stored.append(item)
print(result)

Submission status: Time Limit Exceeded

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

result = 0
stored = []
while len(As)!=0:
    item = As.pop()
    is_exist = False
    if item in stored:
        continue
    for A in sorted(As):
        if item%A==0:
            is_exist = True
            break
    if not is_exist:
        result+=1
    stored.append(item)
print(result)

Submission status: Time Limit Exceeded

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

result = 0
stored = []
while len(As)!=0:
    item = As.pop()
    is_exist = False
    if item in stored:
        continue
    for A in As:
        if item%A==0:
            is_exist = True
            break
    if not is_exist:
        result+=1
    stored.append(item)
print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
a.sort()
b=set([x for x in set(a) if a.count(x) > 1])
for i in range(len(a)):
  s=a[i]
  for j in range(i+1):
    if a[j]>s/2:
      if s not in b:
        ans+=1
        break
      else:
        break
    elif s%a[j]==0:
      break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=[]

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.append(a[i])
    for j in range(2,int((max_a)/a[i])+1):
      check.append(a[i]*j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#エラストテネスのふるいを用いることを考える
#出たものの倍数をいれるダメリストを準備しておく。
#各a[i]についてダメリストに入っていないものが求める個数である
#同じものが複数回出てくるもの（Counterを使えばいい）に関してはダメリストにその数もいれれば良い
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
a.sort()
min_a=a[0]
max_a=a[n-1]
#同じものが複数回出てくるもののcheck
dic=Counter(a)
#別リスト
check=[]

for i in range(n):
  if a[i] not in check:
    if dic[a[i]]>=2:
      check.append(a[i])
    for j in range(a[i]*2,max_a+1,a[i]):
      check.append(j)
ans=0
for i in range(n):
  if a[i] not in check:
    ans=ans+1

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

ans = n
divisibles = [False for i in range(n)]
for i in range(n):
    divisible = False
    for j in range(n):
        if i == j:
            continue
        elif divisibles[i]:
            continue
        elif a[i] < a[j]:
            break
        elif a[i] % a[j] == 0:
            ans -= 1
            divisibles[i] = True
            break

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

ans = n
divisibles = [False for i in range(n)]
for i in range(n):
    divisible = False
    for j in range(n):
        if i == j:
            continue
        elif a[i] < a[j]:
            break
        elif a[i] % a[j] == 0:
            ans -= 1
            divisibles[i] = True
            break

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

ans = n
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif a[i] < a[j]:
            break
        elif a[i] % a[j] == 0:
            ans -= 1
            break

print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

ans = n
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif a[i] % a[j] == 0:
            ans -= 1
            break

print(ans)

Submission status: Time Limit Exceeded

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

a_max = a[-1]
ans_list = [0] * a_max

ans = 0

for i in range(n):

    p = a[i]
    if a.count(p) > 1:
        continue

    if ans_list[p-1] == 0:
        for q in range(1, (a_max//p)+1):
            ans_list[p*q-1] = 1
            
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n= input()
n=int(n)
lst= input().split()
for i in range(0, n):
    lst[i]=int(lst[i])
lst.sort()
cnt=0
for i in range(0,n):
    flg=True
    for j in range(0,n):
        if(j>i and lst[j]>lst[i]):
            break
        else:
            if(j!=i and lst[i] % lst[j]==0):
                flg=False
                break
    if(flg==True):        
        cnt=cnt+1
print(cnt)