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
input=sys.stdin.readline
sys.setrecursionlimit(10**6)


n=int(input().rstrip())
a=sorted([int(i) for i in input().split()])
maxn=10**6+1
dp=[True]*(maxn)
cnt=[0]*(maxn)
ans=0
for i in a:
    if dp[i]:
        cnt[i]+=1
        for j in range(i*2,maxn,i):
            dp[j]=False

for i in a:
    if dp[i] and cnt[i]==1:
        #print(i)
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

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

while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    se = set(make_divisors(ba))
    l1_l2_and = set(li) & set(se)
    if len(l1_l2_and)==0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*(a_max+1)
    for j in range(n):
        a = A[j]
        if note[a]:
            if j != n-1 and A[j]==A[j+1]:
                ans-=1
            ans+=1
            for i in range(a,a_max+1):
                if i%a==0:
                    note[i] = False

        
    
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
x = int(input())
a = list(map(int, input().split()))
a.sort()
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[j] % a[i] == 0:
            b.append(a[j])
    if a[i] in b:
        count += 0
    else:
        count += 1
    #print(b)
print(count)
#print(a)

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()))))
 
def func(c, q, ans):
    if c == 0:
        return ans
    if c == 1:
        ans += 1
        return ans
    if q[0] != q[1]:
        ans += 1
    a_i = q[0]
    new_q = deque()
    new_c = 0
    for i, a_j in enumerate(q):
        if a_j % a_i != 0:
            new_q.append(a_j)
            new_c += 1
    ans = func(new_c, new_q, ans)
    return ans
ans = func(N, A, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
seen = set()
maxN = 1e6
count = 0
for i in range(1, n):
    if arr[i] == arr[i-1]:
        seen.add(arr[i])
for num in arr:
    if num not in seen:
        count += 1
    curr = num
    while curr <= maxN:
        seen.add(curr)
        curr += num
print(count)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
input = stdin.readline

N = int(input())
A_list = list(map(int, input().split()))
ans_list =np.ones(N)
A_list = np.array(A_list)

for i in range(N):
    for j in range(i+1,N):
        if A_list[i] %  A_list[j] == 0:
            ans_list[i] = 0
            if (A_list[j] %  A_list[i] == 0):
                ans_list[j] = 0
        elif A_list[i] ==  A_list[j]:
                ans_list[i] = 0
                ans_list[j] = 0
        elif(A_list[j] %  A_list[i] == 0):
            ans_list[j] = 0
print(int(np.sum(ans_list)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N= int(input())
A = list(map(int, input().split()))
B = A.copy()

for val in set(A):
    B = [b for b in B if b % val != 0 or b == val]

C = Counter(B)
B_filtered = [val for val in C if C[val] == 1]

print(len(B_filtered))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort()

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

while len(li)>0:
    ba = li.pop(-1)
    if c[ba]>1:
        continue
    se = set(make_divisors(ba))
    l1_l2_and = set(li) & set(se)
    if len(l1_l2_and)==0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

from collections import Counter

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

MAX = 10 ** 6 + 1
C = [0] * MAX
seen = [False] * MAX

for v in A:
	C[v] += 1

r = 0

for v in A:
	if C[v] == 1:
		for d in range(1, int(v**.5) + 2):
			if v % d == 0 and (seen[d] or seen[v//d]):
				break
		else:
			r += 1

	seen[v] = True

print(r)

Submission status: Time Limit Exceeded

Solution code:
def eratosthenes(a):
    data = [i for i in a]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data
    
n=int(input())
a=list(map(int, input().split()))
a.sort()
L=eratosthenes(a)
from collections import Counter
c=Counter(L)
ans=0
for v in c.values():
    if v==1:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  A = [int(x) for x in input().split()] # スペース区切り入力
  count = 0
  
  for i in range(N):
    check = [0] * N
    for j in range(N):
      # print(j)
      if j == i:
        check[j] = 1
      else:
        check[j] = A[i] % A[j]
    if 0 in check:
      continue
    else:
      count += 1

  print(count)
          

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
dic={}
for k in a:
    if k in dic:
        dic[k]=0
        continue
    f=1
    for i in dic:
        if k%i==0:
            f=0
            break
    if f:
        dic[k]=1
print(sum(dic.values()))

Submission status: Time Limit Exceeded

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

    uni = sorted(list(set(A)))
    dup = [x for x in set(A) if A.count(x) > 1]
    m = set()

    ans = 0

    for a in uni:
        if a in m: continue

        i = 0
        a_max = uni[len(uni)-1]

        while True:
            m.add(a * i)
            if a*i < a_max:
                i += 1
            else:
                break
        
        if a not in dup:
            ans += 1
 
    print(ans)
 
resolve()

Submission status: Time Limit Exceeded

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

ans = 0

for i in range(n):
    flag = True
    for j in range(n):
        if j != i:
            if a[i] % a[j] == 0:
                flag = False
                break
    if flag:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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


A.sort()
r = 0
for i in A:
    c = 1
    if i in A[r+1:]:
        #print("i", i)
        while(i in A[r+1:]):
            A.remove(i)
        A.remove(i)
        c -= 1
    #print("A",A)
    #print("r+c",r+c)
    for j in A[r+c:]:
        #print("A[r+c:]", A[r+c:])
        if j % i == 0:
            A.remove(j)
    r += 1
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
import copy
n=input()
a_list=input().split()
for h in range(len(a_list)):
    a_list[h]=int(a_list[h])
num_suc=0

for i in range(len(a_list)):
    b_list=copy.copy(a_list)
    b_list.pop(i)
    b_list=list(set(b_list))
    out=[]
    for j in range(len(b_list)):
        q=a_list[i]//b_list[j]
        if b_list[j]*q==a_list[i]:
            out.append("failed")
        if "failed" in out:
            break
    if not "failed" in out:
        num_suc+=1

print(num_suc)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in A:
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

checks = [False] * (1000009)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)
    else:
        for j in range(a, 1000009, a):
            checks[j] = True

# log(B)

ans = 0

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)

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):
    cnt = 0
    for j in range(N):
        if A[i] % A[j] == 0:
            cnt += 1
            if A[j] > A[i]:
                break
    if cnt == 1:
        ans += 1
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]

def solve():
  N = int(input())
  A = [int(i) for i in input().split(' ')]
  divisors_list = {}
  for i in A:
    divisors_list[i] = []

  for k,i in enumerate(A):
    for j in make_divisors(i):
      try:
        divisors_list[j].append(k)
      except:
        continue

  pass_li = {}
  for i in range(N):
    pass_li[i] = 1

  for i in range(N):
    tmp = pass_li[i]
    for j in divisors_list[A[i]]:
      pass_li[j] = 0
    pass_li[i] = tmp 


  print(sum(pass_li.values()))

 
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1

    ans = 0
    for i in range(N):
        x = A[i]
        if x > 1:
            if y[1] : continue
        if y[x] > 1: continue

        f = 1
        for j in range(2,int(math.sqrt(x))+1):
            if x % j == 0 and (y[j] or y[x//j]):
                f = 0
                break
        ans += f

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#import random
#import time
from collections import defaultdict, Counter

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 main():
    #N = 20
    #A = [random.randint(1, int(1e6)) for _ in range(int(N))]
    N = int(input())
    A = [int(c) for c in input().split(' ')]
    #t1 = time.time()
    dup_cnt = Counter(A)
    dup = set(x for x in dup_cnt if dup_cnt[x] > 1)
    A_set = set(A)
    if 1 in A_set:
        if 1 in dup:
            print('0')
        else:
            print('1')
        exit()
    A = list(A_set)
    N = len(A)
    A.sort()
#    B = [factorization(x) for x in A]
#    B.sort()

    d = defaultdict(list)
    B = []
    for x in A:
        x_fac = factorization(x)
        B.append(x_fac)
        for y in x_fac:
            d[y[0]].append(x)
    assert len(A)==len(B)
    #print(A)
    #print(B)
    #print(d)
    not_divided = set()
    for i in range(N):
        bi = A[i]
        bi_fac = B[i]
        can_divide = False
        for y in bi_fac:
            for a in d[y[0]]:
                if bi % a == 0 and bi != a:
                    #print(a,bi)
                    can_divide = True
                    break
                elif a > bi:
                    break
            if can_divide:
                break
        if can_divide or bi in dup:
            continue
        else:
            not_divided.add(bi)
    #print(A)
    #print(dup)
    #print(not_divided)
    print(len(not_divided))
    #print(time.time() - t1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from collections import Counter

N = int(input())
A = sorted(map(int, input().split()))
C = Counter(A)
seen = set()
r = 0

for v in A:
	if C[v] == 1:
		for d in range(1, int(v**.5) + 2):
			if v % d == 0 and (d in seen or v//d in seen):
				break
		else:
			r += 1

	seen.add(v)

print(r)

Submission status: Time Limit Exceeded

Solution code:
import copy
n=int(input())
a=sorted([int(i) for i in input().split()])
f=[True for i in range(n)]
for j in range(n):
    if f[j]==False:
        continue
    for i in range(n):
        if i!=j:
            if a[i]%a[j]==0:
                f[i]=False
            if a[i]==a[j]:
                f[j]=False
print(f.count(True))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(map(int, input().split()), reverse=True)

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]

d = {}
disabled = set()
for i in range(len(A)):
    # save
    divisors = make_divisors(A[i])
    for divisor in divisors:
        if divisor not in d:
            d[divisor] = [i]
        else:
            d[divisor].append(i)
    # judge
    if A[i] in d:
        for item in d[A[i]]:
            if item != i:
                disabled.add(item)
                if A[item] == A[i]:
                    disabled.add(i)

# print(disabled)
print(len(A) - len(disabled))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
A = sorted(A)
ans = [True] * n

for i in range(n):
    ai = A[i]
    if not ans[i]:
        continue
    try:
        if ai == A[i+1]:
            ans[i] = False
    except:
        pass

    for j in range(i+1, n):
        if A[j]%ai == 0:
            ans[j] = False
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
A = sorted(A)
ans = [True] * n

for i in range(n):
    ai = A[i]
    if not ans[i]:
        continue
    try:
        if ai == A[i+1]:
            ans[i] = False
    except:
        pass

    for j in range(i+1, n):
        if A[j]%ai == 0:
            ans[j] = False
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
li = list(map(int,input().split()))
ans = 0

import math
import bisect
import collections
c = collections.Counter(li)
li = list(set(li))
li.sort(reverse=True)
while len(li)>0:
    ba = li.pop(0)
    if c[ba]>1:
        continue
    #s_ba = math.ceil(math.sqrt(ba))+1
    #index = bisect.bisect_right(li, s_ba)
    tmp_li = li
    #print(ba,tmp_li)
    for tt in tmp_li:
        if ba%tt == 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
N = int(input())
#開業されたN個要素を受け付ける
A_list = list(map(int, input().split()))
sorted_A_list = sorted(A_list)

ans = 0

#print(sorted_A_list)

for i in range(N):
    ans = ans+1
    if A_list.count(sorted_A_list[i]) > 1:
        ans = ans-1
        continue
    for j in range(i):
        if sorted_A_list[i]/2 < sorted_A_list[j]:
            break
        if sorted_A_list[i]%sorted_A_list[j] == 0:
            ans = ans-1
            #print(sorted_A_list[i])
            break

print(ans)

Submission status: Time Limit Exceeded

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

count = 0
for i in range(len(A)):
    is_not_dividable = True

    for j in range(len(A)):
        # print(i, j)
        if i == j: continue

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

    # print(is_not_dividable)
    if is_not_dividable:
        count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
 
n = int(input())
A = sorted(map(int, input().split()))
c = Counter(A)
flag = [True] * n
for i in range(n):
    if flag[i] == True:
        for j in range(i+1, n):
            if A[j] % A[i] == 0:
                flag[j] = False
    if c[A[i]] > 1:
        flag[i] = False
print(flag.count(True))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
anstable = [0] * (10 ** 6 + 1)

for i in range(N):
    for j in range(1, 10 ** 6 + 1):
        index = a[i] * j
        if index <= 10 ** 6:
            anstable[index] += 1

cnt = 0
for i in a:
    if anstable[i] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

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

ans = 0
div = []
for i in range(n):
    if 0 < i and a[i] == a[i-1]:
        if i < n-1 and a[i] != a[i+1]:
            div += [a[i]]
        continue
    if i < n-1 and a[i] == a[i+1]:
        continue

    b = True
    for x in div:
        if a[i] < x * 2:
            break
        if a[i] % x == 0:
            b = False
    if b:
        ans += 1
        div += [a[i]]

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(len(B)):
  for j in range(N):
    if A[i]%A[j] == 0 and i != j:
      B[i] = 1
print(N-sum(B))

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

    d = dict()
    for x in A:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    A.sort()

    ans = 0
    dp = [True]*N

    for i in range(N):
        if dp[i]:
            if d[A[i]] == 1:
                ans += 1
            dp[i] = False
            for j in range(i+1, N):
                if dp[j]:
                    if A[j] % A[i] == 0:
                        dp[j] = False
        else:
            continue

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def make_divisors(n):
    if n == 1:
        return [1]
    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


N = int(input())
A = list(map(int, input().split()))
X = [0] * (10**6 + 1)
for a in A:
    X[a] += 1
ans = 0
for a in A:
    if X[a] > 1:
        continue
    for d in make_divisors(a)[:-1]:
        if X[d]:
            break
    else:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N= int(input())
A = list(map(int, input().split()))
A.sort()
B = A.copy()

for i in range(N):
    B = [b for b in B if b % A[i] != 0 or b == A[i]]

C = Counter(B)
B_filtered = [val for val in C if C[val] == 1]

print(len(B_filtered))

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
i = 0
while i<len(a):
    a = [a[i]]*(a.count(a[i])==1) + list(filter(lambda x: x%a[i] >0,a)) 
    i+=1
print(len(a))

Submission status: Time Limit Exceeded

Solution code:
MAX = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * MAX
for a in A:
    cnt[a] += 1
for i in range(N):
    a = A[i]
    if cnt[a] == 0:
        continue
    for j in range(2 * a, MAX, a):
        cnt[j] = 0
res = 0
for a in A:
    if cnt[a] == 1:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in range(N):
        y[A[i]] += 1

    ans = 0
    for i in range(N):
        x = A[i]
        if x > 1:
            if y[1] : continue
        if y[x] > 1: continue

        f = 1
        for j in range(2,int(math.sqrt(x))+1):
            if x % j == 0 and (y[j] or y[x//j]):
                f = 0
                break
        ans += f

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

Submission status: Time Limit Exceeded

Solution code:
import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    note = [True]*n
    for i in range(n):
        if note[i]:
            a = A[i]
            if i != n-1 and a==A[i+1]:
                ans-=1
            ans +=1
            for j in range(i,n):
                if A[j]%a==0:
                    note[j]=False
       
    
    print(ans)
main()

Submission status: Time Limit Exceeded

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

#print("c:",c)
#print(p)
#print("s:",s)

for x in s:
#    print(x)
    t = x * 2
#    print("t:",t)
    while t <= 10 ** 6:
        p[t] = False
        t += x
#        print("t_inner:",t)
ans = 0

#print("a:",a)
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from numba import jit

def main():
    n = int(input().strip())
    L = list(map(int, input().strip().split()))
    seen = Counter()
    
    
    for x in L:
        seen[x]+=1
    @jit
    def loop():
        ans=0
        for x in L:
            if seen[x]>1 or x!=1 and 1 in seen:
                continue
        
            tmp=2
            while tmp**2<=x:
                if x%tmp==0 and (tmp in seen or x/tmp in seen):
                    break
                tmp+=1
            else:
                ans+=1
        return ans
    print(loop())
# print(ans)
    
if '__main__' == __name__:
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

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

c = collections.Counter(A_list)
sorted_list = sorted(A_list)

count = 0

i_memo = 0

for i_index in range(N):
    i = sorted_list[i_index]
    i_memo = i
    for j in sorted_list[:i_index]:
        jmemo = j
        if i % j == 0:
            break
    else:
        if c[i_memo] == 1:
            count+= 1
print(count)

Submission status: Time Limit Exceeded

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

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

ans = 0
div = []
for i in range(n):
    if 0 < i and a[i] == a[i-1]:
        div += [a[i]]
        continue
    if i < n-1 and a[i] == a[i+1]:
        continue

    b = True
    for x in div:
        if a[i] < x * 2:
            break
        if a[i] % x == 0:
            b = False
    if b:
        ans += 1
        div += [a[i]]

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lis = list(map(int,input().split()))
lis2 = [True]*n
lis.sort()
m = max(lis)
ans = 0
for i in range(n):
    if lis2[i]:
        if i < n-1:
            # print(i)
            if lis[i] != lis[i+1]:
                ans += 1
        else:
            ans += 1
        for j in range(i+1,n):
            if lis2[j]:
                if lis[j]%lis[i] == 0:
                    lis2[j] = False

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N = input()
data = input().split()
original = data.copy()
data2 = original.copy()

res_count = 0
loop_count = 0

for num in data:
    flag = 0
    data2 = original.copy()
    data2.pop(loop_count)
 #   print(original)
#    print(data2)
    for num2 in data2:
        if (int(num) % int(num2)) == 0:
            flag = 1
    
    if flag == 0:
        res_count += 1
 #       print('num = {}  num 2 = {}'.format(num,num2))

    loop_count += 1
    
print(res_count)

Submission status: Time Limit Exceeded

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

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

def main():
    n = I()
    mylist = list(MI())
    mylist.sort(reverse = True)
    mylist = tuple(mylist)
    if mylist[n-1] in mylist[:n-1]:
        result = 0
    else:
        result = 1
    for i in range(n-1):
        temp = mylist[i]
        if mylist.count(temp) <= 1:
            divide = True
            for j in range(i+1,n):
                if temp % mylist[j] == 0:
                    divide = False
                    break
            if divide:
                result += 1
    print(result)

main()

Submission status: Time Limit Exceeded

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

a.sort()
t = [True]*n

for i in range(n-1):
    for j in range(i+1, n):
        if a[j] == a[i]:
            t[i] = False
            t[j] = False
        elif t[j] and a[j]%a[i] == 0:
            t[j] = False


print(sum(t))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from collections import defaultdict

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]

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    times = defaultdict(int)
    for i in a:
        times[i] += 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 in tmp:
                break
        else:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import io,sys
sys.setrecursionlimit(10**6)

def main():
    import bisect
    n = int(input())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A.sort()

    ans = 0
    a_max = A[-1]
    note = [True]*n
    for i in range(n):
        if note[i]:
            a = A[i]
            if i != n-1 and a==A[i+1]:
                ans-=1
            ans +=1
            for j in range(i,n):
                if A[j]%a==0:
                    note[j]=False
       
    
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter
def ip():return int(input())
def imp():return map(int,input().split())
def impstr():return map(str,input().split())
def limp():return list(map(int,input().split()))
def limpstr():return list(map(str,input().split()))
def prime(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i==0:return False
    return True

n=ip()
l=limp()
if 1 in l:
    if l.count(1)==1:print(1)
    else:print(0)
    exit()
else:
    #l.sort()
    c=Counter(l)
    ans=0
    for k,v in c.items():
        if v>1:continue
        elif prime(k)==True:ans+=1
        else:
            f=True
            ys=[]
            for i in range(2, int(math.sqrt(k)) + 1):
                if k % i == 0 and (i in c or k//i in c):
                    f=False
                    break
            if f==True:ans+=1

    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 = [int(hoge) for hoge in input().split()]
C = Counter(A)
A.sort()
for start in range(N):
    if start >= len(A):
        break
    flag = [True] * len(A)
    s = A[start]     
    if C[s] >= 2:   
        for n in range(start,len(A)):
            if A[n]%s == 0:
                flag[n] = False
    else:   
        for n in range(start,len(A)):
            if A[n]%s == 0 and A[n] != s:
                flag[n] = False

    A = [A[n] for n in range(len(flag)) if flag[n]]
print(len(A))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    ans = 0
    for i in range(len(a)):
        if a.count(a[i]) > 1:
            continue
        divisors = set()
        for j in range(1, int(a[i] ** 0.5) + 1):
            if a[i] % j == 0:
                divisors.add(j)
                if j != a[i] // j:
                    divisors.add(a[i] // j)
        if len(set(a) & divisors) == 1:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()