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:





# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod
 
    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)
 
def ncr(n, r,  fact, ifact):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t



def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def ceil(n, k): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []


###################################################################

def main():
    n=ii()
    ar=li()
    hsh=[True]*n

    for i in range(n):
        if hsh[i]:
            for j in range(i,n):
                if j!=i:
                    if ar[j]%ar[i]==0:hsh[j]=False
                    if ar[i]%ar[j]==0:hsh[i]=False
    ctr=0
    #print(hsh)
    for i in range(n):
        if hsh[i]:ctr+=1
    print(ctr,end='')



""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
 
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
 
class IOWrapper(IOBase):
 
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')
 
""" main function"""

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()

Submission status: Time Limit Exceeded

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

dp = [0] * (mx+1)
for i in sorted(set(a)):
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in set(a):
    if dp[i] == 0 and a.count(i) == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = [int(v) for v in input().split()]

l = [1 for i in range(max(A)+1)]
for v in sorted(A):
    for j in range(2*v, max(A)+1, v):
        l[j] = 0

ans = 0
c = Counter(A)
for a in A:
    if c[a] > 1:continue
    ans += l[a]
print(ans)

Submission status: Time Limit Exceeded

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

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

    A_remain = sorted(A_dict.keys())
    limit = A_remain[-1] / 2
    prime = []
    a = A_remain[0]

    while a<=limit and len(A_remain)>0:
        a = A_remain[0]
        prime.append(a)
        A_remain = [i for i in A_remain[1:] if i%a != 0]

    prime.extend(A_remain)
    print(sum([1 for i in prime if A_dict[i]==1]))

main()

Submission status: Time Limit Exceeded

Solution code:





# template by 3xC and starkizard.
# contributors: 

#####################################################################################
from __future__ import division, print_function 

import sys
import os
from collections import Counter, deque, defaultdict
import itertools
import math
import io


"""Uncomment modules according to your need"""


# from bisect import bisect_left, bisect_right, insort
# from heapq import heappop, heapify, heappush
# from random import randint as rn
# from Queue import Queue as Q
# from copy import deepcopy
# from decimal import *
# import re
# import operator

#####################################################################################
# this enables you to write python3 code with PyPy2 (Python 2)
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange

    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip

#####################################################################################

"""value of mod"""
MOD = 998244353
mod = 10**9 + 7

"""Uncomment next 4 lines if doing huge recursion"""
# import threading
# threading.stack_size(1<<27)
# sys.setrecursionlimit(10000

def prepare_factorial(mod=mod):
    """ returns two lists, factorial and inverse factorial modulo argument by default 10**9 +7 """
    # Comment code out when you don't need inverse factorial or vice versa
    fact = [1]
    for i in range(1, 200005):
        fact.append((fact[-1] * i) % mod)

    ifact = [0] * 200005
    ifact[200004] = pow(fact[200004], mod - 2, mod)
    for i in range(200004, 0, -1):
        ifact[i - 1] = (i * ifact[i]) % mod
 
    return fact, ifact

def modinv(n, p):
    """ returns N inverse modulo p """
    return pow(n, p - 2, p)
 
def ncr(n, r,  fact, ifact):
    """ takes 4 arguments: n , r and factorial and inverse factorial lists"""
    t = (fact[n] * (ifact[r]*ifact[n-r]) % MOD)% MOD
    return t


def get_n(Sum):    
    """this function returns the maximum n for which Summation(n) <= Sum"""
    ans = (-1 + sqrt(1 + 8*Sum))//2
    return ans

def sieve(n):
    """ returns a list of prime numbers till n """
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r



def divs(n, start=1):
    """ returns a list of all divisors till n """
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors



def divn(n, primes):
    """ returns the number of divisors, two arguments n and the sieve till n """
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t



def lrfind(d, x, default=-1):
    """ Takes 2 arguments an iterable and an element. returns a tuple (firstoccurence,lastoccurence) -1 if not found """
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return default, default
    else:
        return left, right

def gcd(x, y): # math.gcd is slower
    """ returns greatest common divisor of x and y """
    while y:
        x, y = y, x % y
    return x

def ceil(n, k): return n // k + (n % k != 0) #returns math.ceil but protecting against floating inconsistencies
def input(): return sys.stdin.readline().strip()
def ii(): return int(input()) #inputs integer
def mi(): return map(int, input().split()) # inputting space seperated variables for example x,y,z
def li(): return list(map(int, input().split())) #inputting a space seperated list of integers
def lw(): return input().split() #inputting a space seperated list of strings
def lcm(a, b): return abs(a * b) // gcd(a, b) #returns LCM of two arguments
def prr(a, sep=' ', end='\n'): print(sep.join(map(str, a)), end=end) #For printing an iterable with seperator sep as optional second argument (default : " "), ending character (default: "\n") as optional third
def dd(): return defaultdict(int) #returns a dictionary with values defaulted to 0
def ddl(): return defaultdict(list) #returns a dictionary with values defaulted to []


###################################################################

def main():
    n=ii()
    ar=li()
    hsh=[True]*n

    for i in range(n):
        if hsh[i]:
            for j in range(n):
                if j!=i:
                    if ar[j]%ar[i]==0:hsh[j]=False
                    if ar[i]%ar[j]==0:hsh[i]=False
    for i in range(1,n):
        if ar[0]%ar[i]==0:hsh[0]=False;break    
    ctr=0
    #print(hsh)
    for i in range(n):
        if hsh[i]:ctr+=1
    print(ctr,end='')



""" -------- Python 2 and 3 footer by Pajenegod and c1729 ---------"""
 
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
 
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO, self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill();
            self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
 
class IOWrapper(IOBase):
 
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            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')
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')
 
""" main function"""

if __name__ == '__main__':
    main()
    # threading.Thread(target=main).start()

Submission status: Time Limit Exceeded

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

    A_remain = sorted(A_dict.keys())
    limit = A_remain[-1] / 2
    prime = []
    a = A_remain[0]

    while a<= limit and len(A_remain)>0:
        a = A_remain[0]
        prime.append(a)
        A_remain = [i for i in A_remain[1:] if i%a!=0]

    prime.extend(A_remain)
    print(sum([1 for i in prime if A_dict[i]==1]))

main()

Submission status: Time Limit Exceeded

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

dp = [0] * (mx+1)
for i in a:
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in a:
    if dp[i] == 0 and a.count(i) == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

dp = [0] * (mx+1)
for i in sorted(a):
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in a:
    if dp[i] == 0 and a.count(i) == 1:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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


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

c = Counter(a)
div = [make_divisors(i) for i in a]

ans = 0
for i in range(n):
    val = set(div[i]) & set(a)
    if len(val) == 1:
        if c[list(val)[0]] == 1:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())

argv = input().split()
divisible = 0
count = 0
  
for i in range(N):
  divisible = 0
  for j in range(N):
    if i == j:
      continue
    elif (int(argv[i]) % int(argv[j])) == 0:
      divisible = 1
      break
      
  if divisible == 0:
    count += 1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hp
n = int(input())
a = list(map(int, input().split()))
han = list(map(lambda x:x*(-1), a))
hp.heapify(han)
b = hp.heappop(han)*(-1)
che,re = [0 for i in range(b)],[]
for i in a:
    che[i-1] = 1
for i in a:
    if i in re:
        che[i-1] = 0
    else:
        re.append(i)
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
print(che.count(1))

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
list_a = list(map(int, input().split()))  #リスト入力

def calc_amari(k,l):
    return k % l

count = 0
for i in range(n):
    ai = list_a[i] 
    new_list = copy.deepcopy(list_a)  #  全くの別物としてコピー
    del new_list[i] 
    data2 = []
    for aj in new_list:
        data2.append(calc_amari(ai, aj))
    if 0 not in data2:
        count += 1
    else:
        pass

print(count)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = max(a)
che,re = [0 for i in range(b)],[]
for i in a:
    che[i-1] = 1
for i in a:
    if i in re:
        che[i-1] = 0
    else:
        re.append(i)
        c = b // i
        for j in range(2,c+1):
            che[i*j-1] = 0
print(che.count(1))

Submission status: Time Limit Exceeded

Solution code:
#約数
def make_divisors(n): #約数をリストで返す
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set =set(A)
count =set()
couter =Counter(A)
for a in A:
    if couter[a] >=2:
        count.add(a)
    else:
        divi_set =make_divisors(a)
        intersection =divi_set & A_set
        if len(intersection) >=2:
            count.add(a)
ans =len(A_set - count)
print(ans)

Submission status: Time Limit Exceeded

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

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 10:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

c=Counter(a)

cnt=0
for i in a:
  if is_p[i] and c[i]==1:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
*A, = map(int, input().split())
A.sort()
c = Counter(A)
ans = 0
d = [False]*(10**6+1)
for i in range(N):
    if c[A[i]] == 1:
        ok = True
        for j in range(1, int(A[i]**0.5)+2):
            if A[i] % j == 0 and (d[j] or d[A[i]//j]):
                ok = False
                break
        if ok:
            ans += 1
    d[A[i]] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from collections import Counter

def main():
  n = int(input())
  la = sorted(list(map(int, input().split())))
  primes = [la[0]]
  cands = la[1:]
  while len(cands) != 0:
    prime = primes[-1]
    cands = list(filter(lambda x:x%prime != 0, cands))
    if len(cands) == 0:
      break
    primes.append(cands.pop(0))
  print(len(set(primes) - set([k for k, v in Counter(la).items() if v >= 2])))

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

limit = 10**6 + 2
A += [limit]
dp = [True] * (limit)

ans = 0
for i in range(n):
  a = A[i]
  if dp[a] and a != A[i+1]:
    ans += 1

  for t in range(a,limit,a):    
    dp[t] = False
    t += a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  if s[ai]==2:
    continue
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=nl()

s = [0]*(MAX)

for ai in a:
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

import math

MAX=10**6+1

n=ni()
a=sorted(nl())

s = [0]*(MAX)

for ai in a:
  for i in range(ai,MAX,ai):
    s[i]+=1

cnt=0
for ai in a:
  if s[ai]==1:
    cnt+=1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import numpy as np
U = 10 ** 6 + 1

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

C = Counter(A)
memo = np.zeros(U, dtype=bool)
tmp = np.arange(U)
ans = 0

for k in sorted(C.keys()):
    if memo[k]:
        continue
    if C[k] == 1:
        ans += 1
    memo[tmp % k == 0] = True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-*-coding:utf-8-*-
 
import sys
 
def main():
    numbers=[]
    counter=0
    n = int(input())
    numbers=list(map(int,input().split()))
    dp = [0]*max(numbers)
    dp.append(0)
 
    for i in range(1,max(numbers)+1):
    	for number in numbers:    
            if i % number ==0:
                dp[i]+=1
    for number in numbers:
        if dp[number]==1:
            counter+=1
    print(counter)
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_np =np.array(A,dtype=np.int64)
A_set =set(A)
count =set()
for i in range(N):
    if np.any(A[i] %A_np[:i] ==0) :
            count.add(A[i])
ans =len(A_set - count)
print(ans)

Submission status: Time Limit Exceeded

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

import sys

def main():
    numbers=[]
    counter=0
    n = int(input())
    numbers=list(map(int,input().split()))
    dp = [0]*max(numbers)
    dp.append(0)

    for number in numbers:
        for i in range(1,max(numbers)+1):
            if i % number ==0:
                dp[i]+=1
    for number in numbers:
        if dp[number]==1:
            counter+=1
    print(counter)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

if N == 1:
  print(1)
  exit(0)
#
A.append(10000000) 
if N == 1:
  print(0)
  exit(0)
#
A.sort()
ans = 0

for i in range(N):
  if A[i] == A[i+1] or A[i-1] == A[i]:
    continue
  for j in range(i):
    if A[i] % A[j] == 0:
      break
  else:
    ans += 1
#

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
check = [0] * 1000001
res = 0
for i in range(N):
    if not check[A[i]] and (i == N-1 or A[i] != A[i+1]):
        res += 1
    for j in range(A[i], 1000001, A[i]):
        check[j] = 1
print(res)

Submission status: Time Limit Exceeded

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

count_loop_num=0
for i in range(N):
    count_loop=True
    for j in range(N):
        if A[i]%A[j]==0 and i!=j:
            count_loop=False
            break
    if count_loop==True:
        count_loop_num+=1
print(count_loop_num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
b = [False] * len(A)

for i in range(N):
  for j in range(N):
    if b[j] or i == j or A[i] > 500000:
      continue
    if A[j] % A[i] == 0:
      b[j] = True

# print(b)

print(len(tuple(filter(lambda x: x == False, b))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
b = [False] * len(A)

for i in range(N):
  for j in range(N):
    if b[j] or i == j:
      continue
    if A[j] % A[i] == 0:
      b[j] = True

# print(b)

print(len(tuple(filter(lambda x: x == False, b))))

Submission status: Time Limit Exceeded

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

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
import numpy as np 
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
A.sort()
A_np =np.array(A,dtype=np.int64)
A_set =set(A)
count =set()
for i in range(N):
    if np.count_nonzero(A[i] %A_np[:i] ==0) >=1:
            count.add(A[i])
ans =len(A_set - count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():

    N = int(input())
    A = sorted(list(map(int,input().split())))
    check = [0] * N
    ans = 0

    for i in range(N):
        if check[i] == 1:
            continue
        elif check[i] == 0 and A.count(A[i]) == 1:
            ans += 1
        for j in range(i+1,N):
            if A[j] % A[i] == 0:
                check[j] = 1
            else:
                continue
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#dame datta....
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    l = [0] * (10**6+1)
    for i in A:
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = [0]*(max(A) + 5)
for i in A:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2, max(A) + 5, i):
      ans[j] = 2
print(ans.count(1))

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
count = [0 for _ in range(max(a) + 1)]
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, max(a) + 1, i):
        count[j] = 1
    count[i] = 2

for i in a:
    if count[i] != 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=input()
arr=[int(i) for i in input().strip().split(' ')]
ans=0
for i in range(len(arr)):
    for j in range(len(arr)):
        if i==j or arr[i]<arr[j]:
            continue
        if arr[i]%arr[j]==0:
            break
    else:
        ans+=1
print(ans)
# dic1={}
# dic2={}
# for i in arr:
#     dic1[i]=i
#     dic2[i]=i
# for i in dic1:
#     for j in dic2:
#         if i==j or i:
#             continue
#         if dic1[i]%dic2[j]==0:
#             break
#     else:
#         ans+=1    
# print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
count = [0] * (max(a) + 1)
ans = 0

for i in a:
    if count[i] != 0:
        count[i] = 1
        continue
    for j in range(2 * i, max(a) + 1, i):
        count[j] = 1
    count[i] = 2

for i in a:
    if count[i] != 1:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=input()
arr=[int(i) for i in input().strip().split(' ')]
ans=0
for i in range(len(arr)):
    for j in range(len(arr)):
        if i==j:
            continue
        if arr[i]%arr[j]==0:
            break
    else:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
if N == 1:
  print(1)
  exit()
  
A=[int(_) for _ in input().split(" ")]

if A.count(1)==1:
  print(1)
  exit()

if A.count(1)>1:
  print(0)
  exit()

A.sort(reverse=True)
#print(A)

ans=[]

flg=0 
for i in range(N):
  flg=0
  if i == 0:
    if A[i]==A[i+1]:
      flg=1
  elif i==N-1:
    if A[i]==A[i-1]:
      flg=1
  else:
    if A[i]==A[i+1] or A[i]==A[i-1]:
      flg=1

  if flg == 0:
    for j in range(0,N-1-i):
      #print(i,j,A[i],A[N-1-j])
      if A[i] % A[N-1-j] == 0:
        flg=1
        break
      if A[i]/2 < A[N-1-j]:
        break
      
  if flg == 0:
    ans.append(i)
  else:
    flg = 0

#print(ans)
print(len(ans))