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())
Ain=list(map(int,input().split())) 
ansn=0
A=set(Ain)
A=list(A)
A.sort()
A2=list(t for t in A)


ans=[]
while len(A2)!=0:
    ans.append(A2[0])
    templist=[]
    for j in range(len(A2)):
        if A2[j]%A2[0]==0:
            templist.append(j)
    for s in reversed(templist):
        del A2[s]

for anss in ans:
    if Ain.count(anss)==1:
        ansn+=1
print(ansn)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bc
from collections import defaultdict
from collections import deque
N = int(input())
A = list(map(int,input().split()))
A.sort()
q = deque([i for i in range(N)])
 
for i in range(N):
    ai = A[i]
    itr = list(q)
    for j in itr:
        if j == i:
            continue
        if A[j] % ai == 0:
            del q[bc.bisect_left(q,j)]
 
print(len(q))

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n):
    no_div = True
    for j in range(n):
        if i == j:
            continue
        if a[i] < a[j]:
            break
        if a[i] % a[j] == 0:
            no_div = False
            break
    if no_div:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
a = []
cnt = 0

n = int(input())
a = input().split()

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

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

print(n-cnt)

Submission status: Time Limit Exceeded

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

a.sort()
b = []
c = 0
r = []
for i, v in enumerate(a):
    flag = True
    for j in range(1, int(math.sqrt(v))+1):
        if v % j == 0 and (j in b or v/j in b):
            flag = False
            break
    if flag == True:
        b.append(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
nums = [int(s) for s in input().rstrip().split()]

count = 0

def explore(i):
  n_i = nums[i]
  for k in range(n_i):
    if n_i % (k + 1):
      limit = n_i // (k + 1)
      break
  limit = n_i // 2
  for j in range(N):
    if j != i:
      n_j = nums[j]
      if n_j == n_i:
        return 0
      if n_j <= limit:
        if n_i % n_j == 0:
          return 0
  return 1

for i in range(N):
  count += explore(i)

print(count)

Submission status: Time Limit Exceeded

Solution code:
m=input().split(" ")
n=input().split(" ")
n = [int(p) for p in n]
n.sort()
i = 0
ans = 0
drawflg = True;
while True:
	flg = True;
	if i == len(n):
		break
	else:
		for p in range(i):
			if n[i] % n[p] == 0:
				flg = False;
				if n[i] / n[p] == 1:
					if drawflg:
						ans-=1
					drawflg = False;
				break
			else:
				drawflg = True;
		if flg:
			ans+=1
		else:
			del n[i]
			i-=1
		i+=1
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def prime_decomposition(n):
    i = 2
    table = defaultdict(int)
    while i*i <= n:
        while n%i == 0:
            n //= i
            table[i] += 1
        i += 1
    if n > 1:
        table[n] += 1
    return table

ansA = [1]*N

num = defaultdict(int)
pdA = [prime_decomposition(val) for val in A]
for i, pdai in enu(pdA):
    num[A[i]] += 1
    for j, pdaj in enu(pdA[i+1:]):
        if ansA[i+j+1] == 0:
            continue
        if len(pdai) <= len(pdaj):
            for pdaii in pdai.items():
                ki, vi = pdaii
                if pdaj[ki] < vi:
                    break
            else:
                ansA[i+j+1] = 0

# print(A)
# print(ansA)
cnt = 0
for i, a in enu(A):
    if ansA[i] == 0:
        continue
    if num[a] > 1:
        continue
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def check_prime(k):
    if k == 1:return 1
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0

    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()
if n > 1:
    if a[0] == 1 and a[1] == 1:
        print(0)
        exit()
    elif a[0] == 1:
        print(1)
        exit()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter 

def main():
    n = int(input())

    checker = [False] * (10**6+1)

    a = list([int(t)for t in input().split()])
    c = Counter(a)

    for a_i in a:
        for i in range(a_i*2,10**6+1,a_i):
            checker[i] = True

    ans = 0
    for a_i in a:
        if not checker[a_i] and c[a_i]==1:
            ans += 1

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = set(A)
for i in A:
    if A.count(i) > 1: B = B - {i}
multiplier = 2
for i in B:
    while i*multiplier <= max(B):
        B = B - {i*multiplier}
print(len(B))

Submission status: Time Limit Exceeded

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

l = []
l.append(a[0])
cou =[]



for i in range(1,n):
    b = a[i]
    for j in range(len(l)):
      if b==l[j]:
        cou.append(b)
        break
      if b%l[j]==0:
        break
    else:
      l.append(b)

print(len(l)-len(set(cou)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,1001):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=0
b=a.copy()
a=set(a)
for i in range(1,b[-1]+1):
    bi=b.count(i)
    if bi>=2:
        for j in range(bi):
            b.remove(i)
a=list(a)
n=len(a)
m=len(b)
for i in range(m):
    for j in range(n):
        if a[j]!=b[i] and b[i]%a[j]==0:
            b[i]=0
            break
print(m-b.count(0))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
n_list = [int(x) for x in input().split()]
n_list.sort()
counter_1 = 0
for i in range(n):
  counter_2 = 0
  if counter_2 == 1:
    break
  else:
    i_n = min(i+2, n)
    for j in range(i_n):
      if i == j:
        continue
      else:
        if n_list[i] % n_list[j] == 0:
          counter_2 += 1
          break
  if counter_2 == 0:
    counter_1 += 1
print(counter_1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(input())
a = [int(y) for y in input().split()]
a.sort()

q = deque()
for i in range(N):
    q.append(a[i])

cnt = 0

while N > 0:
    flag = True
    res = q.popleft()

    for i in range(N-1):
        now = q.popleft()
        if now == res and flag:
            cnt -= 1
            flag = False
        if now % res != 0:
            q.append(now)
    
    N = len(q)
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
a_list = [int(_c) for _c in input().split(" ")]
a_list = sorted(a_list)

if 1 in a_list:
    if a_list.count(1) == 1:
        print(1)
    else:
        print(0)
    sys.exit(0)

answers = []
ng_list = []
for a in a_list:
    if a in answers:
        if a not in ng_list:
            ng_list.append(a)
        continue

    if len(answers) == 0:
        answers.append(a)
        continue

    append_num = True
    for answer in answers:
        if a % answer == 0:
            append_num = False
            break
    if append_num:
        answers.append(a)

print(len(answers) - len(ng_list))

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):
  a = 0
  if A.count(A[i]) > 1:
    a = 1
  else:
    for j in range(i):
      if A[i] % A[j] == 0:
        a = 1
    if a == 0:
      ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

cand = set(a)

exist = set()
dup = set()
for item in a:
    if item in exist:
        dup.add(item)
    else:
        exist.add(item)

dame_set = set()

a.sort()
ret = 0

for val in a:
    if val in dup:
        i = 1
        cnt = 10 ** 6 // val
        while i <= cnt:
            dame_set.add(i * val)
            i += 1
    else:
        if val in dame_set:
            continue
        else:
            ret += 1
            i = 1
            cnt = 10 ** 6 // val
            while i <= cnt:
                dame_set.add(i * val)
                i += 1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

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
m = [0] * MAX
for i in range(n):
  m[a[i]] += 1
#print(m[:30])
mx = max(a)
ans = 0
for p in range(n):
  i = a[p]
  if m[i] != 1:
    continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
aa = list(map(int, input().split()))
aa.sort()

oks = np.ones(len(aa))
for i in range(n):
    oks[i+1:] = [oks[j]*int(not aa[j]%aa[i] == 0)  for j in range(i+1,n)]
    if i < n-1:
        if aa[i+1] == aa[i]:
            oks[i] = 0
print(int(oks.sum()))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    A.sort()
    divisible = [False] * N

    for i in range(N):
        for j in range(N):
            if not divisible[j] and i != j:
                if A[j] % A[i] == 0:
                    # print(A[j], A[i])
                    divisible[j] = True

    print(divisible.count(False))

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
li = list(map(int, input().split()))
ans = []
kotae = 0
for i in range(a):
    for j in range(a):
        if not i == j:
            if not li[i] % li[j] == 0:
                ans.append(i)
for i in range(a):
    if ans.count(i) == a-1:
        kotae += 1
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
input()
a = [int(i) for i in input().split()]
a.sort()
 
L = 0
for n,i in enumerate(a):
    H = 0
    for m,j in enumerate(a[:n+2]):
        if i % j == 0 and n != m:
            H = 1
            break
    if H == 0:
        L+=1
print(L)

Submission status: Time Limit Exceeded

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

cnt=0

for k in range(n):
    for i in range(1,n):
        
        if a[k]%a[k+i]==0:
            if a[k] in A:
                A.remove(a[k])
                break
                
        
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline


  N = int(input())
  A = tuple(map(int, input().split()))
  count = N

  i = 0
  while i != N:
    for j in range(N):
      if i != j and A[i] % A[j] == 0:
        count -= 1
        break
    i += 1
  
  print(count)
  
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans_list=[]
for i in range(N):
  for j in range(i+1,N):
    temp=math.gcd(A[i],A[j])
    if A[i]==temp:
      ans_list.append(j)  
    if A[j]==temp:
      ans_list.append(i)
      break
      

print(N-len(set(ans_list)))
#print(gcd_list)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = list(map(int, input().split()))[0]
A = np.array(list(((map(int, input().split())))))
idx = np.argsort(A)
A = np.sort(A)
Z = np.zeros(N)

def get_result():
    result = 0
    for i in range(N):
        flag = True
        if i < N - 1 and A[i] == A[i + 1]:
            flag = False
        for j in range(i):
            if Z[j] != 0:
                continue
            d, m = divmod(A[i], A[j])
            if m == 0:
                flag = False
                Z[i] = 1
                break
        if flag:
            result += 1
    return result

print(get_result())

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = sorted([int(x) for x in input().split()])
if A[0] == 1:
    if N == 1:
        print(1)
        exit()
    elif A[1] == 1:
        print(0)
        exit()
    print(1)
    exit()
cA = Counter(A)

cand = set()
ans = 0
for a, val in cA.items():
    if len(cand) != 0 and val == 1:
        for t in cand:
            if a % t == 0:
                break
        else:
            #print(a)
            cand.add(a)
            ans += 1
    elif val == 1:
        #print(a)
        cand.add(a)
        ans += 1
    else:
        continue
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

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


def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
    

    n = int(lines[0])
    a = [int(e) for e in lines[1].split(' ')]

    return (n, a)


def solve(n, a):

    if n == 1:
        return 1
    
    count_dict = dict()
    for i in range(n):
        cnt = count_dict.get(a[i], 0)
        cnt = cnt + 1
        count_dict[a[i]] = cnt
    
    a.sort()

    tmp = a.copy()
    result = []
    while len(tmp) > 0:
        h = tmp[0]
        result.append(h)
        tails = tmp[1:]
        tmp2 = []
        for t in tails: 
            if t % h == 0:
                pass
            else:
                tmp2.append(t)

        tmp = tmp2

    result_2 = []    
    removed = set([k for k, v in count_dict.items() if v > 1])
    for r in result:
        if r in removed:
            pass
        else:
            result_2.append(r)
    
    len_result = len(result_2)

    return len_result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':
  
    main()

Submission status: Time Limit Exceeded

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

a_list_sorted = sorted(a_list)

j = 0
remove_flag = False
while True:
    remove_flag = False
    if j >= len(a_list_sorted):
        break
    check = a_list_sorted[j]
    i = j-1 # 検索の初期値
    while True:
        i += 1
        if i >= len(a_list_sorted):
            break
        value = a_list_sorted[i]
        if j >= i:
            continue
        if value == check: # 同じ数字を持つ
            remove_flag = True
        if value % check == 0:
            del a_list_sorted[i]
            i -= 1
    if remove_flag:
        del a_list_sorted[j] # 探索した数字
        j -= 1
    j += 1

print(len(a_list_sorted))

Submission status: Time Limit Exceeded

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

cnt = 0
for i in range(len(a)):
    chk = True
    for j in range(len(a)):
        if i == j:
            continue
        if (a[i] % a[j]) == 0:
            chk = False
    if chk:
        cnt += 1
print (cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
n = int(input())
a = list(map(int, input().split()))
counter = set([])
for i in range(n - 1):
    a_np = np.roll(np.array(a), i + 1)
    index = np.where(a % a_np == 0)
    for num in index[0]:
        counter.add(num)
print(n - len(counter))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
nun_list = list(map(int, input().split()))
count=0
hoge = len(nun_list) - 1
for i in range(1,n+1):
    tmp = 0
    for j in range(1,n+1):
        if i != j:
            if nun_list[i-1] % nun_list[j-1]  == 0:
                break
            else :
                tmp+=1
    if tmp == hoge:
        count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n = input()
a_list = input().split()

n = int(n)

def check():
    exact_list = []
    for i in range(0, n):

        # 一回も割り切れない場合を探す
        flg = False

        for j in range(0, n):
            # 一緒の数字ならば飛ばす
            if i == j:
                continue

            # 割り切れない場合を探せ
            # print(int(a_list[i]) % int(a_list[j]))
            if int(a_list[i]) % int(a_list[j]) == 0:
                flg = True
                break
        
        # 割り切れた場合、該当配列を記録する
        if flg == False:
            exact_list.append(i+1)


    print(len(exact_list))

check()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def divisor(n): #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()
A = LIST()
A.sort()

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

dic = defaultdict(int)
no_exist = 0
ans = 0
kaburi = defaultdict(int)
for a in A:
    kaburi[a] += 1

for a in A:
    if kaburi[a] == 1:
        no_exist = 0
        prime = set(divisor(a))
        # print("p", prime)
        for p in prime:
            p = int(p)
            if dic[p] != 0:
                no_exist += 1
            
        if no_exist == 0:
            ans += 1
    dic[a] += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N= int(input())
A = input().split()
Ans = 0
flag = 0
for i in range(N):
  for j in range(N):
    if i != j :
      if (int(A[i]) % int(A[j])) == 0:
        flag = 1
      #print(i, j, A[i], A[j], flag)
  if flag == 0:
    Ans += 1
  flag = 0
print(Ans)

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

cnt = [0] * 1000001

for i in range(n):
    cnt[p[i]] += 1

ans = n

for i in range(n):
    c = make_divisors(p[i])
    for j in range(len(c)):
        if (not (c[j] == p[i]) or cnt[c[j]] > 1) and cnt[c[j]]:
            ans -= 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
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()))
a=sorted(a)
c=Counter(a)
x=set()
for i in range(n):
    x.add(a[i])
d={}
for i in x:
    d[i]=1
ans = 0
for i in x:
    if c[i]>1:
        continue
    l=make_divisors(i)
    x.remove(i)
    f=1
    for r in l:
        if not r in d:
            continue
        if r == i:
            continue
        if d[r] == 1:
            f=0
            break
    if f:
        ans += 1
    x.add(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
list = list(map(int, input().split()))
rlist = list
rlist.sort()
ans=0

for i in range (0,N):
  res=0
  for j in range(0,N):
    if(i!=j and rlist[i] % rlist[j]==0):
      res+=1
      break
  if(0<res):
    ans+=1

print(N-ans)

Submission status: Time Limit Exceeded

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

a.sort()
ans = 0

while True:
  x = a[0]
  if a.count(x) == 1:
    ans += 1
  for y in a[:]:
    if y%x == 0:
      a.remove(y)
  if len(a) == 0:
    break

print(ans)

Submission status: Time Limit Exceeded

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

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

count = 0

for i in range(N):
    for j in range(N):
        if i == j:
            continue

        if A[i] % A[j] == 0:
            break

    else:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
As = list(map(int, input().split()))
count = sorted(Counter(As).items(), key = lambda x: x[0])
divider = set()


ans = 0
for numi, c in count:
  if c > 1:
    divider.add(numi)
    continue
  flag = True
  for numj in divider:
    if numj ** (0.5) > numi:
      divider.add(numi)
      ans += 1
      break
    if numi % numj == 0:
      break
  else:
    divider.add(numi)
    ans += 1
  
print(ans)

Submission status: Time Limit Exceeded

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

cnt = 0

for i in ints:
    clr = [i % j == 0 for j in ints]
    if clr.count(True) == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int, input().split()))
li.sort()
inf = (10**6)+1
isprime = [False]*(inf+1)
for i in li:
    isprime[i] = True
m = 2
for i in li:
    if not isprime[i]:
        continue
    for k in li:
        if k%i == 0 and k!=i:
            isprime[k] = False
    m = i
prime_list = []
for i in range(len(li)):
      if i+1<len(li):
            if li[i] == li[i+1]:
                isprime[li[i]] = False
for i in range(1, inf+1):
    if isprime[i]:
        prime_list.append(i)
print(len(prime_list))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(s) for s in input().split()]
k = 0
l = []
for i in A: #ｎ個の数について調べる 今調べてるのはi
    for j in A:  #要素で割っていって余りがないか調べる　自分自身で割るときは余らないことに注意
        if (i%j == 0):
            k += 1
    if (k == 1):
        l = l + [i]
    k = 0
print (len(l))

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
# from fractions import gcd

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

    q = deque(sorted(A))

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

    ans = 0
    while q:
        # print(q)
        n = q.popleft()
        ans = ans + memo[n]
        next_q = deque([])
        for t in q:
            if t % n == 0:
                pass
            else:
                # print(n, t)
                next_q.append(t)
        q = next_q
    print(ans)


if __name__ == '__main__':
    solve()

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):
    flg = 0
    for j in range(i):
        if i +1 < N:
            if A[i+1] == A[i]:
                flg = 1
                break
        if A[i] == A[i-1]:
            flg = 1
            break
        #if A[j]*2 > A[i]:
            #print(A[j], A[i])
            #if A[j] == A[i]:
                #flg = 1
            break
        if i != 0:
            if A[i]%A[j] == 0:
                flg = 1
                break    
    if flg == 0:
        if i +1 < N:
            if A[i+1] != A[i]:
                ans += 1
        else:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#4問目
import math
N = int(input())
A = list(map(int, input().split()))
newA = []
count = 0

for i in range(N):
    newA = []
    for j in range(N):
        if i != j:
            newA.append(A[i] % A[j])
        if i == j:
            newA.append(1)
    if(0 not in newA):
        count += 1
print(count)

Submission status: Time Limit Exceeded

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

A.sort()
B = [0]*N

for i in range(N):
    if B[i]:
        continue
    if i < N-1:
        if A[i] == A[i+1]:
            B[i] = 1
    x = A[i]
    for j in range(i+1, N):
        if B[j]:
            continue
        if A[j]%x == 0:
            B[j] = 1

print(N-sum(B))

Submission status: Time Limit Exceeded

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

if n != 1:
    if a[0] == a[1]:
        cnt -= 1

for i in range(1, n):
    for j in range(i):
        if i != n-1:
            if a[i+1] == a[i]:
                cnt -= 1
                break
        if a[i] % a[j] == 0:
            cnt -= 1
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(0,N):
  flag = True
  for j in range(0,N):
    if i != j and A[i] >= A[j]:
      if A[i] % A[j] == 0:
        flag = False
        break
  if(flag):
    l.append(A[i])

print(len(l))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit
@njit
def solve(A,N):
    value_count=0
    for i in range(N):
        Ai=A[i]
        test_A=Ai%A
        if(np.sum(test_A==0)==1):
            value_count+=1
    return value_count
N=int(input())
A= np.array(list(map(int,input().split())))
print(solve(A,N))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
c = []
for i in range(n):
    for j in range(n):
        if i !=j and A[i]%A[j] == 0:
            c.append(i)
c = set(c)
print(n - len(c))