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 = list(map(int, input().split()))

seed = []

while A:
    A = sorted(A)
    wareta = []
    warenai = []

    q = A.pop(0)
    for a in A:
        if a % q == 0:
            wareta.append(a)
        else:
            warenai.append(a)

    if q not in wareta:
        seed.append(q) 

    A = warenai[:]

print(len(seed))

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(N):
        if B[j] and j != i:
            if A[j]==A[i]:
                B[i] = False
                B[j] = False
            elif A[j]%A[i]==0:
                B[j] = False
ans = 0
for i in range(N):
    if B[i]:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted(A,reverse=True)
count=0
for i in range(1,N,1):
  if B[i-1]!=B[i]:
    flag=False
    for j in range(N-1,i,-1):
      if B[i]%B[j]==0:
        flag=True
        break
      else:
        continue
    if flag==False:
      count+=1
    else:
      continue
  else:
    continue
flag=False
for j in range(N-1,0,-1):
  if B[0]%B[j]==0:
    flag=True
    break
  else:
    continue
if flag==False:
  count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
visited=[False for i in range(10**6+1)]
ban=[False for i in range(10**6+1)]
from collections import Counter
A.sort()
D=dict(Counter(A))
for n in A:
    if visited[n]==False:
        visited[n]=True
        for j in range(2,10**6):
            if 10**6<n*j:
                break 
            ban[n*j]=True
ans=0
for n in A:
    if D[n]==1 and ban[n]==False:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
used = [0 for _ in range(int(1e6+1))]

ans = 0
for i in A:
    if used[i] == 1:
        used[i] += 1
        continue
    for j in range(i, len(used), i):
        used[j] += 1
for a in A:
    if used[a] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A.sort()
collect = collections.Counter(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:
N = int(input())
A = input()
A = A.split(' ')

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

print(N - total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
lstA = []
dctA = {}
for n in input().split():
  i = int(n)
  lstA.append(i)
  dctA[i] = 0
lstA.sort()
for i in range(N):
  Ai = lstA[i]
  if dctA[Ai] > 0:
    continue
  for j in range(i + 1,N):
    Aj = lstA[j]
    if dctA[Aj] > 0:
      continue
    m = Aj % Ai
    if m == 0:
      dctA[Aj] += 1
c = 0
for a in dctA:
  if dctA[a] == 0:
    c += 1
print(c)

Submission status: Time Limit Exceeded

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

prime = [A[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:
        prime.append(A[0])
        if collect[A[0]] == 1:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      if j in aa:
	      ans[j] += 1
print(ans.count(1))

Submission status: Time Limit Exceeded

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

a.sort()
m = a[-1]

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

lis = [0]
for _ in range(m) :
    lis.append(0)

for i in a :
    t = 1
    while i*t <= m :
        lis[i*t] += 1
        t += 1

cnt = 0 
for i in a :
    if lis[i] == 1 :
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

a=[]

@jit
def dp(a):
    aaset=set()
    while True:
        aaset.add(a[0])
        a2=[]
        for i,ai in enumerate(a,1):
            if ai%a[0]!=0:
                a2.append(ai)
        a=a2.copy()
        if len(a2)==0:
          break
    return aaset

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)
    
aaset=dp(a)
aaset=aaset-dset    
print(len(aaset))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = np.array(A)
aa = np.sort(aa)
for i in range(len(aa)):
  judge = True
  j = i+1
  div = []
  while True:
    if len(aa) <= j:
      break
    if aa[j]%aa[i] == 0:
      if aa[j] == aa[i]:
        div.append(i)
      div.append(j)
    j += 1
  aa = np.delete(aa,div,0)

print(len(aa))

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(1,N+1):
  for j in range(1,N+1):
    
    if A[i-1] % A[j-1] == 0 and not i==j:
      break
    if j == N:
      ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
c = collections.Counter(A)
cnt = 0
max = int(10e5+1)
l = [0] * (max+1)
for n in A:
    for j in range(n, max+1, n):
        l[j] += 1
for n in A:
    if c[n] > 1:
        continue
    if l[n] == 1:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c = 0
for n in input().split():
  i = int(n)
  A.append(i)
A.sort()
for i in range(N):
  Ai = A[i]
  if i != N - 1:
    if Ai == A[i + 1]:
      continue
  flg = True
  for j in range(i):
    Aj = A[j]
    if Ai % Aj == 0:
      flg = False
      break
  if flg:
    c += 1
print(c)

Submission status: Time Limit Exceeded

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

a_list.sort()

tf_list=np.array([1]*n)

@njit
def fff(tf_list,a_list):
  for i in range(n):
    if tf_list[i]==0:
      continue
    for j in range(i+1,n):
      #print(i,j)
      if a_list[j] % a_list[i]==0:
        tf_list[j]=0
        if a_list[j] == a_list[i]:
          tf_list[i]=0
  return(tf_list,a_list)

tf_list,a_list=fff(tf_list,a_list)
#print(tf_list)      
print(sum(tf_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

U = 10**6 + 10

def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2:3] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]

def main(A, primes):
    B = np.zeros(U + 1, np.int64)
    for x in A:
        B[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            B[p * i] += B[i]
    ret = 0
    for x in A:
        ret += B[x] == 1
    return ret

A = np.array(read().split(), np.int64)[1:]
_, primes = prime_table(U)

print(main(A, primes))

Submission status: Time Limit Exceeded

Solution code:
from numba import njit
n=int(input())
a_list = list(map(int, input().split()))

a_list.sort()

tf_list=[1]*n

@njit
def fff(tf_list,a_list):
  for i in range(n):
    if tf_list[i]==0:
      continue
    for j in range(i+1,n):
      #print(i,j)
      if a_list[j] % a_list[i]==0:
        tf_list[j]=0
        if a_list[j] == a_list[i]:
          tf_list[i]=0
  return(tf_list,a_list)

tf_list,a_list=fff(tf_list,a_list)
#print(tf_list)      
print(sum(tf_list))

Submission status: Time Limit Exceeded

Solution code:
def d170(n,a):
    count=0
    dp=[0 for i in range(max(a)+1)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,max(a)+1,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c = 0
for n in input().split():
  i = int(n)
  A.append(i)
for i in range(N):
  Ai = A[i]
  flg = True
  for j in range(N):
    if i == j:
      continue
    Aj = A[j]
    if Ai % Aj == 0:
      flg = False
      break
  if flg:
    c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
c = 0
for n in input().split():
  i = int(n)
  A.append(i)
for i in range(N):
  Ai = A[i]
  flg = True
  for j in range(N):
    if i == j:
      continue
    Aj = A[j]
    if Ai % Aj == 0:
      flg = False
  if flg:
    c += 1
print(c)

Submission status: Time Limit Exceeded

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

a_list.sort()

tf_list=[1]*n

for i in range(n):
  if tf_list[i]==0:
    continue
  for j in range(i+1,n):
    #print(i,j)
    if a_list[j] % a_list[i]==0:
      tf_list[j]=0
      if a_list[j] == a_list[i]:
        tf_list[i]=0
      

#print(tf_list)      
print(sum(tf_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
a.sort()
n = 0
for i in range(N):
  d = True
  for j in range(N):
    if a[i] < a[j]:
      break
    elif i != j and a[i] % a[j] == 0:
      d = False
      break
  if d:
    n += 1
print(n)

Submission status: Time Limit Exceeded

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

dp = [True for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if A[i] % A[j] == 0:
            dp[i] = False
            break


ans = 0
for i,v in enumerate(dp):
    if v:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


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


def divisor(n):
    div_list = []
    limit = int(n**0.5) + 1
    for div in range(1, limit):
        if n % div == 0:
            div2 = n // div
            div_list.append(div)
            if div != div2:
                div_list.append(div2)
    
    return div_list


        
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

    
ans = n
for a in A:
    divs = divisor(a)
    for div in divs:
        if div == a:
            
            if A_dict[div] >= 2:
                ans -= 1
                break
        else:
            if A_dict[div] >= 1:
                ans -= 1
                break
            

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
teisuu1=10**6
N=int(input())
A=list(map(int,input().split()))
count_A=Counter(A)
dp=[True]*(teisuu1+1)
s=list(set(A))
for i in s:
  temp=i*2
  while temp<=max(s):
    dp[temp]=False
    temp+=i
ans=0
for i in A:
  if count_A[i]==1 and dp[i]==True:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = set([i for i in range(n)])

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1

    if i in erat:
        kouho.append(arr[i])

        dis = []
        for val in erat:
            if arr[val]%arr[i] == 0:
                dis.append(val)
        for d in dis:
            if len(erat) > 0:
                erat.discard(d)

    # print(erat)

# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 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()))


def divisor(n):
    div_list = set()
    limit = int(n**0.5) + 1
    for div in range(1, limit):
        if n % div == 0:
            div2 = n // div
            div_list.add(div)
            div_list.add(div2)
    
    return list(div_list)


        
A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

    
ans = n
for a in A:
    A_dict[a] -= 1
    divs = divisor(a)
    for div in divs:
        if A_dict[div] >= 1:
            ans -= 1
            break
            
    A_dict[a] += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy 
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[::-1]

N=int(input())
A=list(map(int,input().split()))
C=copy.copy(A)
count=0
s=0
for i in range(len(C)):
    A=copy.copy(C)
    B=make_divisors(C[i])
    B.append(C[i])
    A.remove(A[i])
    s=0
    for k in B:
        if k in A:
            s=1
    if s==0:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans_count = 0
for i in A:
  ans = [i%x for x in A]
  zerocount = ans.count(0)
  if zerocount < 2:
    ans_count = ans_count+1
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans_count = 0
for i in A:
  ans = list(map(lambda x: i%x, A))
  zerocount = ans.count(0)
  if zerocount < 2:
    ans_count = ans_count+1
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
count = 0
ans_count = 0
for i in range(N):
  for j in range(N):
    if A[i] == A[j]:
      continue
    if A[i]%A[j]!=0:
      count=count+1
  if count == (N-1):
    ans_count = ans_count + 1
  count = 0
print(ans_count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = sorted(list(map(int, input().split())))
dp = [True] * N

for i, ai in enumerate(a_list):
  if dp[i] == False:
    continue
  
  for j, aj in enumerate(a_list[i+1:]):
    if ai == aj:
      dp[i] = False
    if aj%ai == 0:
      dp[i+1+j] = False
  if dp[i] > a_list[-1]**0.5+1:
    break
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
##AC
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([0]*(max_num))
for i in a:
    for j in np.arange(i, max_num, i):
        dp[j] += 1
print(np.count_nonzero(dp[a] == 1))

Submission status: Time Limit Exceeded

Solution code:

def main():

    MAX_VALUE = 10**6 + 5

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

    cnt = [0] * MAX_VALUE

    ans = 0

    for x in a:

        for i in range(x, MAX_VALUE, x):
            cnt[i] += 1

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A.sort()

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

    ans = 0
    for i, a in enumerate(A):
        if B[a] == 1:
            continue
        for aa in range(a, max(A) + 1, a):
            B[aa] = 1

        if i != len(A) - 1 and A[i] == A[i + 1]:
            continue

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    A.sort()

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

    ans = 0
    for i, a in enumerate(A):
        if B[a]:
            continue
        for aa in range(a, max(A) + 1, a):
            B[aa] = True

        if i != len(A) - 1 and A[i] == A[i + 1]:
            continue

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = a[-1]+1
dp = np.array([True]*(max_num))

if n == 1:
    print(1)
elif np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in a:
        if dp[i]:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
            if np.count_nonzero(a==i) >1:
                dp[i] = False
    print(np.count_nonzero(dp[np.unique(a)] == True))

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
S = list(map(int,readline().split()))
A = sorted(set(S))
q = deque(A)
ans = 0
while q:
  t = q.popleft()
  if t == 1:
    if S.count(1) == 1:
      print(1)
      sys.exit()
    else:
      print(0)
      sys.exit()
  if S.count(t) ==1:
    ans += 1
  count = 0
  for j in range(len(q)):
    if q[j] % t == 0:
      count +=1
      q.remove(q[j])
      q.appendleft(1)
  for i in range(count):
    q.remove(1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
num=[False for _ in range(max(A)+1)]
check=[False for _ in range(max(A)+1)]
for a in A:
    if num[a]:
        check[a]=True
    else:
        num[a]=True
    
for a in A:
    if a>int(max(A)**1/2):
        break
    for k in range(2,max(A)//a+1):
        num[a*k]=False

ans=0
for i in range(1,max(A)+1):
    if num[i] and not check[i]:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
  N = int(input())
  A = [int(x) for x in input().split(" ")]
  A.sort()
  setA = set(A)
  maxA = max(A)
  DP = [0] * (maxA + 1)

  for i in range(1, maxA+1):
    if i in setA:
      DP[i] += A.count(i) 
      n = 2
      while i * n < maxA+1:
        DP[i * n] += 1
        n += 1

  not_divisible_list = [True] * N
  for i, a in enumerate(A):
    if DP[a] > 1:
      not_divisible_list[i] = False

  print(sum(not_divisible_list))

if __name__ == "__main__":
  resolve()

Submission status: Time Limit Exceeded

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

F = [0 for i in range(A[-1]+1)]
for i in A:
  F[i] = 1

c_set = set()
for i in A:
  if F[i] == 0:
    continue
  c_set.add(i)
  for j in range(i, A[-1]+1, i):
    F[j] = 0

ans = len(c_set)
d = 0
for i in c_set:
  if A.count(i) > 1:
    d += 1

print(ans - d)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = np.sort(np.array(list(map(int, input().split()))))
max_num = np.max(a)+1
dp = np.array([True]*(max_num))

if n == 1:
    print(1)
elif np.all(a==a[0]):
    print(0)
elif np.count_nonzero(a==1)  == 1:
    print(1)
else:
    for i in range(1,max_num):
        if dp[i] and i in a:
            for j in np.arange(i*2, max_num, i):
                dp[j] = False
            if np.count_nonzero(a==i) >1:
                dp[i] = False
    print(np.count_nonzero(dp[np.unique(a)] == True))

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(' ')]

s = np.array(sorted(set(a)),int)
bl = np.array([True]*len(s), bool)
for i in range(1, len(s)):
    mod = s[i]
    buf = s[:i][bl[:i]]
    for j in range(len(buf)):
        if mod % buf[j] == 0:
            bl[i] = False
            break
s = set(s[bl])

c = Counter(a)
keys = set([k for k, v in c.items() if v == 1])

print(len(s&keys))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = 1000001
X = [-1] * (N+1)
L = [{} for _ in range(N+1)]
k = 2
while k <= N:
    X[k] = 1
    L[k][k] = 1
    for i in range(k*2, N+1, k):
        X[i] = 0
        L[i][k] = 1
    d = 2
    while k**d <= N:
        for i in range(k**d, N+1, k**d):
            L[i][k] += 1
        d += 1
    while k <= N and X[k] >= 0:
        k += 1
P = [i for i in range(N+1) if X[i] == 1]

def divisors(n):
    ret = [1]
    for p in L[n]:
        ret_prev = ret
        ret = []
        for i in range(L[n][p]+1):
            for r in ret_prev:
                ret.append(r * (p ** i))
    return sorted(ret)

N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 1000001
for a in A:
    X[a] += 1

ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import njit

@njit(cache=True)
def solve(a,n):
    ava = [0]*a[-1]
    for i in range(n):
        for j in range(n):
            if a[j]%a[i]==0 and ava[a[j]-1]<2:
                ava[a[j]-1] += 1
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
from numba import njit

@njit
def solve(a,n):
    ava = [0]*a[-1]
    for i in range(n):
        for j in range(n):
            if a[j]%a[i]==0 and ava[a[j]-1]<2:
                ava[a[j]-1] += 1
    return ava.count(1)
 
if __name__=='__main__':
    n = int(sys.stdin.readline().rstrip())
    a = list(map(int,sys.stdin.readline().rstrip().split()))
    a.sort()
    print(solve(a,n))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = sorted([int(a) for a in input().split()])
counter = 0
for i in range(n):
    Dup = False
    a = A[i]
    if a == -1:
        continue
    else:
        counter += 1
        if i < n-1:
            for j in range(i+1,n):
                if a == A[j]:
                    Dup = True
                    A[j] = -1
                elif A[j] % a == 0:
                    A[j] = -1
            if Dup:
                counter -= 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
alist = tuple(map(int, input().split()))
dp = [0] * (max(alist) + 1)

for num in alist:
  r = num
  if dp[num] >= 2:
    continue
    
  while num <= max(alist):
    dp[num] += 1
    num += r

ans = 0    
    
for num in alist:
  if(dp[num] == 1):
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    a.sort()
    ava = [0]*a[-1]

    for i in range(n):
        for j in range(n):
            if a[j]%a[i]==0 and ava[a[j]-1]<2:
                ava[a[j]-1] += 1
    print(ava.count(1))
    return
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

for num in alist:
  r = num
  if dp[num] >= 2:
    continue
    
  while num <= max(alist):
    dp[num] += 1
    num += r

ans = 0    
    
for num in alist:
  if(dp[num] == 1):
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
# x,y = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 0
M = 1000005
cnt = [0 for _ in range(M)]

for x in a:
    for j in range(x,M,x):
        cnt[j] += 1
    
for x in a:
    if cnt[x] == 1:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def divisor(n):
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append(i)
            if i ** 2 == n:
                continue
            d.append(n // i)
    return d

n = int(input())
A = list(map(int, input().split()))
set_A = set(A)

cnt = [0]*(max(A)+1)
for a in A:
    tmp = set(divisor(a)) & set_A
    if len(tmp) == 1: cnt[a] += 1

ans = collections.Counter(cnt)
print(ans[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
# x,y = map(int,input().split())
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = 0
M = 1000005
cnt = [0 for _ in range(M)]

for ix,x in enumerate(a):
    i = x
    while i < M:
        cnt[i] += 1
        i += x
for x in a:
    if cnt[x] == 1:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[False]*10**6

for i in range(n):
  for j in range(a[i]*2,10**6,a[i]):
    b[j]=True

cnt=0
for i in range(n):
  if a.count(a[i])>1:
    continue
  if not b[a[i]]:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

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

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort(reverse=True)
temp = plst[:]
ans = 0
while temp:
    q = temp.pop()
    lst = []
    for i in temp:
        if i%q!=0: lst.append(i)
    if cnt[q] == 1: ans += 1
    temp = lst[:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter
N = int(input())
p = list(map(int, input().split()))

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort()
temp = plst[:]
ans = 0
while temp:
    q = temp[0]
    lst = []
    for i in temp:
        if i%q!=0: lst.append(i)
    if cnt[q] == 1: ans += 1
    temp = lst[:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import Counter
N = int(input())
p = list(map(int, input().split()))

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort()
temp = plst[:]
ans = 0
while temp:
    jdg = True
    q = temp[0]
    m = bisect.bisect_left(temp, 2*q)
    if len(temp)==1: lst = []
    else: lst = temp[1:m]
    for i in temp[m:]:
        if i%q!=0: lst.append(i)
    if cnt[q] == 1: ans += 1
    temp = lst[:]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split()))

    nums = [0] * 1000001
    for a in A:
        i, n = 1, a
        while n <= 1000000:
            nums[n] += i
            i += 1
            n = a * i
    ans = 0
    for a in A:
        if nums[a] < 2:
            ans += 1
    print(ans)


main()

Submission status: Time Limit Exceeded

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

A.sort()

flags = [1] * N

for ia, a in enumerate(A):
    if flags[ia] == 0:
        continue
    if ia == N-1:
        break
    for i in range(ia+1, len(A)):
        if A[i] == a:
            flags[ia] = 0
        if A[i] % a == 0:
            flags[i] = 0
print(sum(flags))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6

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

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
leng = 10**6+1
memo = [0]*leng
li = []
for n in map(int, input().split()):
    x = 0
    li.append(n)
    while x < leng:
        memo[x] +=1
        x += n
count = 0
for n in li:
    if memo[n] == 1:
        count+=1
print(count)