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 argparse
import collections
import logging.config
import sys
import csv
import numpy as np

def tester(n, a):
  cnt = 0
  for i in range(n):
    tester = 1
    for j in range(n):
      if (i != j) and (a[i]%a[j] == 0):
        tester = 0
    cnt += tester
  return (cnt)

  
  
def main():

    sa = input()
    n = int(sa)
    a = []
    sb = input().split()
    for d in sb:
      a.append(int(d))        
    print (tester(n,a))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
ai = [int(i) for i in input().split()]

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors



for i in range(n):
    num_li[ai[i]] += 1

ans = 0
    
for i in range(n):
    if num_li[ai[i]] > 1:
        continue
    #print(ai[i])
    flag = True
    div = make_divisors(ai[i])
    #print(div)
    for j in range(len(div)):
        if div[j] == ai[i]:
            continue
        #print(div[j],div)
        if num_li[div[j]] > 0:
            flag = False
            break
    if flag == True:
        ans += 1
    #exit()
print(ans)

Submission status: Time Limit Exceeded

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

counter = Counter(A)

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

check=A.copy()
search=[]

while True:
    if len(check)<=0:
        break
    
    c = check.pop(0)
    search.append(c)

    check = [ _ for _ in check if (_%c !=0)or(_ < c**(1/2)) ]

ans=[s for s in search if counter[s]==1]
print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
from collections import Counter as co
l=co(map(int,input().split()))
ans=set()
for k in l:
    if l[k]>=2:ans.add(k)
    for j in range(2*k,10**6+1,k):
        if j in l:
            ans.add(j)
        
        
print(len(l)-len(ans))

Submission status: Time Limit Exceeded

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

dp = np.ones(max(A)+1, dtype=bool)

for a in A:
    ind = [a * i for i in range(2, max(A)//a + 1)]
    dp[ind] = False
dub = [x for x in set(A) if A.count(x) > 1]
dp[dub] = False
print(sum(dp[A]))

Submission status: Time Limit Exceeded

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

B = sorted([x for x in set(A) if A.count(x) == 1])
C = [x for x in set(A) if A.count(x) > 1]
ans = 0
#自身よりも小さい数で試し割　あとに重複した要素で試し割
for i in range(len(B)):
    for b in B[:i]:
        if B[i] % b == 0:
            break
    else:
        for c in C:
            if B[i] % c == 0:
                break
        else:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    from collections import Counter
    C = Counter(A)
    #print(C)

    X = [0]*(max(A)+1)
    for i in A:
        j = i*2
        while j <= max(A):
            X[j] = 1
            j += i
    #print(X)

    ans = 0
    for a in A:
        if C[a] == 1 and X[a] != 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()))
A.sort()
check = [0]*(max(A)+1)
for a in A:
    i = 1
    while a * i <= max(A):
        check[a*i] += 1
        i += 1
cnt = 0
for a in A:
    if check[a] == 1: cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

check = [0]*(max(A)+1)
for a in A:
    i = 1
    while a * i <= max(A):
        check[a*i] += 1
        i += 1
cnt = 0
for a in A:
    if check[a] == 1: cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

from collections import Counter
C = Counter(A)
#print(C)

X = [0]*(max(A)+1)
for i in A:
    j = i*2
    while j <= max(A):
        X[j] = 1
        j += i
#print(X)

ans = 0
for a in A:
    if C[a] == 1 and X[a] != 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[0]*Amax

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==0:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=1
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math
import numpy as np

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

    A.sort()

    Amax=max(A)

    dp=np.array([0 for _ in range(Amax)])

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==0:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=1
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==True:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=False
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==True:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
            m=1
            while (a*m)<=Amax:
                dp[a*m-1]=False
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    c = Counter(a)
    del_list = []
    for k, v in c.items():
        if v >= 2:
            del_list.append(k)
    a = sorted(set(a))
    if len(a) == 0:
        print(0)
        exit()
    max_a = a[-1]
    b = [True] * (max_a + 1)
    def sived(x):
        for not_ans in range(x+x, max_a + 1, x):
            b[not_ans] = False
    for i in a:
        if b[i]:
            sived(i)
    ans = 0
    for i in a:
        if b[i]:
            if i in del_list:
                continue
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import math

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

    A.sort()

    Amax=max(A)

    dp=[True for _ in range(Amax)]

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop(0)
        if a==tmp:
            continue
        if dp[a-1]==True:
            if len(A)>0:
                if A[0]!=a:
                    res+=1
            else:
                res+=1
        m=1
        while (a*m)<=Amax:
            dp[a*m-1]=False
            m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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


def judge():
  count = 0
  for i in range(n):
    for j in range(n):
      if a[i]%a[j] ==0 and i!=j:
        count+=1
        break
  print(n-count)


judge()

Submission status: Time Limit Exceeded

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


ans=0
for i in range(N):
    time=0
    for j in range(N):
        if i==j:
            continue
        if P[i]%P[j] == 0:
            continue
        time+=1
    if time == (N-1):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
d = deque(a)

cnt = 0
while len(d) > 0:
    dd = d.pop()
    flg = 0
    for i in reversed(range(len(d))):
        if d[i] == dd:
            del d[i]
            flg = 1
        elif d[i] % dd == 0:
            del d[i]
    if flg == 0:
        cnt = cnt + 1


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
num = int(input())
x = input().split()
for i in range(num):
  x[i] = int(x[i])
count = 0
for i in range(num):
  ju = 0
  for j in range(num):
    if x[i] % x[j] == 0:
      ju += 1
    else:
      ju += 0
  if ju == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
p = []
while True:
        if len(a) == 0:
           break
        prime = min(a)       
        if len(a) ==  1:
            p.append(prime)
            break    
        if prime != a[1]:
          p.append(prime)    
        i = 0
        while i < len(a):
            if a[i] % prime == 0:
                a.pop(i)
                continue
            i += 1  
print(len(p))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,K,i):
      Flag[j] = 0
    if List.count(i) > 1:
      res += -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
K = New_List[N-1]+1
Flag = [1]*K
for i in New_List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,K,i):
      Flag[j] = 0
    if New_List.count(i) > 1:
      res += -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*1000001

for i in New_List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,1000001,i):
      Flag[j] = 0
    if New_List.count(i) > 1:
      res += -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(10**6+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

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

print(ans)

Submission status: Time Limit Exceeded

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

O = A.copy()

O = [k for k in O if O.count(k) == 1]

for i in A:
    for j in A:
        if i != j:
            if (i%j == 0):
                if i in O:
                    O.remove(i)

ans = len(O)

print(ans)

Submission status: Time Limit Exceeded

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

O = A.copy()

for h in A:
    if A.count(h) >1:
        if h in O:
            O.remove(h)



for i in A:
    for j in A:
        if i != j:
            if (i%j == 0):
                if i in O:
                    O.remove(i)

ans = len(O)

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
length=int(input())
list=list(map(int,input().split()))
list.sort()
max=list[-1]
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        for i in range(max//num+1):
            dp[num*i]=False
        if list.count(num)==1:
            ret=ret+1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
length=int(input())
list=list(map(int,input().split()))
list.sort()
max=list[-1]
dp=[True]*(max+1)
ret=0
for num in list:
    if dp[num]:
        for i in range(max//num+1):
            dp[num*i]=False
        if list.count(num)==1:
            ret=ret+1
print(ret)

Submission status: Time Limit Exceeded

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

if N == 1:
  print(1)
  exit(0)
#
A.sort()
A.append(0) 

b = []
ans = 0
i = 0

if A[0] ==1:
  if A[1] == 1:
    print(0)
  else:
    print(1)
  exit(0)
#
while i < N:
  c = A[i]
  for j in b:
    if c % j == 0:
      break
  else:
    b.append(c)
    if c != A[i+1]:
      ans += 1
  while c == A[i+1]:
    i += 1
  i += 1
#          
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:
        num += 1
  if num == int(N)-1:
    s += 1
print(s)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	refd = [0 for i in range(1000000 + 1)]
	for i,val in enumerate(A):
		for j in range(val,1000000 + 1,val):
			refd[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if refd[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
M = max(a)+1
t=[True]*M
a.sort()
s=set(a)
for i in a:
    if t[i] == 0:
        continue
    if a.count(i)>1:
        t[i] = False
    for j in range(2*i,M,i):
        t[j] = False
ans = 0
for k in a:
    if t[k] == True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A_ = [int(i) for i in input().split(None,n)[:n]]
A = sorted(A_)

cand = set()
dup = set()

for a in A:
  if a in cand:
    dup.add(a)
  flg = True
  for c in cand:
    if a % c == 0:
      flg = False
      break
  if flg:
    cand.add(a)
cand -= dup
print(len(cand))

Submission status: Time Limit Exceeded

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

a.sort()


for i in range(n):
    if i==0 or (i>=1 and a[i] != a[i-1]):
        for j in range(n):
            if a[i] % a[j] == 0:
                check += 1
            if check > 2:
                break
        if check == 1:
            ans += 1
        check = 0

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if a[i] % a[j] == 0:
            check += 1
        if check > 2:
            break
    if check == 1:
        ans += 1
    check = 0

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(n):
    for j in range(n):
        if a[i] % a[j] == 0:
            check += 1
    if check == 1:
        ans += 1
    check = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
from math import*

n=int(input())
arr=list(map(int,input().split()))
arr.sort()
ans=0
for i in range(len(arr)):
	z=0
	c=bisect_right(arr,arr[i])
	#print(c)
	for j in range(c-1):
		if arr[i]%arr[j]==0:
			z=1
			break
	if z==0:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
input=[input().split() for i in range(2)]
length=int(input[0][0])
list=[]
for i in range(length):
    list.append(int(input[1][i]))
ret=0
list.sort()
for i in range(length):
    flg=True
    num=list[i]
    if list.count(num)==1:
        for j in range(i):
            if i!=j and num%list[j]==0:
                flg=False
                break
        if flg:
            ret=ret+1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
input=[input().split() for i in range(2)]
length=int(input[0][0])
list=[]
for i in range(length):
    list.append(int(input[1][i]))
ret=0
for i in range(length):
    flg=True
    num=list[i]
    for j in range(length):
        if i!=j and num%list[j]==0:
            flg=False
            break
    if flg:
        ret=ret+1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(map(int,input().split()),reverse=True)
t=[0]*1000001
for i in a:
    t[i]+=1
    for j in range(i*2,1000001,i):
        t[j]+=2
print(t.count(1))

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
a=sorted(map(int,input().split()))
count=0
for i in range(n):
    b=a[i]
    c=True
    for j in range(n):
        if a[j]>b:
            break
        if b%a[j]==0 and i!=j:
            c=False
            break
    if c:
        count+=1
print(count)

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        elif (A[i] % A[j]) == 0:
            res.append(A[j])
        else:
            continue
        
    else:
        if len(res) == 0:
            count += 1
            
        else:
            res.clear()

print(count)

Submission status: Time Limit Exceeded

Solution code:
# エラトステネスの篩を使う！O(nloglogn)
N = int(input())
A = list(map(int,input().split()))

listA = [0] * (10**6+10)
ans = 0
for i in A:
    for j in range(i,10**6+10,i):
        if listA[j] != 0:
            listA[j] = 2
            continue
        else:
            listA[j] += 1

for i in A:
    if listA[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# エラトステネスの篩を使う！O(nloglogn)
N = int(input())
A = list(map(int,input().split()))

listA = [0] * (10**6+100)
ans = 0
for i in A:
    for j in range(i,10**6+100,i):
        if listA[j] != 0:
            listA[j] = 2
            continue
        else:
            listA[j] += 1

for i in A:
    if listA[i] == 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

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

ans = 0
for num in a:
    if cnt[num]==1: ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    for j in range(m):
        if (j + 1) % i == 0:
            x[j] += 1

for i in ints:
    if x[i-1] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [1] * n
cnt = Counter(a)

for i in range(n - 1):
    if check[i] == 0:continue
    if cnt[a[i]] > 1:check[i] = 0
    for j in range(i + 1, n):
        if a[j] % a[i] == 0:check[j] = 0

ans = sum(check)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections##from collections import Counter
N = int(input())
A = [int(x) for x in input().split()]  
A.sort()
Ac = collections.Counter(A)
Ak = list(Ac.keys())
Al = list(Ac.values())

i = 0
while i<=len(Ak)-1:
  a = Ak[i]
  j = i+1
  while j<=len(Ak)-1:
    if Ak[j]%a==0:
      del Ak[j]
      del Al[j]
    else:
      j+=1
      
  if Al[i]>1:
    del Ak[i]
    del Al[i]
  else:
    i+=1
    
print(len(Ak))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
List=list(map(int,input().split()))
b=[]
q=0
List=sorted(List)
M=List[len(List)-1]/2
while (List[0]<=M and len(List)>1):
    p=List[0]
    for i in range(0,len(List)):
        if List[i]%p!=0:
            b.append(List[i])
    if List[0]!=List[1]:
        q+=1
    List=b
    b=[]
    if len(List)==0:
        break
    M=List[len(List)-1]/2
if len(List)>0:
    y=[x for x in set(List) if List.count(x)==1]
    q+=len(y)
print(q)

Submission status: Time Limit Exceeded

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

while True:
  if i>=len(A)-1:
    break
  a = A[i]
  same_num = 0
  j = i+1
  
  while True:
    if j>len(A)-1:
      break
    elif A[j]==a:
      same_num+=1
      del A[j]
      ##continue
    elif A[j]%a==0:
      del A[j]
    else:
      j+=1
      
  if same_num>0:
    del A[i]
  else:
    i+=1
    
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if Flag[j] ==1:
        if New_List[j] % New_List[i] ==0:
          Flag[j] = 0
  if New_List[i] > New_List[N-1]/2:
    break
for i in range(N-1):
  for j in range(i+1,N):
    if New_List[j] == New_List[i]:
      Flag[j] = 0
      Flag[i] = 0
res = Flag.count(1)
print(res)

Submission status: Time Limit Exceeded

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

DP = [-1 for i in range(max(A)+1)]

A.sort()

for a in A:
  if DP[a] != 0:
    if DP[a] == 1:
      DP[a] = 0
      continue
    for i in range(2*a, max(A)+1, a):
      DP[i] = 0
    DP[a] = 1
  
    
ans = 0
for i in DP:
  if i == 1:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
List = list(map(int, input().split()))
res = 0
New_List = sorted(List)
Flag = [1]*N
for i in range(N):
  if Flag[i] ==1:
    for j in range(i+1,N):
      if Flag[j] ==1:
        if New_List[i] == New_List[j]:
          Flag[i] = 0
          Flag[j] = 0
        elif New_List[j] % New_List[i] ==0:
          Flag[j] = 0
        else:
          pass
      elif Flag[j] ==0:
        pass
  else:
    pass
res = Flag.count(1)
print(res)

Submission status: Time Limit Exceeded

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

DP = [-1 for i in range(max(A)+1)]

A.sort()

for a in A:
  if DP[a] == -1:
    for i in range(2*a, max(A)+1, a):
      DP[i] = 0
    DP[a] = 1
  elif DP[a] == 1:
    DP[a] = 2
    
ans = 0
for i in DP:
  if i == 1:
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def is_divideable(a, nums):
    x = 1
    while x ** 2 <= a:
        if a % x == 0:
            if x in nums or (a // x) in nums:
                return True
        x += 1
    return False


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    nums = set()
    A.sort()
    ans = 0
    for a in A:
        if cnt[a] == 1 and not is_divideable(a, nums):
            ans += 1
        nums.add(a)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(N - 1):
    for j in range(i + 1, N):
        if int(A[i]) > int(A[j]):
            A[i], A[j] = A[j], A[i]
            
total = 0
for i in range(N):
    chk = -1
    for j in range(N):
        if (i != j) and (int(A[i]) % int(A[j]) == 0):
            chk = 1
            break
        else:
            continue
        break

    if chk == 1:
        total += 1
print(N - total)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_array = list(map(int, input().split()))
ans = 0
check = [0 for _ in range(10 ** 6 + 5)]
A = A_array

for i in range(N):
  for j in range(int((len(check) - 1) / A[i])):
    check[A[i] * (j + 1)] += 1

for i in range(len(check) - 1):
  if i + 1 in A:
    if check[i + 1] == 1:
      ans += 1
    else:
      continue
  else:
    continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_array = list(map(int, input().split()))
ans = 0
check = [0 for _ in range(10 ** 6 + 5)]
A = sorted(A_array)

for i in range(N):
  for j in range(int((len(check) - 1) / A[i])):
    check[A[i] * (j + 1)] += 1

for i in range(len(check) - 1):
  if i + 1 in A:
    if check[i + 1] == 1:
      ans += 1
    else:
      continue
  else:
    continue

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = sorted(list(C.keys()))
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+2)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    cnt = 0

    Even = []

    for i in range(lenb):
        if B[i]%2==0:
            Even.append((B[i],i))
    lenEven = len(Even)
    evenindex = 0

    for i in range(lenb):
        if Boo[i] :
            if C[B[i]]==1:
                    cnt += 1
            if B[i]<500001:
                temp = B[i]*2 -1
                if  B[i]%2==0:
                    evenindex += 1
                    for j in range(evenindex,lenEven):
                        if Boo[Even[j][1]] and Even[j][0]>temp and Even[j][0] % B[i] == 0:
                            Boo[Even[j][1]]= False
                else:
                    for j in range(i+1,lenb):
                        if Boo[j] and s[B[j]-1]==False and B[j]>temp and B[j] % B[i] == 0:
                            Boo[j] = False

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
ex=[0]*1000001
for a in A:ex[a]+=1
cnt=0
for a in A:
    ex[a]-=1
    i=1
    while i*i<=a:
        if a%i==0 and(ex[i]>0 or ex[a//i]>0):
            break
        i+=1
    else:
        cnt+=1
    ex[a]+=1
print(cnt)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


l = [0] * (max(a)+1)


# for i in a:

#     c = 1
#     while True:
#         if i*c >= max(a):
#             break
#         l[i*c - 1] += 1
#         c += 1



for i in a:
    for j in range(i,max(a)+1, i):
        l[j] += 1



ans = 0

for i in set(a):
    if l[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


l = [0] * max(a)


for i in a:

    c = 1
    while True:
        if i*c-1 >= max(a):
            break
        l[i*c - 1] += 1
        c += 1



ans = 0

for i in set(a):
    if l[i-1] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N =int(input())
A = list(map(int, input().split()))
 
element1=[]
for u in range(N):
    for i in range(N):
        if A[u]<A[i]:
            continue
        if i==u:
                continue    
        amari=A[u]%A[i]
        if amari  == 0 :
            
            element1.append(A[u])
a=set(A)^set(element1)
print(len(a))

Submission status: Time Limit Exceeded

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

a.sort()
dp = [True for i in range(n)]

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

print(dp.count(True))