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 sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)

isprime = {a[i]:True for i in range(n)}

for i in range(n):
    if a[i] > a[-1]//2: break 
    if not isprime[a[i]]: continue
    for j in range(2, a[-1]//a[i]+1):
        if a[i]*j in a:
            isprime[a[i]*j] = False

diff = len([i for i in range(len(c)) if list(c.values())[i] != 1 and isprime[list(c.keys())[i]]])
print(list(isprime.values()).count(True)-diff)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[0 for _ in range(n)]

a.sort()

for i in range(n):
    for j in range(n):
        if a.count(a[i])>=2:
            l[i]=1
            break
        if ((a[i]//2)<a[j]):
            break
        if a[i]%a[j]==0:
            l[i]=1
            break

cnt=l.count(0)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    A_dict = {}
    for a in A:
        if a in A_dict.keys():
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    black_list = []
    ans = 0
    for a in sorted(A_dict.keys()):
        for b in black_list:
            if a % b == 0:
                break
        else:
            if A_dict[a] == 1:
                ans += 1
            black_list.append(a)
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate
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)

    return divisors

def solve():
    N = II()
    A = LI()

    cost = {}
    for a in A:
        if cost.get(a, -1) == -1:
            cost[a] = 1
        else:
            cost[a] = 0

    A = sorted(A)

    memo = {}
    ans = 0
    for a in A:
        for i in range(1, int(a ** 0.5) + 1):
            if a % i: continue
            if memo.get(i, -1) != -1 or memo.get(a//i, -1) != -1:
                break
        else:
            ans += cost[a]

        memo[a] = 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
mod0 = [True] * N
for i in range(N):
    if not mod0[i]:
        continue
    for j in range(1,N - i):
        if not mod0[i+j]:
            continue
        elif A[i + j] % A[i] == 0:
            mod0[i + j] = False
cnt = 0
for i in range(N):
    if mod0[i]:
        cnt += 1
        if i < N-1 and A[i] == A[i+1]:
            cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict
import copy
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
a = list(map(int, input().split()))
ans = 0
times = defaultdict(int)
for k in a:
    times[k] += 1
for j in a:
    if times[j] > 1:
        continue
    tmp = set(a)
    # tmp.remove(j)
    table_ = make_divisors(j)
    for i in table_:
        if i == j:
            continue
        if i in tmp:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
import copy
A_list_2 = copy.deepcopy(A_list)



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
  
  
list_ = []
list_list =[]
for i in range(N):
  list_ = make_divisors(A_list[i])
  list_list.append(list_)
  
  
  
  
  
count = 0
and_ = []
a =[]


for i in range(N):
  #約数
  A_list = copy.deepcopy(A_list_2)
  #print(A_list)
  #a = make_divisors(A_list[i])
  #a.pop(len(a)-1)
  #約数とA_listの共通点
  A_list.pop(i)
  and_ = list(set(A_list) & set(list_list[i]))
  #共通がなかったら(len==0)割り切れない
  if(len(and_)==0):
    count += 1
    #print(i,a,and_)
    
    
print(count)

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):
        if li2i % li2[j] == 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:
N = int(input())
A = list(map(int,input().split()))

ans = 0
for i in range(N):
  j_flag = True
  for j in range(N):
    if not j_flag:
      pass
    elif i == j:
      pass
    elif A[i] % A[j] == 0:
      j_flag = False
  if j_flag:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

import collections
c = collections.Counter(a)

d=[]
for ck,cv in c.items():
    if cv>=2:
       d.append(ck) 
dset=set(d)
    
#aa=[]
aaset=set()
#icnt=0
while True:
    aaset.add(a[0])
#    aa.append(a[0])
    a2=[]
#    for i in range(1,len(a)):
    for i,ai in enumerate(a,1):
        if ai%a[0]!=0:
            a2.append(ai)
    a=a2.copy()
#    print(aa,a)     
    if len(a2)==0:
        break
#    icnt+=1
#    if icnt>10:break

#aaset=set(aa)
aaset=aaset-dset    
print(len(aaset))

Submission status: Time Limit Exceeded

Solution code:
# 出現した数のフラグを立てればよいだけでは
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
happend = set()
A.sort()
ans = 0

for val in A:
    if count[val] >= 2:
        ans += 1
        happend.add(val)
        continue
    for j in range(1, int(val**(1/2))+1):
        if val % j == 0 and (j in happend or val//j in happend):
            ans += 1
            break
    happend.add(val)

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    A.sort()
    one_num = len(list(filter(lambda a: a == 1, A)))
    if one_num == 1:
        print(1)
        return
    elif one_num >= 2:
        print(0)
        return
    nums = list()
    for a in A:
        is_target = True
        for n in nums:
            if a % n == 0:
                is_target = False
                break
            if a // 2 < n:
                break
        if is_target:
            nums.append(a)
    print(len(list(filter(lambda n: counter[n] == 1, nums))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
listA = list(map(int,input().split()))
listA.sort()
cnt = 0
for i in range(n):
    a=0
    for j in listA:
        if listA[i]%j==0:
            a+=1
            if a>1:
                break;
    if a==1:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
*A, = map(int, input().split())
A.sort()
a = []
b = []
last = 0
for i in range(N):
    if last != A[i]:
        a.append([A[i], 0])
        b.append(A[i])
        last = A[i]
    a[-1][1] += 1


def factorList(n):
    # [素因数]=数を出力
    f = {}
    c = 0
    r = int(n**0.5)
    l = []
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            l.append([i, c])
            c = 0
    if n != 1:
        l.append([n, 1])
    return l


def cmb(a, i, h, t):
    if i >= len(a):
        return h[t]
    for j in range(a[i][1]+1):
        d = cmb(a, i+1, h, t*pow(a[i][0], j))
        if d:
            return True
    return False


h = [False]*(10**6+1)
ans = 0
for n, c in a:
    if c == 1:
        fl = factorList(n)
        if not cmb(fl, 0, h, 1):
            ans += 1
    h[n] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
count = 0
bl = []
for i in range(n):
    t = a[i]
    count+=1
    if i+1!=n:
        if t==a[i+1]:
            count-=1
            bl.append(i)
            continue
    if i!=0:
        if t==a[i-1]:
            count-=1
            bl.append(i)
            continue
    for j in range(i):
        if j in bl: continue
        if t%a[j]==0:
            count-=1
            bl.append(i)
            break
print(count)

Submission status: Time Limit Exceeded

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

if a[0]==1:
    if n>=2 and a[1]==1:
        print(0)
    else:
        print(1)
else:
    ans = 0
    for num in a:
        if a.count(num) >= 2:
            continue
        else:
            cands = set([i for i in a if i!=num])
            for i in range(2, int(num**0.5)+1):
                if num % i == 0 and (i in cands or num//i in cands):
                    break
            else:
                ans+=1
            
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import chain


def prime_set(N):
    """
    Nまでの素数のsetを返す
    """
    if N < 4:
        return ({}, {}, {2}, {2, 3})[N]
    Nsq = int(N ** 0.5 + 0.5) + 1
    primes = {2, 3} | set(chain(range(5, N + 1, 6), range(7, N + 1, 6)))
    for i in range(5, Nsq, 2):
        if i in primes:
            primes -= set(range(i * i, N + 1, i * 2))
    return primes


N = int(input())
A = list(map(int, input().split()))
prime = prime_set(10 ** 6 + 1)


C = Counter(A)
if C[1] == 1:
    print(1)
    exit()
if C[1] >= 2:
    print(0)
    exit()

ans = 0
for a, v in C.items():
    if v >= 2:
        ans += v
        continue
    if a in prime:
        continue
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            if C[i] > 0:
                ans += 1
                break
            if C[a // i] > 0:
                ans += 1
                break

print(N-ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

A_sort = sorted(set(A))
A_counter = Counter(A)
# print(A_sort)

res = 0
# res_list = []
for i in range(len(A_sort)):
    # print(A_sort[i], A_sort_tmp)
    if A_counter[A_sort[i]] >= 2:
        continue

    A_sort_tmp = A_sort[:i]
    for j in range(len(A_sort_tmp)):
        if A_sort[i] % A_sort_tmp[j] == 0:
            break
    else:
        res += 1
        # res_list.append(i + 1)

print(res)
# print(res_list)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
import sys
def solve():
    N = int(input())
    A = list(map(int,sys.stdin.readline().split()))

    counter = Counter(A)

    ans = 0
    for i in range(N):
        if counter[A[i]] >= 2:
            continue
        divisors = calc_divisors(A[i])
        for divisor in divisors:
            if divisor == A[i]:
                continue
            if counter[divisor] > 0:
                break
        else:
            ans += 1
    
    print(ans)

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

    return divisors

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
r=0
import numpy as np
while len(a)>0:
  if len(a)==1:
    a.pop(0)
    r+=1
  else:
    #for jj in np.arange(1,len(a)):
    for jj in range(len(a)-1,0,-1):
      a0=a[0]
      if a0%a[jj]==0:
        while a[0]==a0:
          a.pop(0)
          if len(a)<=0:
            break
        break
      if jj==1:
        a.pop(0)
        r+=1
    #print(a0,r)
print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
tmp = []
flag = [0]*N
for i in range(N):
    f = 0
    for j in range(N):
        if i == j:
            continue
        else:
            if A[i]%A[j]==0:
                f=1
                break
    if f == 0:
        ans += 1
    

print(ans)
# print(tmp)
# print(flag)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())

nums=np.array([int(s) for s in input().split()])

nums.sort()

for i,n in enumerate(nums):
  ls=[]
  for j in range(len(nums)-i-1):
    if nums[i+j+1] % nums[i]==0:
      ls.append(nums[i+j+1])
  for t in ls:
  	nums=np.delete(nums, np.where(nums == t)[0])
  if len(nums)<=i:
    break
print(len(nums))

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
count = 0
if(n == 1):
  print(1)
  sys.exit()
for i in range(1,n):
  if(a.count(a[i]) >= 2):
    continue
  flg = False
  for j in range(i):
    if(a[i] % a[j] == 0):
      flg = True
      break
  if(flg == False):
    count += 1

if(a[0] != a[1]):
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import collections
import sys
ACMOD = 1000000007
INF = 1 << 62


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 2
    while i * i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1
    # return lower_divisors + upper_divisors[::-1]


def solve(A):
    ans = 0
    c = collections.Counter(A)
    # dupes = {k for k, v in c.items() if v > 1}
    dupes = set()
    for k, v in c.items():
        if v > 1:
            dupes.add(k)
    if 1 in c:
        print(int(1 not in dupes))
        return
    aset = set(A)
    for a in A:
        if a in dupes:
            continue
        for v in ((make_divisors(a))):
            if v in aset:
                break
        else:
            ans += 1
    print(ans)
    return


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input())):
n=int(input())
l=[int(x) for x in input().split()]
v=set()
l.sort()
d={}
for i in range(n):
	if l[i] in d:
		d[l[i]]+=1
	else:
		d[l[i]]=1

ans=0
for i in range(n):
	c=0
	if l[i]==-1:
		continue
	for j in range(n):
		if i==j:
			continue
		if l[j]%l[i]==0:
			l[j]=-1
	if d[l[i]]>1:
		l[i]=-1
c=0
for i in range(n):
	if l[i]!=-1:
		ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
nlist = list(map(int, input().split()))

perm = list(itertools.permutations(nlist, 2))
ref = []
tmp = []
for num, j in enumerate(perm):
    tmp.append(j[0] % j[1])
    if (num + 1) % (len(nlist) - 1) == 0:
        ref.append(tmp)
        tmp = []
check = 0
for ind, i in enumerate(ref):
    if 0 in i:
        check += 1

print(len(nlist) - check)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    l = [int(x) for x in input().split()]
    dict={}
    l = sorted(l)
    L=[l[0]]
    for i in range(1,N):
        for j in L:
            if l[i]%j==0:
                if l[i]==j:
                    dict[j]=0
                break
        else:
           # print("i",i)
            L.append(l[i])

    print(len(L)-len(dict))
    
main()

Submission status: Time Limit Exceeded

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

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

d = [0 for i in range(max(a)+1)]
for i in range(N):
    d[a[i]] += 1
ans = 0

for i in range(N):
    divisors = make_divisors(a[i])
    flag = 1
    d[a[i]] -= 1
    for d_temp in divisors:
        if d[d_temp] > 0:
            flag = 0
            break
    ans += flag
    d[a[i]] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from fractions import gcd
#from itertools import combinations # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = sorted(readInts())
dic = defaultdict(int)
cnt = 0

# ------------
is_prime = [True] * (10**6+1)
#print('a')
for i in range(n):
    #ll += 1
    #print(i)
    if is_prime[A[i]] == True:
        for j in range(2*A[i], 10**6+1,A[i]):
            is_prime[j] = False # その素数の倍数のやつ

 # -----------
for i in A:
    dic[i] += 1
cnt = 0
if A[0] == 1:
    if dic[1] >= 2:
        print(0)
        exit()
    else:    
        print(1)
        exit()
for a in A:
    if is_prime[a] and not dic[a] >= 2:
        #print(a)
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

def main():
  from collections import Counter
  n = int(input())
  A = list(map(int, input().split()))
  C = Counter(A)
  def f(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)
      return divisors

  ans = 0
  for a in A:
      for j in f(a):
          if j == a:
              if C[j] > 1:
                  break
          else:
              if C[j] > 0:
                  break
      else:
          ans += 1
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
p = [int(x) for x in input().split()]

p=sorted(p, reverse=True)
cnt = 0
for i in range(N):
    if p.count(p[i])>1:
        continue
    flg = 0
    for j in range(i+1,N):
        if p[i]%p[j] == 0:
            flg=1
            break
    if flg==0:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

A.sort()

X = {i:A[i] for i in range(N)}

for i in range(N):
    Ai = A[i]
    for key in list(X):
        if i != key and X[key] % Ai == 0:
            del X[key]
print(len(X))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=sorted(list(map(int,input().split(" "))))
g=0

for i in range(n):
  if A.count(A[i])>=2:
      g=g+1
  else:
    for j in range(i):
      if A[i]%A[j]==0:
        g=g+1
        break
      j=j+1
print(n-g)

Submission status: Time Limit Exceeded

Solution code:
def divisor(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 table


n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
cnt = 0
for i in a:
    flag = True
    for j in divisor(i):
        if j in a[a.index(i) + 1:]:
            flag = False
    if flag:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split())) 
A=sorted(A)
N=len(A)
A_ok=[True]*N
for i in range(N):
    if(A_ok[i]):
        for j in range(i+1,N):
            if(A_ok[j]):
                if(A[j]%A[i]==0):
                    A_ok[j]=False
                if(A[j]==A[i]):
                    A_ok[i]=False
ans=0
for i in range(N):
    if(A_ok[i]):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

d = list(map(int,input().split()))
a = np.array(list(map(int,input().split())))


ansindex = []
cnt = 0
for var in range(0, len(a)):
    new_list = np.delete(a, var)
    #Sprint(a[var])
    #print(new_list%a[var])
    resp = new_list%a[var]
    basis = np.insert(resp,var,a[var])
    #print(basis)
    found = np.where(basis == 0)
    #modが0になったところをさがす
    #print(basis)


    for fd in range(0, len(found)):
        #ある一つの数字で割った結果について
        f = found[fd]
        #print(f)
        for ff in f:
            #print(f)
            if ff not in ansindex:
                ansindex.append(ff)
            else:
                continue


#print(ansindex)
print(int(d[0]) - len(ansindex))

Submission status: Time Limit Exceeded

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    #rootA=math.sqrt(ListA[i])
    MaxVal=ListA[i]/factorization(ListA[i])[0][0]

    # if(ListA[i]%2==0):
    #     Maxval=ListA[i]/2
    # if(ListA[i]%3==0):
    #     Maxval=ListA[i]/3
    # if(ListA[i]%5==0):
    #     Maxval=ListA[i]/5
    # if(ListA[i]%7==0):
    #     Maxval=ListA[i]/7


    for j in range(i):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>MaxVal):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10**5)

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

ans = 0
def func(c, q):
    global ans
    if c == 0:
        return 
    if c == 1:
        ans += 1
        return
    new_c = 0
    new_q = deque()
    if q[0] != q[1]:
        ans += 1
    a_i = q[0]
    for a_j in q:
        if a_j % a_i != 0:
            new_q.append(a_j)
            new_c += 1
    func(new_c, new_q)

func(N, A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    A = collections.Counter(ZZ())
    e = collections.defaultdict(list)
    l = [False] * (10 ** 6 + 5)

    def yakusu(num):
        ret = []
        lim = int(num ** 0.5) + 5
        for i in range(1, lim):
            if i * i > num: break
            if num%i != 0: continue
            ret.append(i)
            if i != num//i: ret.append(num//i)
        return ret

    if 1 in A.keys():
        if A[1] == 1: print(1)
        elif A[1] >= 2: print(0)
        return

    ans = 0
    for n in A.keys():
        l[n] = True
        if A[n] == 1: e[n] = yakusu(n)

    for n in A.keys():
        if A[n] >= 2: continue
        if len(e[n]) == 2:
            ans += 1
            continue
        for p in e[n]:
            if p in {1, n}: continue
            if l[p]: break
        else: ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return set(lower_divisors + upper_divisors)-{n}
def main():
    from collections import Counter
    n,*a=map(int,open(0).read().split())
    d=Counter(a)
    s=set(a)
    c=0
    for t in s:
        if d[t]<2:
            for t in make_divisors(t):
                if t in s:break
            else:c+=1
    print(c)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def resolve():
    nn = int(input())
    aa = list(map(int, input().split()))
    a = set(aa)
    exists = {k for k,v in Counter(aa).items() if v > 1}
    ans = 0
    for n in a:
        for div in range(1, int(n**0.5)+1):
            if n in exists:
                break
            if n % div == 0:
                dd = n // div
                if dd != 1 and div in a:
                    break
                if dd != n and dd in a:
                    break
        else:
            ans += 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

def main():
    n = input()
    a = list(map(int, input().split()))
    bt = [0] * len(a)
    a.sort()
    for i in range(0, len(a)):
        for j in range(0, len(a)):
            if (a[j] // 2) > a[i]:
                break
            if i == j:
                continue
            if a[i] % a[j] == 0:
                bt[i] = 1
    print(len(bt) - sum(bt))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

x = int(input())
a = list(map(int, input().split()))
b = []

count = 0
ans_count = 0
for i in range(x):
    if a[i] in b:
        continue
    for j in range(x):
        if i == j:
            continue
        if a[i] % a[j] != 0:
            count += 1
            #print(count)
    if count == x - 1:
        ans_count += 1
    count = 0
    b.append(a[i])
print(ans_count)
#print(a)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input(): return sys.stdin.readline()

def main():
  n=int(input())
  a=np.array(list(map(int,input().split())))
  
  ans=0
  #print(a%(np.array([a for _ in range(n)])).transpose())
  
  for A in a:
    b=A%a==0
    #print(b)
    if np.count_nonzero(b)==1:
      ans+=1
  print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a_origin = sorted(inpl())
ans = 0
count = collections.defaultdict(int)
a = []
for i in range(n):
    count[a_origin[i]] += 1
    if count[a_origin[i]] < 3:
        a.append(a_origin[i])
n = len(a)


class Cell:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None


prev = Cell(a[0])
now = prev
for i in range(1, n):
    new = Cell(a[i])
    prev.next = new
    new.prev = prev
    prev = prev.next
FLAG = True
while now:
    if not now.next:
        if FLAG:
            ans += 1
        break
    target = now.next
    FLAG = True
    while target:
        if FLAG and target.value == now.value:
            FLAG = False
            ans -= 1
        if target.value % now.value == 0:
            if target.next:
                target.next.prev = target.prev
                target.prev.next = target.next
            else:
                target.prev.next = None
        target = target.next
    ans += 1
    now = now.next
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
 
ttable = [[False for i in range(N)] for j in range(N)]
no_list = [False] * N

for i in range(N):
  if no_list[i]:
    continue
  for j in range(i+1, N):
    if As[i] == As[j]:
      ttable[i][j] = True
      ttable[j][i] = True
      no_list[i] = True
      no_list[j] = True
      break
    elif As[i] % As[j] == 0:
      ttable[i][j] = True
      no_list[i] = True
      break
    elif As[j] % As[i] == 0:
      ttable[j][i] = True
      no_list[j] = True
#for i in range(N):
#  if True not in ttable[i]:
#    cnt += 1

print(N-sum(no_list))