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

a.sort()

ans = 0

for i in range(n):
    ai = a[i]

    if i != n-1:
        if ai == a[i+1]:
            continue

    if i != 0:
        if ai == a[i-1]:
            continue

    for j in range(i):
        aj = a[j]

        if aj*2 > ai:
            ans += 1
            break

        if ai % a[j] == 0:
            break
    else:
        ans += 1



print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう

kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
maxA = A[-1]
work=[0]*(A[-1]+1)

for i in range(len(A)):
    maxN = int(maxA/A[i])
    for n in range(1,maxN+1):
        buf = A[i]*n
        #remove_list.append(buf)
        work[buf]+=1
            #print(A[i]*n)
#target = kouho[:]
#kouho = list(set(kouho) - set(remove_list))

sm=0
for s in A:
    if work[s]==1: sm+=1
print(sm)

#print(len(kouho))

Submission status: Time Limit Exceeded

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

a.sort()

ans = 0

for i in range(n):
    ai = a[i]

    if i != n-1:
        if ai == a[i+1]:
            continue

    for j in range(i):
        if ai % a[j] == 0:
            break
    else:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
c=[1]*n
for i in range(n-1):
  t=a[i]
  if c[i]:
    if t==a[i+1]:
      c[i]=0
    for j in range(i+1,n):
      if a[j]%t==0:
        c[j]=0
print(sum(c))

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
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:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  ans = 0
  
  for i in range(n):
    flag = True
    for j in range(n):
      if i == j:
        continue
       
      if As[i] == As[j]:
        flag = False
        break
       
      if As[i] < 2*As[j]:
        continue
      
      if As[i] % As[j] == 0:
        flag = False
        break
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	count = 0
	a_max = A[-1]
	dp = [1]*a_max
	for a in A:
		point = dp[a-1]
		if point == 1:
			dp[a-1] = 2
			count += 1
			i = 2
			while a*i <= a_max:
				dp[a*i-1] = 0
				i += 1
		elif point == 2:
			count -= 1
			dp[a-1] = 0
	print(count)






if __name__ == '__main__':
    main()

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)
data = sorted(list(set(a)))
prime_bool = [True]*(max(a)+1)
prime_bool[0] = False

for i in range(len(data)):
  p = data[i]
  if prime_bool[p]:
    #print(p)
    for j in range(2*p, max(a)+1, p):
      prime_bool[j] = False

count = 0
for i in range(len(prime_bool)):
  if prime_bool[i]:
    if c[i] == 1:
      count += 1
print(count)
#print(prime_bool)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
OKlist = [0]*(10**6+100)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        OKlist[A[i]] += 1
    else:
        for j in range(10**6+10):
            if A[i]*j > 10**6:
                break
            else:
                OKlist[A[i]*j] += 1
OKlist[max(A)] += 1
cnt = 0
for i in A:
    if OKlist[i] == 1:
        cnt += 1
        
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	A = np.array(LI())
	A.sort()
	prime_list = set()
	a_max = A[-1]
	dp = [1]*a_max
	for a in A:
		point = dp[a-1]
		if point == 1:
			dp[a-1] = 2
			prime_list.add(a)
			i = 2
			while a*i <= a_max:
				dp[a*i-1] = 0
				i += 1
		elif point == 2:
			prime_list.remove(a)
			dp[a-1] = 0

	print(len(prime_list))






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

ans = 0

for i in range(n):
    ai = a[i]
    for j in range(n):
        if i == j:
            continue

        if ai % a[j] == 0:
            break

    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
#import sys
#input = sys.stdin.readline

def MakeDivisors(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]

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
#
def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))

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

#################################################
#################################################
#################################################
#################################################

#31-

n = int(input())

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

a.sort()

#print(a)
li = [0 for i in range(10**6+1)]
ans = 0
co = 0

taboo = [0]*n





for i in a:
    #print(i)
    if(taboo[co]==1):
        co+=1
        continue
    t = MakeDivisors(i)
    #print(li[:30])
    #print(i,t,ans)
    ok=1

    if(co!=0):
        if(a[co-1]==i):
            ok=0
    if(co!=n-1):
        if(a[co+1]==i):
            ok=0
    for j in t:
        if(li[j]==1):
            ok=0
    ans+=ok
    #print(i,ok,ans)
    li[i]=1
    co+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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:
try:
  n  = int(input())
  As = list(map(int, input().split()))
  ans = 0
  
  for i in range(n):
    flag = True
    for j in range(n):
      if i == j:
        continue
      
      if As[i] % As[j] == 0:
        flag = False
        break
    if flag:
      ans += 1
  print(ans)
except EOFError:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


def sieve(N,A,dp):
    for i in range(N):
        now = A[i]
        M = A[-1] // now
        for j in range(2,M+1):
            dp[now*j-1] = False
    return dp


def cnt(N,A,dp):
    skip = 0
    res = 0
    for i in range(N):
        now = A[i]
        if skip == now:
            continue
        if i != N - 1:
            if now == A[i+1]:
                skip = now
                continue
        if dp[now-1]:
            res += 1
    return res


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

    A = sorted(A)
    A = np.array(A)

    dp = np.array([True for i in range(A[-1])])
    # print(dp)
    dp = sieve(N,A,dp)
    # print(dp)

    res = cnt(N,A,dp)

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
A = sorted(LI())
ans_bool = [0]*(10**6+1)
for a in A:
    num = a
    while num<=10**6:
        ans_bool[num] += 1
        num += a
ans = 0
for a in A:
    if ans_bool[a]==1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
wa = []
while a != []:
    t = a[0]
    if len(a) == 1:
        wa.append(t)
    elif a[0] != a[1]:
        wa.append(t)
    han = int(max(a)/t)+2
    bai = [i*t for i in range(1, han)]
    a = [i for i in a if i not in bai]
    

print(len(wa))

Submission status: Time Limit Exceeded

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

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

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

    tmp = 1
    while tmp * a[i] <= 10 ** 6:
        flg[tmp * a[i]] = False
        tmp += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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


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

    past = set()
    ans = 0
    ansset = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in past:
                break
        else:
            ansset.add(a)
            ans += 1

        past.add(a)

    c = collections.Counter(A)
    for cc in c.most_common():
        if cc[1] == 1:
            break

        if cc[1] > 1 and cc[0] in ansset:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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


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

    past = set()
    ans = 0
    ansset = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in past:
                break
        else:
            ansset.add(a)
            ans += 1

        past.add(a)

    c = collections.Counter(A)
    for cc in c.most_common():
        if cc[1] == 1:
            break

        if cc[1] > 1 and cc[0] in ansset:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import time

N = int(input())
A = list(map(int, input().split()))
A.sort()#わるほう
remove_list = []

kouho = sorted([x for x in set(A) if A.count(x) == 1])
#maxA = 10**5

#target = kouho[:]
if kouho != []:
    maxA = kouho[-1]

for i in range(len(A)):
    if kouho == []:
        break
    maxN = int(maxA/A[i])
    for n in range(2,maxN+1):
        buf = A[i]*n
        remove_list.append(buf)
            #print(A[i]*n)

#target = kouho[:]
kouho = list(set(kouho) - set(remove_list))

print(len(kouho))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False
        
ans = 0
for i in range(n):
    if flg[a[i]]:
        ans += 1

    tmp = 1
    while tmp * a[i] <= 10 ** 6:
        flg[tmp * a[i]] = False
        tmp += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import collections


def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return sorted(table)

N = int(input())
A = [int(a) for a in input().split()]
L = collections.Counter(A)

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

print(ans)

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n = I()
mylist = sorted(list(MI()))
max_num = int(math.sqrt(mylist[n-1]))
start = mylist[0]
input_list = [0] * n
index = 0

while len(mylist) >= 1:
    temp = mylist.pop(0)
    if not(temp in mylist):
        index += 1
    for j in set(mylist):
        if j % temp == 0:
            while j in mylist:
                mylist.remove(j)
print(index)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
dp = [0] * (max(A)+1)

for i in range(N):
    if dp[A[i]] == 0:
        dp[A[i]] = 1
        for j in range(i+1, N):
            if dp[A[j]] != 2 and A[j] % A[i] == 0:
                dp[A[j]] = 2
print(dp.count(1))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))

def heapsort(iterable):
  h = []
  for value in iterable:
    heapq.heappush(h, value)
  l = []
  for _ in range(len(h)):
    l.append(heapq.heappop(h))
  return l

n = ri()
li = rl()
dic = {}
for w in li:
    if w in dic:
        dic[w] += 1
    else:
        dic[w] = 1
li1 = []
li2 = []
for k, v in dic.items():
    if v > 1:
        li1.append(k)
    else:
        li2.append(k)
li1 = heapsort(li1)
li2 = heapsort(li2)
le1 = len(li1)
le2 = len(li2)
cnt = 0
for i in range(le2):
    li2i = li2[i]
    for j in range(i):
        li2j = li2[j]
        if li2j > li2i*0.5:
            for k in range(le1):
                li1k = li1[k]
                if li1k > li2i*0.5:
                    cnt += 1
                    break
                if li2i % li1k == 0:
                    break
            else:
                cnt += 1
            break
        if li2i % li2j == 0:
            break
    else:
        for k in range(le1):
            li1k = li1[k]
            if li1k > li2i*0.5:
                cnt += 1
                break
            if li2i % li1k == 0:
                break
        else:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline

def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return sorted(table)

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:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
dp = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    e = x * 2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    # 重複なし and 約数なし 
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

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

# 0 ~ 10**6のリスト
A_list = [True for i in range(10**6+1)]
# 倍数のところにFalseを入れる
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# 0 ~ 10**6に入力値の個数を入れる
# (count()で数えると、o(n**2)になるため)
val_list = [0 for i in range(10**6+1)]
for i in a_l:
	val_list[i] += 1

# Trueと一致するa_lの個数を数える
cnt = 0
for i in a_l:
	if(val_list[i] != 1):
		continue
	if(A_list[i]):
		cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = set(A)
B = dict(Counter(A))
ans = 0
for i in range(N):
    if B[A[i]] > 1:
        pass
    else:
        flag = True
        for j in range(1, A[i]+1):
            if j**2 > A[i]:
                break
            if A[i] % j == 0:
                if A[i]//j in C:
                    if A[i]//j < A[i]:
                        flag = False
                        break
                if j in C:
                    if j < A[i]:
                        flag = False
                        break

        ans += int(flag)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
dp = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    e = x * 2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    # 重複なし and 約数なし
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

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

M = 10**6 + 1
cnt = [0]*M

for a in A:
    for i in range(M)[a::a]:
        cnt[i] += 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
dp = [0] * (max(A)+1)

for i in range(N):
    if dp[A[i]] == 0:
        dp[A[i]] = 1
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                dp[A[j]] = 2
print(dp.count(1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = list(set(a))
dp = [True] * (10**6+1)
for x in s:
    e = x*2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x
ret = 0
for x in a:
    # 重複なし and 約数なし
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
def divisors(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return sorted(table)

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:
N = int(input())
A = list(map(int,input().split()))
B = [0]*(max(A))

for i in A:
    B[i-1] += 1

ans = 0
for i in sorted(A):
    if B[i-1] == 0:
        continue
    if B[i-1] == 1:
        ans += 1
    for j in range(i,max(A)+1,i):
        B[j-1] = 0

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
 
input()
c = Counter(map(int, input().split()))
r = int(c[1] == 1)
if c[1] == 0:
  for k, v in c.items():
    if v == 1:
      i = 2
      while i * i <= k and (k % i or c[i] == c[k // i] == 0):
        i += 1
      if i * i > k:
        r += 1
print(r)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[1]*n
    a.sort()
    ans=0
    for i in range(n):
        if b[i]==1:
            for j in range(i+1,n):
                if b[j]==1:
                    if a[j]%a[i]==0:
                        b[j]=0
                        if a[j]==a[i]:
                          b[i]=0
    print(sum(b))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())
a = list(map(int, input().split()))
size = max(a)
a.sort()
a2 = copy.copy(a)
b = [0] * (size + 1)
while a:
    test = a.pop(0)
    count = 1
    if not a:
        pass
    else:
        while a[0] == test:
            a.pop(0)
            count += 1
            if not a:
                break
    for i in range(size // test):
        b[test * (i + 1)] += count
ans = 0
for i in range(n):
    if b[a2[i]] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = a=int(input())
listP=[]
while True:
    try:
        listP=list(map(int,input().split()))
    except:
        break;
        
listTF=[1]*N
listP.sort()
for i in range(N):
  if listTF[i]==0:
    break
  for j in range(N):
    if (i!=j) and (listP[i]%listP[j]==0):
      listTF[i]=0

print(len([i for i in listTF if i > 0]))

Submission status: Time Limit Exceeded

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

count = 0

for i in range(1, n+1):
    a_i = A[i-1]
    state = "yes"
    for j in range(1, n+1):
        a_j = A[j-1]
        if i == j:
            continue
        if a_i%a_j == 0:
            state = "no"
            break
    if state == "yes":
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[1]*n
    a.sort()
    ans=0
    for i in range(n):
        if b[i]!=0:
            for j in range(i+1,n):
                if a[j]%a[i]==0:
                    b[j]=0
                    if a[j]==a[i]:
                        b[i]=0
    print(sum(b))
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
s = list (set(a))
dp = [True] * (10**6+1)

for x in s:
    e = x*2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x

ret = 0
for x in a:
    # 重複なし かつ 素数
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def make_divisors(n):
    l_divs, u_divs = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            l_divs.append(i)
            if i != n // i:
                u_divs.append(n // i)
        i += 1
    return l_divs + u_divs[::-1]


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

    past = set()
    ans = 0
    ansset = set()
    for a in aset:
        divs = make_divisors(a)
        for div in divs:
            if div in past:
                break
        else:
            ansset.add(a)
            ans += 1

        past.add(a)

    c = collections.Counter(A)
    for cc in c.most_common():
        if cc[1] == 1:
            break

        if cc[1] > 1 and cc[0] in ansset:
            ans -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = sorted(list(map(int,input().split())),reverse=True)
c = Counter(a)
s = list (set(a))
dp = [True] * (10**6+1)

for x in s:
    e = x*2
    # エラトステネスの篩
    while e <= 10 ** 6:
        dp[e] = False
        e += x

ret = 0
for x in a:
    # 重複なし かつ 素数
    if c[x] == 1 and dp[x] == True:
        ret += 1
print(ret)

Submission status: Time Limit Exceeded

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

for i in A:
    B[i-1] += 1

ans = 0
C = set()
for i in sorted(set(A)):
    if i in C:
        continue
    if B[i-1] == 1:
        ans += 1
    for j in range(2 * i,max(A)+1,i):
        if B[j-1]:
            C.add(j)
            B[j-1] = 0

print(ans)

Submission status: Time Limit Exceeded

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

dp=[False]*(a[-1]+1)
for x in a:
  dp[x]=True
for x in a:
  i=1 if a.count(x)>1 else 2
  while x*i<len(dp):
    dp[x*i]=False
    i+=1
print(sum(dp))

Submission status: Time Limit Exceeded

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 0
    max_a = max(a)
    arr = [1] * (max_a + 1)

    for num in a:
        if a.count(num) > 1:
            arr[num] = 0
        for i in range(num*2, max_a+1, num):
            arr[i] = 0

    for i in range(n):
        if arr[a[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()