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 math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

	def find(self, x): # root
		if self.parents[x]<0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		x = self.find(x)
		y = self.find(y)

		if x==y:
			return

		if self.parents[x]>self.parents[y]:
			x,y = y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		root = self.find(x)
		return [i for i in range(self.n) if self.find(i)==root]

	def roots(self):
		return [i for i,x in enumerate(self.parents) if x<0]

	def group_count(self):
		return len(self.roots())

	def all_group_members(self):
		return {r: self.members(r) for r in self.roots()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()

d = defaultdict(int)

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

arr = []
remain = set()
for i in d:
	if d[i]!=1:
		remain.add(i)
arr = a[:]
arr.sort()

if len(arr)==0:
	print(0)
	exit()

maxa = 10**6+1
ans = [0]*(maxa+1)
for i in arr:
	ans[i]=1

for i in arr:
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

tyo = 0

for i in remain:
	if ans[i]==1:
		tyo+=1

print(ans.count(1)-tyo)

Submission status: Time Limit Exceeded

Solution code:
d=[i:=0]*8**7
for j in[*open(0)][1].split():d[int(j)]+=1
while i<1e6:
 i+=1;j=i
 while j<1e6:j+=i;d[j]*=d[i]<1
print(d.count(1))

Submission status: Time Limit Exceeded

Solution code:
N =input()
A = list(map(int, input().split()))
MA =max(A)
N=int(N)
s=0
A2 = [-1] 
B =[-1]#重複
LS =[-1]
for i in range(0,N):
  k=1
  P =A[i]
  if P in A2:
    B.append(P)
    pass
  else:
    while P*k<=MA:
      LS.append(P*k)
      k+=1
    A2.append(P)
for j in range(0,N):
  if A[j] in B:
    pass
  else:
    if LS.count(A[j]) ==1:
      s=s+1

print(s)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

for i in range(n):
  v=a[i]
  if is_p[v]:
    for j in range(v+v,10**6+1,v):
#      print(j)
      is_p[j]=0

c=Counter(a)

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:
from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    A.sort()
    C = Counter(A)

    MAX = 2000005
    T = [0]*MAX

    ans = 0
    for a in A:
        if T[a]:
            continue
        else:
            if C[a] == 1:
                ans += 1
            for i in range(2*a, MAX, a):
                T[i] += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    A.sort()
    C = Counter(A)

    MAX = 2000005
    T = [0]*MAX

    ans = 0
    for a in A:
        if T[a]:
            continue
        else:
            if C[a] == 1:
                ans += 1
            for i in range(2*a, MAX, a):
                T[i] += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Contest No.: ABC170
# Problem No.: D
# Solver:      JEMINI
# Date:        20200614

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    nums.sort()

    check = [False] * (10 ** 6 + 1)
    for i in range(1, n):
        if nums[i] == nums[i - 1]:
            check[nums[i]] = True

    ans = 0
    for i in range(n):
        if check[nums[i]] == False:
            ans += 1
        cnt = nums[i] * 2
        while cnt < 10 ** 6 + 1:
            check[cnt] = True
            cnt += nums[i]
    print(ans)

    
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N=input()
A = list(map(int, input().split()))
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    if T== False:
      break
    if A[i]>=A[j]:
      if A[i] % A[j]==0:
        if i==j:
          pass
        else:
          T=False
  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Time Limit Exceeded

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

def func1(a):
    a.sort()
    cnt=0
    chker=[]
    for i in a:
        candiv=False
        if a.count(i)>1:
            candiv=True
            if chker.count(i)==0:
                chker.append(i)
        else:
            for j in chker:
                if j*2>i:
                    break
                if i%j==0:
                    candiv=True
                    break
        if candiv==False:
            cnt+=1
            chker.append(i)
    print(cnt)
func1(a)

Submission status: Time Limit Exceeded

Solution code:
N=input()
A = list(map(int, input().split()))
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    if T== False:
      break
    if A[i] % A[j]==0:
      if i==j:
        pass
      else:
        T=False
        
  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Time Limit Exceeded

Solution code:
N=input()
A = list(map(int, input().split()))
T=True
sucl =[]
for i in range(0,int(N)):
  T=True
  for j in range(0,int(N)):
    
    if A[i] % A[j]==0:
      if i==j:
        pass
      else:
        T=False
        
  if T==True:
    sucl.append(i)
print(len(sucl))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def read():
    return list(map(int, input().split()))

n = int(input())
a = read()
a = np.array(a)
ans = np.zeros(n)
for i in a:
    mod = a % i
    ans += (mod > 0).astype(np.uint8)
print(np.count_nonzero(ans == n - 1))

Submission status: Time Limit Exceeded

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

dp = {i: 0 for i in a}
for elem in a:
    t = 2
    while elem * t <= maxa:
        dp[elem * t] = 1
        t += 1

ans = 0
for elem in a:
    if dp[elem] == 0 and a.count(elem) == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

dp = {i+1: 0 for i in range(maxa)}
for elem in a:
    t = 2
    while elem * t <= maxa:
        dp[elem * t] = 1
        t += 1

ans = 0
for elem in a:
    if dp[elem] == 0 and a.count(elem) == 1:
        ans += 1
print(ans)

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 range(i+1,n+1):
        #print(a[j])
        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()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in x:
        if not is_prime[i]:
            continue
        if not x.count(i) > 1:
            cnt += 1
        for j in range(i*2, nmax+1, i):
            is_prime[j] = False
    print(cnt)

Eratosthenes(a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
def isPrime(n):
  if n == 1:
    return False
  for k in range(2, int(math.sqrt(n)) + 1):
    if n % k == 0:
      return False
  return True

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

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

if A[0] == 1 and A[1] == 1:
  print(0)
  exit()
if A[0] == 1 and A[1] != 1:
  print(1)
  exit()

for i in range(N):
  x = A[i]
  if isPrime(x):
    if i - 1 >= 0 and x == A[i - 1]:
        cnt -= 1
        continue
    if i + 1 < N and x == A[i + 1]:
        cnt -= 1
        continue
    continue
    
  for j in range(min(i + 2, N)):
    if i == j:
      continue
    y = A[j]
    if x % y == 0:
      cnt -= 1
      break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    """"ここに今までのコード"""

    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    count = 0
    while a != []:
        t = a[0]
        if len(a) == 1:
            count +=1
        elif a[0] != a[1]:
            count +=1
        a = [i for i in a if i % t != 0]
    
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 and not ac[j]==0:
                ac[j]=0


print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(list(map(int, input().split()))) + [0]
 
memo = ['Y'] * (10**6+1)
count = 0
 
for i in range(N):
    if memo[A[i]] == 'N':
        continue
    for j in range(A[i], max(A)+1, A[i]):
        memo[j] = 'N'
    if A[i] == A[i+1]:
        continue
    
    count += 1
 
print(count)

Submission status: Time Limit Exceeded

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

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

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

ans = 0

for i in range(max(A)+1):
    if dp[i] == 1:
        ans += 1
    if dp[i] != 0:
        for j in range(2*i, max(A)+1, i):
            if dp[j] != 0:
                dp[j] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
s = list(set(A))
dp = [True] * m
for x in s:
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if Counter(A)[a] == 1 and dp[a]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]

a = sorted(a)

for i in a:
    ac[i] +=1

count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 and not ac[j]==0:
                ac[j]=0


print(count)

Submission status: Time Limit Exceeded

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


D = [0]*(10**6+1)
for i in A:
    # ダブってる値は2以上に
    D[i] += 1
U = []
for i in A:
    # 一つしかないものを選ぶ
    if D[i] == 1:
        U.append(i)

T = [False]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6+1, i):
        T[j] = True

# TがFalseかつDが1の数を数える
ans = 0
for i in U:
    if T[i] == False:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
def divisor(N):
    from math import sqrt
    D = []
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
          D.append(i)
          D.append(N // i)
 
    return list(set(D))
 
 
count = 0
A_set = set(A)
A_dict = {a: 0 for a in A}
for a in A:
    A_dict[a] += 1
    
for a in A:
    a_div = set(divisor(a)) - {a}
    if len(a_div - A_set) == len(a_div):
        if A_dict[a] == 1:
            count += 1
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  As.sort(reverse=True)
  ans = 0
  
  for i in range(n):
    flag = True
    if As[i] in As[0:i] or As[i] in As[i+1:n]:
        flag = False
        continue
    	
    for j in range(n-1,i,-1):
      #print(As[i], As[j])
      if As[i] < 2*As[j] :
        break
             
      if As[i] % As[j] == 0:
        flag = False
        break
    #print(flag)
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(n)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list=[int(i) for i in input().split()]

count1=[0 for i in range(N)]

for i in range(N):
    count2=0
    for j in range(i,N):
        if i==j:
            continue
        if A_list[i]%A_list[j]==0:
            count1[i]+=1
        if A_list[j]%A_list[i]==0:
            count1[j]+=1
print(len([1 for i in count1 if i==0]))

Submission status: Time Limit Exceeded

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


D = [0]*(10**6+1)
for i in A:
    # ダブってる値は2以上に
    D[i] += 1
U = []
for i in A:
    # 一つしかないものを選ぶ
    if D[i] == 1:
        U.append(i)

T = [False]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6+1, i):
        T[j] = True

# TがFalseかつDが1の数を数える
ans = 0
for i in U:
    if T[i] == False:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]

a = sorted(a)

for i in a:
    ac[i] +=1

count =0

for i in a:
    if ac[i]>0:
 
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 :
                ac[j]=0


print(count)

Submission status: Time Limit Exceeded

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

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

A_sort = sorted(A)
A_set = list(sorted(set(A)))
A_chk = [0]*len(A_set)
A_temp_ans = []
A_overlap = []
ans = 0

#print("A_sort", A_sort)
#print("A_set", A_set)
#print("A_chk", A_chk)


 #
for i in range( len(A_set) ):

  if( A_chk[i]==0 ):
    A_chk[i] = 1
    A_temp_ans.append( A_set[i] )
    
    for j in range( len(A_set)-(i+1) ):
      if ( A_chk[i+1+j]==0 ):
        if ( A_set[i+1+j] % A_set[i] == 0  ):
          A_chk[i+1+j] = -1
  
  #print(i+1,A_chk)
#print("A_temp_ans",A_temp_ans)


 #
for i in range( len(A_sort)-1 ):
  if ( A_sort[i] == A_sort[i+1] ):
    A_overlap.append( A_sort[i] )

A_overlap = list(set(A_overlap))
#print("A_overlap",A_overlap)


 #
ans = 0
for i in range( len(A_temp_ans) ):

  overlap_chk = 0
  
  for j in range( len(A_overlap) ):
    if ( A_temp_ans[i]==A_overlap[j] ):
      overlap_chk = 1
      break
  
  if ( overlap_chk == 0 ):
    ans += 1
  
 #
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
count = 0
while a != []:
    t = a[0]
    if len(a) == 1:
        count +=1
    elif a[0] != a[1]:
        count +=1
    a = [i for i in a if i % t != 0]
    

print(count)

Submission status: Time Limit Exceeded

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

T = [0]*(10**6+1)
D = [0]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6+1, i):
        T[j] += 1
    # ダブってる値は2以上に
    D[i] += 1

# TがFalseかつDが1の数を数える
ans = 0
for i in A:
    if T[i] == 0 and D[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

for i in arr:
    for j in range(i, len(dp), i):
        if j in arr:
            dp[j] += 1
print(dp.count(1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int, input().split()))
 
count = 0
for i in range(n):
  for j in range(n):
    if i != j and a[i] % a[j] == 0:
      break
    elif j == n-1:
      count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
dp = [True] * m
for x in list(set(A)):
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if Counter(A)[a] == 1 and dp[a]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

T = [False]*(10**6+1)
D = [0]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6+1, i):
        T[j] = True
    # ダブってる値は2以上に
    D[i] += 1

# TがFalseかつDが1の数を数える
ans = 0
for i in A:
    if T[i] == False and D[i] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

#定数倍のやつに＋１する
A=[0]*(max(ls)+1)
for i in range(len(ls)):
  a=1
  while ls[i]*a<=max(ls):
    b=ls[i]*a
    if A[b]<=1:
      A[b]+=1
    a+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = set()
ans = 0
for i in sorted(set(a)):
    j=i*2
    while j<=1000000:
        s.add(j)
        j+=i
    if i not in s and c[i]==1:
        ans+=1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list=[int(i) for i in input().split()]

count1=0
for i in range(N):
    count2=0
    for j in range(N):
        if i==j:
            continue
        if A_list[i]%A_list[j]==0:
            count2+=1
            break
    if count2==0:
        count1+=1
print(count1)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [False] * (A[-1]+1)

for a in A:
    B[a] = True

i = 0
while i < len(A)-1:
    if A[i] == A[i+1]:
        B[A[i]] = False
        A.pop(i)
    i += 1

for a in A:
    for x in range(2*a, len(B), a):
        B[x] = False

print(sum(B))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = set()
ans = 0
for i in sorted(set(a)):
    j=i*2
    while j<=1000000:
        s.add(j)
        j+=i
    if i not in s and c[i]==1:
        ans+=1
            
print(ans)

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[a] == True))

Submission status: Time Limit Exceeded

Solution code:
M=10**7
A=[0]*M
_,*l=map(int,open(0).read().split())
for i in sorted(l):
    A[i]+=1
    if A[i]==1:
      for j in range(2*i,M,i):A[j]+=9
print(A.count(1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
s = set(A)
dp = [True] * m
for i in range(len(s)):
    t = A[i] * 2
    while t < m:
        dp[t] = False
        t += A[i]
ans = 0
for a in A:
    if A.count(a) == 1 and dp[a]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
s = set(A)
dp = [True] * m
for i in range(N):
    t = A[i] * 2
    while t < m:
        dp[t] = False
        t += A[i]
ans = 0
for a in A:
    if A.count(a) == 1 and dp[a]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
M=10**7
_,*l=map(int,open(0).read().split())
d=[1]*(M)
C=Counter(sorted(l))
s=0
for a,b in C.items():
    if b != 1:d[a]=0
    elif d[a]:s+=1
    for j in range(a,M,a):d[j]=0
print(s)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list=[int(i) for i in input().split()]

count1=0
for i in range(N):
    count2=0
    for j in range(N):
        if i==j:
            continue
        if A_list[i]%A_list[j]==0:
            count2+=1
    if count2==0:
        count1+=1
print(count1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

D = defaultdict(int)
E = defaultdict(int)

for x in A:
  Flag = True

  if E[x] >= 1:
    D[x] += 1
    continue

  for j in D.keys():
    if x%j == 0:
      Flag = False
      break
    
  if Flag:
    D[x] += 1
    E[x] += 1

ans = len([i for i in D if D[i] == 1])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
_,*p=map(int,open(0).read().split())
i=0
p.sort()
while(len(p)!=0):
  t=p[0]
  p=[m if m!=t else 0 for m in p[1:] if m%t!=0 or m==t ]
  if 0 in p:p=[i for i in p if i!=0]
  else:i+=1
print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array(sorted([a for a in map(int,input().split())]))

DP = [True] * N

for dp,a,i in zip(DP,A,range(N)):
    if dp:
        if len(np.where(A==a)[0])>=2:
            DP[i] = False
        for j in np.where(A[(i+1):]%a==0)[0]:
            DP[j+i+1] = False

        
print(DP.count(True))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = list(map(int, input().split()))
na = np.array(a)
cnt = 0

for i in range(n):
    m = np.count_nonzero(na[i] % na == 0)
    if m == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

# 倍数のやつはTrueに
T = [False]*(10**6+1)
for i in A:
    for j in range(i*2, 10**6, i):
        T[j] = True

# ダブってるやつはTrueに
dbl = []
for i in A:
    if A.count(i) != 1:
        dbl.append(i)

for i in dbl:
    T[i] = True

# Falseの数を数える
ans = 0
for i in A:
    if T[i] == False:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
_,*p=map(int,open(0).read().split())
q=[]
while(len(p)!=0):
  t=p[0]
  q=[m for m in q if m%t!=0]
  p=[m if m!=t else 0 for m in p[1:] if m%t!=0 or m==t ]
  if 0 in p:
    p=[i for i in p if i!=0]
  else:q+=[t]
print(len(q))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

def solve(N: int, A: "List[int]"):
    A.sort()
    ret = 0
    used = [False] * N
    for i, v in enumerate(A):
        if used[i]:
            continue
        if not (i < N - 1 and v == A[i + 1]):
            ret += 1
        for j in range(i + 1, N):
            if A[j] % v == 0:
                used[j] = True
    print(ret)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
dp = [0] * m
for i in range(N):
    if dp[A[i]] == 0:
        dp[A[i]] = 1
        t = A[i] * 2
        while t < m:
            dp[t] = 2
            t += A[i]
ans = 0
for a in A:
    if A.count(a) == 1 and dp[a] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
prime_judge = [0]*(max(a)+1)
for p in a:
  prime_judge[p] += 1
  if prime_judge[p] == 1:
    for j in range(2*p, max(a)+1, p):
      prime_judge[j] += 2

print(prime_judge.count(1))

Submission status: Time Limit Exceeded

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

def divisor(N):
    from math import sqrt
    D = []
    for i in range(1, int(sqrt(N)) + 1):
        if N % i == 0:
          D.append(i)
          D.append(N // i)

    return list(set(D))


count = 0
A_set = set(A)
A_dict = {a: 0 for a in A}
for a in A:
    A_dict[a] += 1
    
for a in A:
    a_div = set(divisor(a)) - {a}
    if len(a_div - A_set) == len(a_div):
        if A_dict[a] == 1:
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:


# def main():
#     n = int(input())
#     a = list(map(int, input().split()))
#     cnt = [0]*n
#     a.sort(reverse=True)
#     if a.count(1) == 1:
#         print(1)
#         exit()
#     if a.count(1) >= 2:
#         print(0)
#         exit()
#     for i in range(n-1):
#         if cnt[i] == 1:
#             continue
#         for j in range(i+1,n):
#             if a[i] == a[j]:
#                 cnt[i] = 1
#                 cnt[j] = 1
#                 break
#             if a[i]%a[j] == 0:
#                 cnt[i] = 1
#                 break
#     print(n - sum(cnt))

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



def main():
    n = int(input())
    a = list(map(int, input().split()))
    temp = [1]*(max(a)+1)
    temp[0] = 0
    a.sort()
    if a.count(1) == 1:
        print(1)
        exit()
    if a.count(1) >= 2:
        print(0)
        exit()
    for i in range(n-1):
        if a[i] == a[i+1]:
            temp[a[i]] = 0
        for j in range(2,(max(a)//a[i])+1):
            if a[i] * j <= max(a):
                temp[a[i] * j] = 0
    cnt = 0
    for k in a:
        if temp[k] == 1:
            cnt += 1
    print(cnt)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n = int(input().strip())
    a = list(map(int, input().strip().split()))

    a.sort()
    penalty = 0

    num = 0
    while len(a) > num and not len(a) == 0:
        if not len(a) == num + 1 and a[num] == a[num + 1]:
            while not len(a) == num + 1 and a[num] == a[num + 1]:
                a.pop(num)
            penalty += 1

        i = num + 1
        while len(a) > i:
            if a[i] % a[num] == 0:
                a.pop(i)
            else:
                i += 1
        num += 1
    print(len(a) - penalty)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))


count =0

while(not a==[]):
    am = min(a)
    c = a.count(am)
    a = [j for j in a if not j %am ==0]
    if c ==1:
        count =count +1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = [int(x) for x in input().split()]

A.sort()
M = max(A)
num_list = [0] * (M + 1)
for a in A:
    i = a
    if num_list[i] > 0:
        num_list[i] += 1
        continue
    while i < M + 1:
        num_list[i] += 1
        i += a
count = 0
for i in range(len(num_list)):
    if num_list[i] == 1 and i in A:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = {}
for i in range(n):
  c[a[i]] = c.get(a[i], 0) + 1

prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for p in sorted(a):
  if prime_bool[p]:
    if c[p] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
c = {}
for i in range(n):
  c[a[i]] = c.get(a[i], 0) + 1
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False
count = 0
for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    if c[p] == 1:
      count += 1
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

print(count)

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
A = sorted([int(i) for i in input().split()])
C = collections.Counter(A)
tested = [True for i in range(10**7+1)]

ans = 0
for i in range(N):
    if C[A[i]] == 1 and tested[A[i]] is True:
        ans += 1

    for j in range(A[i], 10**6+1, A[i]):
        tested[j] = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = [int(x) for x in input().split()]

A.sort()
M = max(A)
num_list = [0] * (M + 1)
for a in A:
    i = a
    while i < M + 1:
        num_list[i] += 1
        i += a
count = 0
for i in range(len(num_list)):
    if num_list[i] == 1 and i in A:
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
	_ = int(input())
	A = sorted(list(map(int, input().split())))
	Y = 0
	while True:
		a = A[0]
		A = A[1:]
		if not a in A:
			Y+=1
		A = list(filter(lambda x: x%a>0, A))
		if len(A)<2:
			break
	print(Y+len(A))
resolve()