Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
num_list = list( map( int, input().split() ) )
Amax = max(num_list)

dp = np.ones( (Amax+1,), dtype=np.bool8 )
dp2 = np.zeros( (Amax+1,) )

for i in range(Amax+1):
    if i in num_list:
        for j in range(i+i, Amax+1, i):
            dp[j] = False

for i in num_list:
    if dp[i]:
        dp2[i] += 1

print( sum(dp2 == 1) )

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = np.zeros(max(A) + 5)
for i in range(N):
  if ans[A[i]] == 0:
    for j in range(0, max(A) + 5, A[i]):
      ans[j] += 1
  else:
    ans[A[i]] += 1
cnt = 0
for a in A:
  if ans[a] == 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_maxのbool配列dpを用意し、trueで初期化する
A_max = max(A)
dp = [True] * (A_max + 1)
calculated = {}

# 数列の要素を昇順に見る O(nloglogn)
for x in range(A_max):
    # すでに計算していれば再度計算しない
    if x in calculated:
        continue
    # xが数列Aに含まれているとき、xより大きいxの倍数yについて、dp[y]をfalseに変更する
    if x in A:
        calculated[x] = True
        t = 2
        while x * t <= A_max:
            dp[x * t] = False
            t += 1

# 同じ値が複数存在するかチェックする用のカウンタ
C = {a: 0 for a in A}
for a in A:
    C[a] += 1

ans = 0
for a in A:
    if C[a] == 1 and dp[a] is True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = [0 for _ in range(max(A) + 5)]
for i in range(N):
  if ans[A[i]] == 0:
    for j in range(0, max(A) + 5, A[i]):
      ans[j] += 1
  else:
    ans[A[i]] += 1
cnt = 0
for a in A:
  if ans[a] == 1:
    cnt += 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):
  flg = True
  for j in range(n):
    if i is not j and flg:
      if a[i] % a[j] is 0:
        flg = False

  if flg:
    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_maxのbool配列dpを用意し、trueで初期化する
A_max = max(A)
dp = [True] * (A_max + 1)
 
# 数列の要素を昇順に見る O(nloglogn)
for x in range(A_max):
    # すでに計算していれば再度計算しない
    if not dp[x]:
        continue
    # xが数列Aに含まれているとき、xより大きいxの倍数yについて、dp[y]をfalseに変更する
    if x in A:
        t = 2
        while x * t <= A_max:
            dp[x * t] = False
            t += 1
 
# 同じ値が複数存在するかチェックする用のカウンタ
C = {a: 0 for a in A}
for a in A:
    C[a] += 1
 
ans = 0
for a in A:
    if C[a] == 1 and dp[a] is True:
        ans += 1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
mapped_list = map(int,input().split())
list = list(mapped_list)
answer = 0
for i in range (N):
  count = 0
  for j in range (N):
    s = list[i]
    t = list[j]
    if j != i :
      if s % t == 0:
        count = count+1
  if count == 0:
    answer = answer+1
print (answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    for i in range(2*val,a[n-1]+1,val):
        dp[i-1]=False
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

# サイズA_maxのbool配列dpを用意し、trueで初期化する
A_max = max(A)
dp = [True] * (A_max + 1)

# 数列の要素を昇順に見る O(nloglogn)
for x in range(A_max):
    # すでに計算していれば再度計算しない
    if not dp[x]:
        continue
    # xが数列Aに含まれているとき、xより大きいxの倍数yについて、dp[y]をfalseに変更する
    if x in A:
        t = 2
        while x * t <= A_max:
            dp[x * t] = False
            t += 1

# 同じ値が複数存在するかチェックする用のカウンタ
C = {a: 0 for a in A}
for a in A:
    C[a] += 1

ans = 0
for a in A:
    if C[a] == 1 and dp[a] is True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

l=[]
d=collections.Counter(a)
count=0

for i in list(set(a)):
    c=0
    d[i]-=1
    if d[i]==0:
        del d[i]
    for j in range(1,math.floor(math.sqrt(i))+1):
        if i%j==0:
            if j in d:
                c=1
                break
            if i%(i//j)==0:
                if (i//j) in d:
                    c=1
                    break
    
    if c==0:
        count+=1
    if i not in d:
        d[i]=1
    else:
        d[i]+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True for _ in range(a[n-1])]
for val in set(a):
    temp=2
    while val*temp<=a[n-1]:
        dp[val*temp-1]=False
        temp+=1
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=list(map(int,input().split()))
a.sort()
dp = [True]*(a[n-1])
for val in set(a):
    temp=2
    while val*temp<=a[n-1]:
        dp[val*temp-1]=False
        temp+=1
ans = 0
for val in a:
    if dp[val-1] and a.count(val)==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

# サイズA_maxのbool配列dpを用意し、trueで初期化する
A_max = max(A)
dp = [True] * (A_max + 1)

# 数列の要素を昇順に見る O(nloglogn)
for x in range(A_max):
    # すでに計算していれば再度計算しない
    if not dp[x]:
        continue
    # xが数列Aに含まれているとき、xより大きいxの倍数yについて、dp[y]をfalseに変更する
    if x in A:
        t = 2
        while x * t <= A_max:
            dp[x * t] = False
            t += 1

# 同じ値が複数存在するかチェックする用のカウンタ
counter = Counter(A)

ans = 0
for a in A:
    if counter[a] == 1 and dp[a] is True:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(N)]

A.sort()

for i in range(N):
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
cnt = 0
for i in range(N):
    if dp[i] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

l=[]
d=collections.Counter(a)
count=0

for i in range(n):
    c=0
    d[a[i]]-=1
    if d[a[i]]==0:
        del d[a[i]]
    for j in range(1,math.floor(math.sqrt(a[i]))+1):
        if a[i]%j==0:
            if j in d:
                c=1
                break
            if a[i]%(a[i]//j)==0:
                if (a[i]//j) in d:
                    c=1
                    break
    
    if c==0:
        count+=1
    if a[i] not in d:
        d[a[i]]=1
    else:
        d[a[i]]+=1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
n=int(input())
l=list(map(int,input().split()))
from math import sqrt
ans=0
import collections
c=collections.Counter(l)
if c[1]==1:
    print(1)
    quit()
elif c[1]>1:
    print(0)
    quit()
for i in l:
    if c[i]>1:
        continue
    for j in range(2,int(sqrt(i))+1):
        if i%j==0:
            if j in c or i//j in c:
                break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
def Yes(x):print("Yes")if x==True else print("No")
n=N()
l=L()
from math import sqrt
ans=0
import collections
c=collections.Counter(l)
if c[1]==1:
    print(1)
    quit()
elif c[1]>1:
    print(0)
    quit()
for i in l:
    if c[i]>1:
        continue
    for j in range(2,int(sqrt(i))+1):
        if i%j==0:
            if c[j] or c[i//j]:
                break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(n):
  flg = 0
  for j in range(n):
    if i is not j and a[i] % a[j] is not 0:
      flg += 1
  
  if flg is n - 1:
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import math
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
an = [list(map(int, input().split()))]
an_n = np.array(an).reshape(-1)
an_n2 = np.array(an).reshape(-1)
cnt = 0
for i, num in enumerate(an_n):
    an_a = np.where(an_n % num == 0)
    t = an_a[0]
    if len(t) > 1:
        ab = an_n2[i]
        an_n2[t] = 0
        an_n2[i] = ab
rs = np.where(an_n2 != 0)
rs_0 = rs[0]
print(len(rs_0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter


def solve(N: int, A: "List[int]"):
    c = Counter(A)
    a = sorted(list(set(A)))
    dp = [True] * (max(A) + 7)
    for i in a:
        if dp[i]:
            for j in range(2, max(A) // i + 1):
                dp[i * j] = False
    # print(dp)
    print(len([x for x in A if dp[x] and c[x] == 1]))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 = list(map(int, input().split()))
dp = [0 for _ in range(N)]

A.sort()

for i in range(N):
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if dp[j] < 2 and A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
cnt = 0
for i in range(N):
    if dp[i] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0;p=l[-1]
if l[0]==1:
  print(1 if n==1 else int(l[1]!=1));exit()
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  for j in range(x,p+1,x):
  	g[j]=1
  if f and (i!=n-1 and l[i+1]!=l[i]):
    an+=1
  elif f and i==n-1:
    an+=1
print(an)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(N)]

A.sort()

for i in range(N):
    if dp[i] < 2:
        p = A[i]
        for j in range(N):
            if A[j]%p == 0 and A[j] >= p:
                dp[j] += 1
cnt = 0
for i in range(N):
    if dp[i] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  g[x]=1
  if f and (i!=n-1 and l[i+1]!=l[i]):
    an+=1
  elif f and i==n-1:
    an+=1
print(an)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N=int(input())
  A=list(map(int,input().split()))
  x=0
  for i in range(N):
    for j in range(N):
      if i==j:
        pass
      elif A[i]%A[j]==0:
        break
    else:
      x+=1
  print(x)
main()

Submission status: Time Limit Exceeded

Solution code:
I = lambda :list(map(int,input().split()))

n,=I()
l = sorted(I())
g=[0]*(10**6+1)
an=0
for i in range(n):
  x=l[i];f=1
  for j in range(1,int(x**0.5)+1):
    if x%j==0:
      if g[j] or g[x//j]:
        f=0;break
  g[x]=1
  if f and (i!=n-1 and l[i+1]!=l[i]):
    an+=1
  elif f and i==n-1:
    an+=1
print(an)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
l = 0
for i in range(n):
  for j in range(n):
    if s.count(s[i]) > 1:
      l += 1
      break
    if s[i]%s[j] == 0 and (i != j):
      l += 1
      break
print(len(s)-l)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

a.sort()

if n > 1:
    if a[0] == a[1]:
        ans = 0
    else:
        ans = 1
else:
    print(1)
    exit()

for i in range(1,n):
    flag = True
    for j in range(i):
        if a[i] % a[j] == 0:
            flag = False
            break
        if int(a[i]//2)+1 < a[j]:  
            break
    if i == n-1:
        if flag and a[i] != a[i-1]:
            ans += 1
    else:
        if flag and a[i] != a[i-1] and a[i] != a[i+1]:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
table = [True for _ in range(10 ** 7)]
a.sort()
ans = 0
for i in range(n):
    if table[a[i]]:
        for j in range(a[i], 10 ** 7, a[i]):
            table[j] = False
        if i + 1 < n:
            if a[i + 1] != a[i]:
                ans += 1
        elif i + 1 == n:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


# a.sort()

if 1 in a:
# if a[0] == 1:
  # if len(a) > 1 and a[1] == 1:
  #   print(0)
  # else:
  #   print(1)
  
  # if collections.Counter(a)[1]==1:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)

  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

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

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
        break
    if not valid:
      break
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def main():
    MOD = 10**9+7
    n = int(input())
    A = list(map(int,input().split()))

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

    for a in A:
        c = 2
        while a*c <= max(A):
            dp[a*c] = False
            c += 1
    

    d = defaultdict(int)

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

    ans = 0
    for a in A:
        if dp[a] == True and d[a]==1:
            ans += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


a.sort()

# if 1 in a:
if a[0] == 1:
  if len(a) > 1 and a[1] == 1:
    print(0)
  else:
    print(1)
  # if a.count(1) == 1:
  # if collections.Counter(a)[1]==1:
  #   print(1)
  # else:
  #   print(0)

  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

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

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Time Limit Exceeded

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


def solve(N, A):
    A = sorted(A)
    dp = [True for i in range(max(A))]

    for i, a in enumerate(A):
        if dp[a-1] == False:
            continue
        elif dp[a-1] == True:
            for k in range(2, max(A)//a+1):
                dp[a * k - 1] = False
        if i < N-1 and A[i] == A[i+1]:
            dp[a-1] = False

    count = 0
    for a in A:
        if dp[a-1] == True:
            count += 1
    print(count)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

# a.sort()

cCa=collections.Counter(a)

if 1 in a:
  # if a.count(1) == 1:
  if cCa[1]==1:
    print(1)
  else:
    print(0)
  
  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

a = [k for k, v in cCa.items() if v == 1]

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Time Limit Exceeded

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


def solve(N, A):
    A = sorted(A)
    dp = [True for i in range(max(A))]

    for i, a in enumerate(A):
        if dp[a-1] == True:
            for k in range(2, max(A)//a+1):
                dp[a * k - 1] = False
        if i < N-1 and A[i] == A[i+1]:
            dp[a-1] = False

    count = 0
    for a in A:
        if dp[a-1] == True:
            count += 1
    print(count)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

# a.sort()

if 1 in a:
  # if a.count(1) == 1:
  if collections.Counter(a)[1]==1:
    print(1)
  else:
    print(0)
  
  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

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

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  i = 2
  if Adic[temp] >= 2:
    continue
  while i*i <= temp:
    #print(i,temp)
    if temp%i == 0:
      #print(i,temp//i,temp)
      if i in Aset or temp//i in Aset:
        Flag = False
        #print(i,temp//i,"X")
        break
    i += 1
  if not Flag:
    continue
  ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
l = 0
for i in range(n):
  for j in range(n):
    if (s[i] == s[j] or s[i]%s[j] == 0) and (i != j):
      l += 1
      break
print(len(s)-l)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Alist = list(map(int,input().split(" ")))
ansList = list(range(N))
count = 0
for i in range(N):
    flag = False
    for j in range(N):
        if i != j:
            if (Alist[i]%Alist[j]==0):
                flag = True
    if flag==False:
        count+=1


print(count)

Submission status: Time Limit Exceeded

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


def solve(N, A):
    A = sorted(A)
    dp = [True for i in range(N)]  # Trueのものは、割り切れない（カウント対象）
    true_idx_set = set([i for i in range(N)])

    for i, a in enumerate(A):
        if not dp[i]:
            continue

        elif A.count(a) > 1:  # 同じ値が複数入っていたら、その値はカウント対象外
            dp[i] = False
            true_idx_set.remove(i)
            continue

        tmp_set = [x for x in true_idx_set if x>i]
        for idx in tmp_set:
            if A[idx] % a == 0:
                dp[idx] = False
                true_idx_set.remove(idx)

    count = 0
    for i in range(N):
        if dp[i] == True:
            count += 1
    print(count)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
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()
a.sort()

max_a = 10**6
ans = [[0,0] for i in range(max_a+1)]

for i in a:
	ans[i][0]+=1
	ans[i][1]+=1
for i in set(a):
	if ans[i][1]>0:
		for j in range(i*2,len(ans),i):
			ans[j][0]+=2

count = 0
for i in ans:
	if i[1]>0 and i[0]==1:
		count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections
from functools import lru_cache

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/

@lru_cache(maxsize=None)
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


if 1 in a:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)
  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

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

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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


# https://note.nkmk.me/python-prime-factorization/


def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a


if 1 in a:
  if a.count(1) == 1:
    print(1)
  else:
    print(0)
  # print(int(a.count(1)==1))
  exit()

# a=set(a)

dprint('a', '=', a)

p = {tuple(prime_factorize(e)) for e in a}

# p.sort()

dprint('p', '=', p)

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

ans = 0
for e in a:
  f = tuple(prime_factorize(e))
  dprint('f', '=', f)
  # if len(f) == 1:
  #   ans += 1
  #   dprint('ans++', f)
  #   continue
  valid = True
  for r in range(1, len(f) + 1):
    dprint('r', '=', r)
    for com in itertools.combinations(f, r=r):
      dprint(com)
      if com == f:
        continue
      # if p[bisect.bisect_left(p, com)] == com:
      if com in p:
        valid = False
  if valid:
    ans += 1
    dprint('ans++', f)

print(ans)

Submission status: Time Limit Exceeded

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

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

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