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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
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

N = INT()
A = LIST()

def primes_for(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n + 1):
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

ans = 0
lim = 10**6+1
ok = [True]*lim

for a in sorted(A):
    for j in range(a*2, lim, a):
        ok[j] = False

cnt = Counter(A)
for a in A:
    if cnt[a] == 1 and ok[a]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
from collections import Counter, defaultdict

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

memo = [None] * (max(A) + 1)

S = set(A)
counts = Counter(A)
ans = 0
for a in A:
    if counts[a] >= 2:
        continue
    if memo[a] is not None:
        ans += memo[a]
        continue
    ok = True
    for d in get_divisors(a):
        if d == a:
            continue
        ok &= d not in S
        if not ok:
            break
    ans += ok
    memo[a] = ok
print(ans)

exit()
factors = []
for a in A:
    fs = get_factors(a)
    factors.append(fs)
    for f in fs:
        counts[f] += 1

ans = 0
for i, a in enumerate(A):
    fs = factors[i]
    ok = True
    for k, v in Counter(fs).items():
        ok &= counts[k] == v
    ans += ok
    print(i, a, ok)
print(ans)

# TODO: 1

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    b = set(A)
    def find(x):
        l = make_divisors(x)
        for j in l:
            if j == x:
                if a[j] > 1:
                    return 0
            else:
                if j in b:
                    return 0
        return 1
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


def main():
    n = int(input())
    a = list(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:
def examA():
    X = LI()
    for i in range(len(X)):
        if X[i]==0:
            ans = i+1
    print(ans)
    return

def examB():
    X, Y = LI()
    ans = "No"
    for i in range(X+1):
        if i*2+(X-i)*4==Y:
            ans = "Yes"
    print(ans)
    return

def examC():
    X, N = LI()
    P = LI()
    P = set(P)
    cur = inf
    ans = -1
    for i in range(-1,102):
        if i in P:
            continue
        now = abs(i-X)
        if now<cur:
            ans = i
            cur = now
    print(ans)
    return

def examD():
    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
    N = I()
    A = LI()
    C = set()
    D = set()
    ans = 0
    for a in A:
        if a in D:
            C.discard(a)
            continue
        D.add(a)
        C.add(a)

    for a in C:
        flag = 2
        cur = make_divisors(a)
        for c in cur:
            if c in D:
                flag -= 1
            if flag==0:
                break
        if flag>0:
            ans += 1
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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()
yakusu = [[] for i in range(10**6 + 1)] 
for q,a in enumerate(A):
    Y = make_divisors(a)
    for n in range(len(Y)-1):
        yakusu[Y[n]].append(q)

Ans = [True] * N
for n,a in enumerate(A):
    if C[a] >=2:
        Ans[n] =False
    for tf in yakusu[a]:
        Ans[tf] = False
print(sum(Ans))

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def divide(x): #約数配列
    div=[]
    for check in range(1,int(x**0.5)+1):
        if(x%check==0):
            div.append(check)
            div.append(x//check)
    div.sort()
    return div

def main():
    n = inp()
    a = inpl()
    dic = defaultdict(int)
    a.sort()
    ans = 0
    for i in range(n):
        div = divide(a[i])
        flag = 1
        for e in div:
            if dic[e]:
                flag = 0
                break
        if i < n-1 and a[i] == a[i+1]:
            flag = 0
        if flag:
            ans += 1
        dic[a[i]] = 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

for a in A:
    A = [x for x in A if (x == a or x % a != 0)]

counter = Counter(A)
print(len([0 for v in counter.values() if v == 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))

table = [0] * (max(a) + 1)
for x in a: table[x] += 1
#print(table)
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

res = 0
for x in a:
  if table[x] > 1: continue
  for y in make_divisors(x):
    if x == y: continue
    if table[y]: break
  else: res += 1
print(res)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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

dic = {}
ans = 0
lis = [0] * (10**6+1)

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        lis[A[i]] = 1
        continue

    j = 1
    flag = True
    while j ** 2 <= A[i]:

        if A[i] % j == 0:
            k = A[i] // j

            if lis[j] > 0:
                flag = False
                break
            if lis[k] > 0:
                flag = False
                break

        j += 1

    if flag:
        ans += 1
    lis[A[i]] = 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def yakusu(n):
    yakusu = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            yakusu.append(i)
            if n // i != i:
                yakusu.append(n//i)
    return yakusu
     
def main():
    N = I()
    A = LI()
    s = collections.Counter(A)
    cnt = 0
    for a in A:
        flag = True
        for y in yakusu(a):
            if y == a and s[y] == 1:
                continue
            if y in s:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)



main()

Submission status: Time Limit Exceeded

Solution code:
def factor(N):
    arr=[]
    for i in range(1,int(N**0.5)+1):
        if(N%i==0):
            arr.append(i)
            if(N//i!=i):
                arr.append(N//i)
    return arr

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

cnt=[0]*1000001
for i in range(N):
    cnt[A[i]]+=1
ng=set()
for i in range(N):
    if cnt[A[i]]>1:
        ng.add(A[i])

s=set(A)

ans=0
for i in range(N):
    if A[i] in ng:
        continue
    s.remove(A[i])
    arr=factor(A[i])
    ok=True
    for x in arr:
        if x in s:
            ok=False
            break
    if ok:
        ans+=1
    s.add(A[i])
print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = int(input())
    A = LII()
    A.sort()

    B = A.copy()

    for a in A:
        c = B.count(a)
        B = list(filter(lambda x: x % a != 0, B))
        if c == 1:
            B.append(c)

    print(len(B))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = [int(x) for x in input().split()]
a_set = set(a)
#約数の列挙
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
from collections import Counter
c = Counter(a)
cnt = 0
for i in a:
    prime = make_divisors(i)
    flag = 1
    if c[i] > 1:
        continue
    for j in prime:
        if j == i:
            continue
        if j in a_set:
            flag = 0
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [int(x) for x in input().split()]
b = [0] * 1000001

for x in a:
    for y in range(x, 1000001, x):
        b[y] += 1

cnt = 0

for x in a:
    if b[x] == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter as ct
    n = int(input())
    a = ct(list(map(int, input().split())))
    a2 = sorted([i for i, j in a.items() if j == 1])
    a3 = sorted([i for i, j in a.items() if j > 1])

    s = set()
    ans = 0
    for i in a3:
        for j in s:
            if i % j == 0:
                break
        else:
            s.add(i)
    for i in a2:
        for j in s:
            if i % j == 0:
                break
        else:
            ans += 1
            s.add(i)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import os
from collections import Counter

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :rtype: list of int
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

S = set(A)
counts = Counter(A)
ans=0
for a in A:
    if counts[a] >= 2:
        continue
    ok = True
    for d in get_divisors(a):
        if d == a:
            continue
        ok &= d not in S
    ans +=ok
print(ans)

exit()
factors = []
for a in A:
    fs = get_factors(a)
    factors.append(fs)
    for f in fs:
        counts[f] += 1

ans = 0
for i, a in enumerate(A):
    fs = factors[i]
    ok = True
    for k, v in Counter(fs).items():
        ok &= counts[k] == v
    ans += ok
    print(i, a, ok)
print(ans)

# TODO: 1

Submission status: Time Limit Exceeded

Solution code:
def divisor(n):
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append(i)
            if i*i != n:
                ret.append(n//i)
    return ret

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

m = 10**6 + 1
c = [0]*m
for i in a:
    c[i] += 1

ans = 0
for i in a:
    if c[i] > 1:
        continue
    for j in divisor(i):
        if j == i:
            if c[j] > 1:
                break
        else:
            if c[j] > 0:
                break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


n = int(input())
a = list(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)

Submission status: Time Limit Exceeded

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

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(reverse=True)
    return divisors

X = []
for i in range(n):
    d = make_divisors(A[i])
    X.append(d)

l = [0]*n
r = [0]*n
S = set()
for i in range(n):
    for x in X[i]:
        if x in S:
            break
    else:
        l[i] = 1
    S.add(A[i])

S = set()
for i in reversed(range(n)):
    for x in X[i]:
        if x in S:
            break
    else:
        r[i] = 1
    S.add(A[i])

#print(l)
#print(r)
ans = 0
for i in range(n):
    if l[i] == 1 and r[i] == 1:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ok = [True for _ in range(10**6+1)]
ans = 0
for i, x in enumerate(a):
	if ok[x]:
		if i == n-1:
			ans += 1
		elif a[i+1] != x:
			ans += 1
	for y in range(x, 10**6+1, x):
		ok[y] = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    def find(x):
        l = make_divisors(x)
        for j in l:
            if j == x:
                if a[j] > 1:
                    return 0
            else:
                if j in a:
                    return 0
        return 1
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def divisors(n):
    i = 1
    r = []
    while i * i <= n:
        if n % i == 0:
            r.append(i)
            if i != n // i:
                r.append(n // i)
        i += 1
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dup = set()
    T = set()
    for a in A:
        if a in T:
            dup.add(a)
        else:
            T.add(a)
    r = 0
    for a in A:
        if a in dup:
            continue
        for d in divisors(a):
            if d == a:
                continue
            if d in T:
                break
        else:
            r += 1
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 10 ** 9 + 7
def wari(n):
    res = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            res.append(i)
            res.append(n // i)

    return res

def solve():
    n = getN()
    nums = getList()
    cnt = Counter(nums)
    ans = 0
    for num in nums:
        flag = True
        # print(wari(num))
        for r in wari(num):
            if r in cnt.keys() and (r != num or cnt[r] > 1):
                flag = False
                # print(r)
                break
        if flag:
            ans += 1

    print(ans)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def fact(x):
    i = 1
    while i * i <= x:
        if x % i == 0:
            yield i
            yield x // i
        i += 1


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

c = Counter(a)

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)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math


def factors(n):
    fhead = []
    ftail = []
    for x in range(1, int(math.sqrt(n)) + 1):
        if n % x == 0:
            fhead.append(x)
            if x * x != n:
                # This check is to not insert sqrt(n) twice in head and tail portion of the list
                ftail.append(n // x)
    return fhead + ftail[::-1]


(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

freq = Counter(A)
count = 0
for x in A:
    bad = False
    for d in factors(x):
        if (d == x and freq[d] >= 2) or (d != x and freq[d]):
            bad = True
            break

    if not bad:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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

dic = {}
ans = 0

for i in range(N):

    if i != N-1 and A[i+1] == A[i]:
        dic[A[i]] = 1
        continue

    j = 1
    flag = True
    while j ** 2 <= A[i]:

        if A[i] % j == 0:
            k = A[i] // j

            if j in dic:
                flag = False
                break
            if k in dic:
                flag = False
                break

        j += 1

    if flag:
        ans += 1
    dic[A[i]] = 1

print (ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
def divisor(n):
    ret = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ret.append(i)
            if i*i != n:
                ret.append(n//i)
    return ret
from collections import Counter
c = Counter(a)
ans = 0
for i in a:
    for j in divisor(i):
        if j == i:
            if c[j] > 1:
                break
        else:
            if c[j] > 0:
                break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr)
s=set()
cnt=collections.Counter(arr)
for i in range(n):
  if arr[i] in s:
    continue
  for j in range(2,10**6//arr[i]+1):
    s.add(arr[i]*j)
ans=0
for i in range(n):
  if arr[i] in s:
    continue
  if cnt[arr[i]]>=2:
    continue
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    M = 10**6

    A.sort()
    C = Counter(A)
    ans = 0
    seen = [0] * (M+1)
    for a in A:
        if C[a] == 1 and seen[a] == 0:
            ans += 1
        for j in range(1, M+1):
            if a * j > M:
                break
            seen[a*j] = 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    N = 10**6
    f = [1]*(N+1)
    a.sort()
    cnt = [0]*(N+1)
    for i in a:
        cnt[i] += 1
    for i in range(N+1):
        if cnt[i] > 1:
            f[i] = 0
    ans = 0
    for i in a:
        if f[i]:
            ans += 1
        x = i
        while x <= N:
            f[x] = 0
            x += i
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from typing import List
from collections import Counter


def get_no_dupes(arr: List[int]) -> List[int]:
    cntr = Counter(arr)
    ret = []
    for elem in cntr:
        if cntr[elem] == 1:
            ret.append(elem)
    return ret


def main() -> None:
    input()

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

    busted = [False] * (10 ** 6 + 10)

    seen = set()
    max_limit = 10 ** 6
    for num in arr:
        if num in seen:
            continue
        for i in range(2 * num, max_limit + 1, num):
            busted[i] = True
        seen.add(num)

    arr = get_no_dupes(arr)
    cnt = 0
    for num in arr:
        if not busted[num]:
            cnt += 1

    print(cnt)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, **kwargs):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter

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

cnt = Counter(A)

b = np.array([0]*(max(A)+1))

A.sort()
ans = 0
for a in A:
    if cnt[a] == 1 and not b[a]:
        ans += 1
    b[a::a] = 1

print(ans)

Submission status: Accepted

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = float('inf')

N = int(input())    # 数字
A = list(map(int, input().split()))     # スペース区切り連続数字

m = max(A)
num = [0] * (m + 1)
for a in A:
    num[a] += 1

for a in A:
    if num[a] > 1:
        num[a] = 0
    i = 2
    while a * i <= m:
        num[a * i] = 0
        i += 1

res = 0
for n in num:
    if n != 0:
        res += 1

print("{}".format(res))

Submission status: Accepted

Solution code:
import sys

n = int(input())
arr= list(map(int,sys.stdin.readline().split()))
arr = sorted(arr)
max_num = max(arr)
dp = [0 for i in range(max_num+1)]
for i in arr:
    j = i
    while j<=max_num:
        dp[j]+=1
        j+=i
ans = 0
for i in arr:
    if dp[i] == 1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = 10**6 + 1
cnt = [0] * M
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
print(ans)

Submission status: Accepted

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))
A.sort()
cnt = collections.Counter(A)
#print(cnt)
for a in A:
    if cnt[a] >= 2:
        del cnt[a]
    for j in range(2*a, A[-1]+1, a):
        del cnt[j]
#print(cnt)
print(len(cnt))