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
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    n = ni()
    a = na()

    seta = set(a)
    cnta = collections.Counter(a)
    lista = list(seta)
    lista.sort()

    ans = 0

    for ai in lista:
        if cnta[ai] > 1:
            continue
        flg = True
        for div in lista:
            if div >= ai:
                break
            if ai % div == 0:
                flg = False
                break
        if flg:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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_right #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()))
maxA = max(A)
nums = set()
A.sort()
sA = list(set(A))
cnt = 0 
ans = defaultdict(int)
for a in sA:
    new = False
    if not(a in nums):
        cnt += 1
        ans[a] += 1
        new = True
    nums.add(a)
    # while new and a + mlt < maxA+2:
    if new:
        for val in range(a+a, maxA+2, a):
            nums.add(val)

for an in ans.keys():
    if A.count(an)>1:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

final = n

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
lineup=sorted([int(x) for x in input().split()])
duplicate={}
for i in lineup:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
sieve=[1]*(max(lineup)+2)
counter=0
for i in range(N):
	for j in range(lineup[i]*2,max(lineup)+1,lineup[i]):
		sieve[j]=0

	if duplicate[lineup[i]]==1 and sieve[lineup[i]]==1:
		counter+=1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
aa = np.array(list(map(int,input().split())))
a=np.sort(aa)
ah=[1]*len(a)

for i in range(n-1):
    if ah[i]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j],a[i])
            ah[j]=min(wk0,ah[j])
            if wk1==1 and wk0==0:
                ah[i]=0
print(sum(ah))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = [0] * (10**6+1)
    for a in A:
        L[a] += 1
    ans = 0
    Ng = [False] * (10**6+1)
    for a in A:
        for i in range(a*2, 10**6+1, a):
            Ng[i] = True
    for a, (cnt, ng) in enumerate(zip(L, Ng)):
        if cnt == 1 and not ng:
            ans += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(sys.stdin.readline())
array=sorted([int(x) for x in sys.stdin.readline().split()])
duplicate={}
#check for duplicates
for i in array:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1
#loop from the list to check which are divisible and mark them as False
for i in range(N):
	if array[i]==False:
		continue
	for j in range(i+1,N):
		if array[j]==False:
			continue
		if array[j]%array[i]==0:
			array[j]=False

#remove all False
array=[x for x in array if x!=False]

#after that if the only remaining are duplicates, mark them as False
for i in range(len(array)):
	if duplicate[array[i]]>1:
		array[i]=False

#remove all False
array=[x for x in array if x!=False]

print(len(array))

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(sys.stdin.readline())
array=sorted([int(x) for x in sys.stdin.readline().split()])
duplicate={}
for i in array:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1







for i in range(N):
	for j in range(i+1,N):
		if array[i]==False:
			break
		if array[j]%array[i]==0:
			array[j]=False

array=[x for x in array if x!=False]
for i in range(len(array)):
	if duplicate[array[i]]>1:
		array[i]=False
array=[x for x in array if x!=False]

print(len(array))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
array=sorted([int(x) for x in input().split()])
duplicate={}
for i in array:
	if i in duplicate:
		duplicate[i]+=1
	else:
		duplicate[i]=1







for i in range(N):
	for j in range(i+1,N):
		if array[i]==False:
			break
		if array[j]%array[i]==0:
			array[j]=False

array=[x for x in array if x!=False]
for i in range(len(array)):
	if duplicate[array[i]]>1:
		array[i]=False
array=[x for x in array if x!=False]

print(len(array))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
dp = [True]*(A[-1]+1)

for i in range(N-1):
  if dp[A[i]] == True:
    for j in range(A[i], max(A)+1,A[i]):
      dp[j] = False
    if A[i] != A[i+1]:
      cnt+=1
if dp[A[-1]] == True:
  cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = 0
dp = [True]*(max(A)+1)

for i in range(N-1):
  if dp[A[i]] == True:
    for j in range(A[i], max(A)+1,A[i]):
      dp[j] = False
    if A[i] != A[i+1]:
      cnt+=1
if dp[A[-1]] == True:
  cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
aa = list(map(int,input().split()))
a=np.array(sorted(aa))
 
ad=[1]*n
 
for i in range(n-1):
    if ad[i]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j],a[i])
            if wk0==0:
                if wk1==1:
                    ad[i]=0
                ad[j]=0
 
print(sum(ad))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
dp = [1]*(max(a)+1)
his = []
for i in range(n):
    if a[i] in his:
        dp[a[i]] = 0
    else:
        his.append(a[i])
        for j in range(a[i]*2,len(dp),a[i]):
            dp[j] = 0

sum = 0
for i in range(n):
    if dp[a[i]] == 1:
        sum += 1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
input()
li = list(map(int,input().split()))	
li.sort()
l = len(li)
hyo = [1] * l
count = 0
for i in range(0,l):
  if hyo[i] == 0:
    continue
  for j in range(i + 1, l):
    if li[j] % li[i] == 0:
      hyo[j] = 0
  if i < l - 1:
    if li[i] == li[i+1]:
      continue
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
input()
li = list(map(int,input().split()))	
li.sort()
l = len(li)
hyo = [1] * l
for i in range(0,l):
  if hyo[i] == 0:
    continue
  if i > 0 and li[i] == li[i-1]:
    continue
  for j in range(i + 1, l):
    if li[j] % li[i] == 0:
      hyo[j] = 0
count = 0
for i in range(0,l):
  if hyo[i] == 1 and li.count(li[i]) == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
input()
li = list(map(int,input().split()))	
li.sort()
l = len(li)
hyo = [1] * l
for i in range(0,l):
  if hyo[i] == 0:
    continue
  for j in range(i + 1, l):
    if li[j] % li[i] == 0:
      hyo[j] = 0
count = 0
for i in range(0,l):
  if hyo[i] == 1 and li.count(li[i]) == 1:
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted(list(map(int,input().split())))
    for i in range(n-1):
        if a[i]!=0:
            flg = 0
            for j in range(i+1,n):
                if a[i]==a[j]:
                    flg=1
                    a[j] = 0
                elif a[j]%a[i]==0:
                    a[j] = 0
            if flg==1:
                a[i] = 0
    ans = 0
    for i in range(n):
        if a[i]!=0:
            ans+=1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
memo = [0] * (10**6 + 1)
for i in a:
    for j in range(i, 10**6+1, i):
        memo[j] += 1

ans = 0
for i in a:
    if memo[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
aa = [0] * (10 ** 6 + 1)
a.sort()
ans = 0


for i in a:
    for j in range(i, 10 ** 6 + 1, i):
        aa[j] += 1

a = set(a)

for k in a:
    if aa[k] == 1:
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# review
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    OK = [True for i in range(10**6+1)]
    CNT = [0 for i in range(10**6+1)]
    for x in A:
        CNT[x] += 1
        for i in range(2, 10**6+1):
            if i*x > 10**6:
                break
            OK[i*x] = False
    for x in A:
        if CNT[x] == 1 and OK[x]:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1]*(10**6+1)
for i in range(n):
    if ls[a[i]] == 1:
        for j in range(a[i]*2, 10**6+1, a[i]):
            ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and a.count(a[i]) <= 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
aaa = list(map(int,input().split()))
aa=sorted(aaa)
a=np.array([[i,1] for i in aa])

for i in range(n-1):
    if a[i][1]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j][0],a[i][0])
            if wk0==0:
                if wk1==1:
                    a[i][1]=0
                a[j][1]=0

print((np.sum(a,axis=0))[1])

Submission status: Time Limit Exceeded

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

ad=[1]*n
an=n

for i in range(n-1):
    if ad[i]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j],a[i])
            if wk0==0:
                if wk1==1:
                    ad[i]=0
                ad[j]=0

print(sum(ad))

Submission status: Time Limit Exceeded

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

ad=[1]*n
an=n

for i in range(n-1):
    if ad[i]==1:
        for j in range(i+1,n):
            wk1,wk0=divmod(a[j],a[i])
            if wk0==0 and ad[j]==1:
                if wk1==1:
                    ad[i]=0
                ad[j]=0

print(sum(ad))

Submission status: Time Limit Exceeded

Solution code:
import sys
import time

def main():
    N = int(input())
    As = list(map(int, input().split()))
    As.sort()
    made = As[-1]
    lis = [True for _ in range(made)]
    for i in range(len(As)):
        if As.count(As[i]) > 1:
            lis[As[i]-1] = False

    for i in As:
        for j in range(2, int(made/i)+1):
            if lis[i*j-1] == False:
                continue
            lis[i*j-1] = False
    answer = len([int(x) for x in As if lis[x-1]])
    

    print(answer)

if __name__ == '__main__':
    #start = time.time()
    main()
    #elapsed_time = time.time() - start
    #print("経過時間:{}".format(elapsed_time * 1000) + "[msec]")

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, max(a) + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    a = sorted(a)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, 10**6 + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def solve(string):
    n, *a = map(int, string.split())
    table = [True] * (10**6 + 1)
    for _a in a:
        if table[_a]:
            for i in range(2 * _a, 10**6 + 1, _a):
                table[i] = False
    return str(sum(table[k] for k, v in Counter(a).items() if v == 1))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def solve(string):
    n, *a = map(int, string.split())
    if len(a) == 1:
        return "1"
    a = np.array(a, np.int)
    ans = np.ones(n, np.int)
    for i, _a in enumerate(a):
        tmp = a % _a != 0
        tmp[i] = True
        ans *= tmp
    return str(sum(ans))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product


def solve(string):
    n, *a = map(int, string.split())
    a = sorted(a)
    if len(a) == 1:
        return "1"
    t = [True] * n
    for i, j in product(range(n), repeat=2):
        if i == j:
            continue
        if a[i] % a[j] == 0:
            t[i]=False
    return str(sum(t))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Time Limit Exceeded

Solution code:
#約数の列挙O(√n)
def divisor(n):
    res = []
    for i in range(1, n+1):
        if i * i > n:
            break
        if n % i == 0:
            res.append(i)
            if i != n//i:
                res.append(n//i);
    res.sort()
    return res;

N = int(input())
A = list(map(int, input().split()))
# Ai / Aj == 0 を数える
cnt = [0] * 2000000
ans = 0
for i in range(N):
    cnt[A[i]] += 1

for i in range(N):
    div = divisor(A[i])
    sum = 0
    for d in div:
        sum += cnt[d]
    sum -= 1
    if sum == 0:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  a_max = a[-1]
  db = [0] * a_max
  for i in a:
    if a.count(i) == 1:
      db[i-1] = 1
  for i in a:
    t = 2
    while(i * t <= a_max):
      db[i*t-1] = 0
      t += 1
  print(sum(db))
  

if __name__=='__main__':
  main()

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_right #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()))
maxA = max(A)

# nums = [0]*(maxA+2) # osoi?
nums = set()
A.sort()
sA = list(set(A))
cnt = 0 
ans = defaultdict(int)
for a in sA:
    # print('nums', nums)
    new = False
    # if nums[a]==0:
    if not(a in nums):
        # print(a)
        cnt += 1
        ans[a] += 1
        new = True
    mlt = a
    nums.add(a)
    while new and a + mlt < maxA+2:
        a += mlt
        # print(' a:', a)
        # nums[a] += 1
        nums.add(a)

for an in ans.keys():
    if A.count(an)>1:
        cnt -= 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

def main():
  n = int(input())
  a = list(map(int, input().split(' ')))
  a.sort()
  count = 0
  for i in range(n-1):
    if not (any([a[i] % p == 0 for p in a[:i]+[a[i+1]]])):
      count += 1
  if not (any([a[-1] % p == 0 for p in a[:-1]])):
      count += 1
  print(count)
  

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0] * MAX

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Time Limit Exceeded

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


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0] * MAX

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX and i in setA:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Time Limit Exceeded

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


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        All[k] += 1
        k += i
        if All[i] == 2:
            continue
        while k < MAX and i in setA:
            All[k] += 1
            k += i

    ans = 0
    for i in range(1, MAX):
        if All[i] == 1 and i in setA:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Time Limit Exceeded

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


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    A = LI()
    A.sort()
    MAX = 10**6+1
    All = [0 for i in range(MAX)]

    setA = set(A)
    for i in A:
        k = i
        while k < MAX:
            All[k] += 1
            k += i

    ans = 0
    for i in A:
        if All[i] == 1:
            ans += 1

    print(ans)

    # oj t -c "pypy3 main.py"
    # acc s main.py -- --guess-python-interpreter pypy
main()

Submission status: Time Limit Exceeded

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

ad=[1]*n
an=n

ad = [0 if a.count(a[i])>1 else 1 for i in range(n)]

for i in range(n-1):
    if ad[i]==1:
        for j in range(i+1,n):
            if a[j]%a[i]==0 and ad[j]==1:
                ad[j]=0
print(sum(ad))

Submission status: Time Limit Exceeded

Solution code:
def waru(a,b):
    if a/b==1:
        return 2
    elif b%a==0:
        return 0
    else:
        return 1

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

a.sort()
ad=[1]*n

for i in range(n-1):
    for j in range(i+1,n):
        wk=waru(a[i],a[j])
        if wk==2:
            ad[i]=0
            ad[j]=0
        else:            
            ad[j]=min(ad[j],wk)

print(sum(ad))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros((10**6)+1, dtype=int)

for a in aa:
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().rsplit()]
A.sort()
kekka = []
#print(A)

for i in range(len(A)):
    #A[i] = 100
    kekka.append(len([x for x in A[0:i+2] if A[i] % x == 0]))
    #print(kekka)
    answer = kekka.count(1)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
# a = list(range(1, n))
a.sort()
set_factor = set()
counter = 0

if n != 1:
    if a[0] != a[1]:
        counter += 1
    set_factor.add(a[0])

    for i in range(1, n - 1):
        back = a[i - 1]
        if a[i] != back:
            forward = a[i + 1]
            if a[i] != forward:
                for j in range(1, int(a[i] ** (1/2)) + 1):
                    if a[i] % j == 0:
                        high_factor = a[i] // j
                        if j in set_factor:
                            break
                        elif high_factor in set_factor:
                            break
                else:
                    counter += 1
            set_factor.add(a[i])

    if a[n - 2] != a[n - 1]:
        for j in range(1, int(a[n - 1] ** (1/2)) + 1):
            if a[n - 1] % j == 0:
                high_factor = a[n - 1] // j
                if j in set_factor:
                    break
                elif  high_factor in set_factor:
                    break
        else:
            counter += 1
else:
    counter = 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
factor = []
set_factor = set()
counter = 0
if n != 1:
    if a[0] != a[1]:
        counter += 1

    set_factor.add(a[0])
    factor.append(a[0])

    for i in range(1, n - 1):
        back = a[i - 1]
        forward = a[i + 1]
        if a[i] not in set_factor:
            for j in factor:
                if a[i] % j == 0:
                    break
            else:
                if a[i] != forward and a[i] != back:
                    counter += 1
                set_factor.add(a[i])
                factor.append(a[i])
            
    if a[n - 1] != a[n - 2] :
        for i in factor:
            if a[n - 1] % i == 0:
                break
        else:
            counter += 1
    print(counter)
else:
    print(1)

Submission status: Time Limit Exceeded

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

dp = [1]*(max(a)+1)

for i in sorted(a):
  if 2 == dp[i]:
    continue
  if 3 == dp[i]:
    dp[i] = 2
    continue
  dp[i] = 3
  for j in range(2, max(a)//i + 1):
    dp[j * i] = 2

ans=0
for i in a:
  if dp[i] != 2:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

a.sort()

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

num = 1
count = 1

for i in range(1,n):
    for j in range(num):
        if i+1 < n and a[i] == a[i+1]:
            count -= 1
            break
        if a[i] % a[j]== 0:
            count -= 1
            break
    num += 1
    count += 1
if a[0] == a[1]:
    count -= 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=set()
for i in range(n-1):
    if(lista[i]==lista[i+1]):
        listde.add(lista[i])
t=0
for i in range(n):
    t=0
    for k in listde:
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        listde.add(lista[i])
print(s)

Submission status: Time Limit Exceeded

Solution code:
n=int(input(""))
aa=input("").split(" ")
lista=[]
for i in range(n):
    lista+=[int(aa[i])]
s=0
lista.sort()
listde=[]
for i in range(n-1):
    if(lista[i]==lista[i+1]):
        listde+=[lista[i]]
t=0
for i in range(n):
    t=0
    for k in listde:
        if (lista[i]%k==0):
            t=1
            break
    if (t==0):
        s+=1
        listde+=[lista[i]]
print(s)

Submission status: Time Limit Exceeded

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

ans = [0]*(n)

for i in range(n):
  for j in range(n):
    if i == j:
      continue
    if ans[i] == 1 or ans[j] == 1:
      continue
    if a[i] % a[j] == 0:
      ans[i] = 1
    if a[j] % a[i] == 0:
      ans[j] = 1
print(n - sum(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n=int(input())
inp = list(map(int,input().split()))
c=Counter(inp)
arr=[1]*len(inp)
inp.sort()
ans=0
for i in range(len(inp)):
    if arr[i]==0:
        continue
    else:
        if c[inp[i]]==1:
            ans+=1
        for j in range(i+1,len(inp)):
            if inp[j]%inp[i]==0:
                arr[j]=0
print (ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        if bisect_right(a, i) - bisect_left(a, i) == 1:
            c[i] += 1

print(c.count(1))

Submission status: Time Limit Exceeded

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

counter = 0
while A:
    min_A = min(A.keys())
    if A[min_A] == 1:
        counter += 1

    A = {k: v for (k, v) in A.items() if k%min_A != 0}

print(counter)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
m = max(a)
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        if i in a:
            c[i] += 1

print(c.count(1))

Submission status: Time Limit Exceeded

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

for i in range(n):
    if a[i] == 0:
        continue
    m = a[i]
    for j in range(i + 1, n):
        if a[j] == m:
            a[i] = 0
        if a[j] % m == 0:
            a[j] = 0

ans = sum(x > 0 for x in a)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit


@njit#(fastmath=True)
def fact(x):
    i = 1
    ret = set()
    while i * i <= x:
        if x % i == 0:
            ret.add(i)
            ret.add(x // i)
        i += 1

    return ret


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

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from numba import njit


@njit(fastmath=True)
def fact(x):
    i = 1
    ret = set()
    while i * i <= x:
        if x % i == 0:
            ret.add(i)
            ret.add(x // i)
        i += 1

    return ret


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

    c = [0] * (max(a) + 1)

    for e in a:
        c[e] += 1

    ans = n
    for e in a:
        c[e] -= 1
        for fct in fact(e):
            if c[fct]:
                ans -= 1
                break

        c[e] += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

c = Counter(A)
minus = []
for i in c.items():
  if i[1] > 1:
    minus.append(i[0])

flag = True
A = sorted(set(A))
i = 0
j = len(A)-1

while i < j:
  if A[j] % A[i] == 0:
    A.pop(j)
  j -= 1
  if j == i:
    j = len(A)-1
    i += 1
  
cnt = 0
for n in minus:
  if n in A:
    cnt += 1
ans = len(A) - cnt
print(ans)

Submission status: Time Limit Exceeded

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

#ループ回数が大きくならないように止める
a=sorted(a,reverse=True)

c=[0]*n
for i in range(n):
    if a.count(a[i])>1:
        c[i]=+1
        continue
    for j in range (i+1,n):
        if a[i]<2*a[j]:
            continue
        elif a[i]%a[j]==0:
            c[i]=+1
            break

#print(c)
print(c.count(0))

Submission status: Time Limit Exceeded

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

#ループ回数が大きくならないように止める
a=sorted(a,reverse=True)

c=[0]*n
for i in range(n):
    if a.count(a[i])>1:
        c[i]=+1
        continue
    for j in range (i+1,n):
        if a[i]%a[j]==0:
            c[i]=+1
            break

print(c.count(0))

Submission status: Time Limit Exceeded

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

m = 10**6+10
d = [False] * (m+1)
ans = 0
for i in range(n):
    same = (i > 0 and a[i] == a[i-1]) or (i < (n-1) and a[i] == a[i+1])
    x = a[i]
    if not d[x] and not same: ans += 1
    for j in range(x, m+1, x):
        d[j] = True
    
print(ans)