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: Accepted

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 check_sorted(a):
    ''' returns True/False '''
    for i in range(len(a)-1):
        if a[i]>a[i+1]:
            return False
    return True
def ceil(n, k=1): 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 write(s): return sys.stdout.write(s)












###################################################################
def main():
    #CODE GOES HERE:
    n=ii()
    a=li()
    b=sorted(list(set(a)))
    countd=dd()
    for i in a:
        if i in countd:
            countd[i]+=1
        else:
            countd[i]=1
    answer={}
    for i in b:
        if countd[i]>1:
            answer[i]=False
        else:
            answer[i]=True
    for i in b:
        multiplier=2
        while(i*multiplier<=10**6):
            if i*multiplier in answer:
                answer[i*multiplier]=False
            multiplier+=1
    count=0
    for i in answer:    
        if answer[i]==True:
            count+=1
    print(count)






























""" -------- 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: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
m=max(a)+9
l=[0]*m
for x in a:l[x]+=1
r=0
for i in range(m):
	if l[i]:
		r+=l[i]==1
		for j in range(i,m,i):l[j]=0
print(r)

Submission status: Accepted

Solution code:
from decimal import Decimal
from collections import Counter

N = int(input())
A = sorted([int(_) for _ in input().split()])
max_a = max(A)
min_a = min(A)
counter_A = Counter(A)
set_A = set(A)

for a in A:
  if a not in set_A:
    continue
  
  if counter_A[a] > 1:
    set_A.remove(a)
  
  i = 2
  while True:
    num = a * i
    if num > max_a:
      break
    if num in set_A:
      set_A.remove(num)
    i += 1

print(len(set_A))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
M=max(a)
p=[]
for i in range(n):
    if i+1<=n-1:
        if a[i]==a[i+1]:
            p+=[j for j in range(a[i],M+1,a[i])]
        else:
            p+=[j for j in range(a[i]*2,M+1,a[i])]
    else:
        p+=[j for j in range(a[i]*2,M+1,a[i])]

print(len(set(set(a)-set(p))))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = sorted(map(int, input().split()))
M = A[-1]
c = Counter(A)
s = set()
ans = 0
for a in A:
    if a in s:
        continue
    if c[a] == 1:
        ans += 1
    i = 1
    while a * i <= M:
        s.add(a * i)
        i += 1
print(ans)

Submission status: Accepted

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

ans = 0

baisu = [0]*(a[n-1]+1)
an = a[n-1]

for i in range(n):
    a0 = a[i]
    a1 = a0
    while a1 <= an:
        baisu[a1] += 1
        a1 += a0


for i in range(n):
    if baisu[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
c = Counter(A)
lst = [1] * (10**6+1)
res = 0

for i,a in enumerate(A):
  if lst[a] == 0: continue
  if i==N-1 or A[i+1] != a:
    res += 1
  for j in range(a, 10**6+1, a):
    lst[j] = 0

print(res)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(A)
p = [True]*(10**6+1)

for k, v in c.items():
    t = k*2
    while t <= 10**6:
        p[t] = False
        t += k

ans = 0
for a in A:
    if c[a] == 1 and p[a]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


# def gcd(a, b):
#     if b == 0:
#         return a
#     return gcd(b, a % b)


# def lcm(a, b):
#     return a*b // gcd(a, b)


# def good(A, N):
#     # A = sorted(A)
#     ans = A[0]
#     # for i in range(1, N):
#     #     ans = fractions.gcd(A[i], ans)
#     for i in range(1, N):
#         ans = lcm(ans, A[i])
#     return ans

def primes(n):
    is_prime = [1] * (n + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return is_prime


def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
             return False
    return True


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def coprime(a, b):
    return gcd(a, b) == 1


def factorization(n):
    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 main():
    N = I()
    A = LI()
    MX = 2 * 10**6
    ans = []

    # for i in range(N):
    #     n = []
    #     for j in range(N):
    #         if i == j:
    #             continue
    #         n.append(A[i] % A[j] != 0)
    #     if all(n):
    #         ans.append(i+1)

    # print(len(ans))
    # print([A[i-1] for i in ans])

    a_map = Counter(A)

    n = MX
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = 1 in a_map
    for i in range(1, 10**6 + 1):
        if not is_prime[i]:
            continue
        if i not in a_map:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False

    ans = 0
    for i in range(N):
        if is_prime[A[i]] and a_map[A[i]] == 1:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
cnt = collections.Counter(a)
ans = 0
dp = [0] * (10**6 + 1)
for i in a:
    if dp[i] == 0:
        for j in range(1, 10**7):
            if i * j > 10**6:
                break
            dp[i * j] = 1
        if cnt[i] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

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


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

    N = ii()
    A = il()
    A.sort()

    already = set()
    cnt = collections.Counter(A)
    mx = max(A)
    ret = 0
    for a in A:
        if a in already: continue
        if cnt[a] == 1:
            ret += 1

        i = 1
        while a * i <= mx:
            already.add(a * i)
            i += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
s = set(A)
counter = Counter(A)
A.sort()
ans = [1]*(10**6+1)
for i in range(1,10**6+1):
    if i in s and ans[i]:
        tmp = i
        cnt = 2
        while tmp*cnt <= 10**6:
            ans[tmp*cnt] = 0
            cnt += 1
    else:
        ans[i] = 0
    if counter[i] != 1:
        ans[i] = 0
print(sum(ans)-1)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = [0]*(10**6+1)
mul = set()
for i in range(N):
	if ans[A[i]] == 0:
		ans[A[i]] = 1
		p = A[i]*2
		while p <= 10**6:
			ans[p] = -1
			p += A[i]
	elif ans[A[i]] == 1:
		ans[A[i]] = 2

q = 0	
for i in range(10**6+1):
	if ans[i] == 1:
		q += 1
print(q)

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
if n == 1:
    print(1)
    quit()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
M = max(a)
cnt = [0]*(M+1)
ans = 0
for i in range(n):
    if cnt[a[i]]:
        continue
    j = a[i]
    if i == 0:
        if a[i] == a[i+1]:
            1
        else:
            ans += 1
    elif i == n-1:
        if a[i-1] == a[i]:
            1
        else:
            ans += 1
    elif a[i] == a[i+1] or a[i-1] == a[i]:
        1
    else:
        ans += 1
    while j <= M:
        cnt[j] = 1
        j += a[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
SUPER_A=10**6+1
n=int(input())
a_array=list(map(int,input().split()))
a_array.sort()
div_dict=defaultdict(bool)
count=0
for i in range(n):
    a=a_array[i]
    if div_dict[a]:
        count+=1
    else:
        for j in range(1,math.ceil(SUPER_A/a)):
            div_dict[j*a]=True
        if i + 1 < n and (a_array[i]==a_array[i+1]):
            count+=1
print(n-count)

Submission status: Accepted

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

N,*A = map(int, sys.stdin.buffer.read().split())

S = [0 for _ in range(10**6+1)]
T = [0 for _ in range(10**6+1)]

for a in A:
  S[a] += 1

count = 0
for i in range(1,10**6+1):
  if T[i] == 1:
    continue
  if S[i] == 0:
    continue
  if S[i] == 1:
    count += 1
  for j in range(10**6//i+1):
    T[i*j] = 1

print(count)

Submission status: Accepted

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

table = [0 for i in range(10**6+1)]
ans = 0
a.sort()
a.append(10**7)
for i in range(n):
    el = a[i]
    if table[el] != 0:
        continue
    else:
        if el != a[i+1]:
            ans += 1
    idx = el
    while idx <= 10**6:
        table[idx] += 1
        idx += el

print(ans)

Submission status: Accepted

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

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

num = [0]*1000005
for a in A:
    num[a] += 1

b = [False]*1000005
seen = [False]*1000005
cnt = 0
A = list(set(A))
A.sort()
for a in A:
    if seen[a]:
        continue

    seen[a] = True
    if b[a] == False:
        cnt += 1
        if num[a] > 1:
            cnt -= 1

    for i in range(a, 1000005, a):
        b[i] = True
print(cnt)

Submission status: Accepted

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

A.sort()

maxv = A[-1]
minv = A[0]

cash = set()
ok = set()
ans = 0
p = set()

for i in A:
    if i in cash:
        if i in p:
            ans -= 1
            p.remove(i)
        continue

    else:
        # print("NI:", i)
        # print("CUR:cash", cash)
        p.add(i)

        ans += 1

        c = 1
        cur = i

        while cur <= maxv:
            cash.add(cur)
            c += 1
            cur = i * c
# print(cash)
# print(p)
print(ans)

Submission status: Accepted

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



cnt = Counter(A)
A.sort()
ans = 0
P = [0] * (10**6+1)
#print(cnt)
for a in A:
    if P[a]==0:
        for i in range(10**7):
            x = a*i
            if x>10**6:
                break
            P[x] = 1
        if cnt[a]==1:
            ans +=1

print (ans)

Submission status: Accepted

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

s = set()
x = a[0]

count = 0
for i in range(n):
    flg = True
    flg2 = False
    if i < n - 1 and a[i] == a[i + 1]:
        flg = False
        flg2 = True
    if a[i] in s:
        flg = False
        flg2 = False

    if flg:
        count += 1
    if flg or flg2:
        x = a[i]
        while x <= 10 ** 6:
            s.add(x)
            x += a[i]
print(count)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    d[a[i]] += 1
for i in range(1,1000001):
    if d[i] == 1:
        ans += 1
        for j in range(2,2+10**6//i):
            d[j*i] = 0
    elif d[i] >= 2:
        for j in range(2,2+10**6//i):
            d[j*i] = 0
print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 6)

def debug(s):
    if True:
        print(s)

def get_sieve_of_eratosthenes(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while False:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def filterTrue(a):
    return a

def solve(N: int, A: "List[int]"):
    A = sorted(A)
    table = [False for i in range(A[-1]+1)]
    alreadyDid = set()
    for a in A:
        table[a] = True
    for a in A:
        if a in alreadyDid:
            table[a] = False
            continue
        alreadyDid.add(a)
        i = a*2
        while i < len(table):
            table[i] = False
            i += a
    print(len(list(filter(filterTrue,table))))
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
s = set()
s1 = set()
same_s = set()
ans = 0
for i in a:
    if i in s1:
        same_s.add(i)
    if i not in s:
        s1.add(i)
        ans +=1
        for j in range(10**6 // i + 1):
            s.add(j*i)
print(ans - len(same_s))

Submission status: Accepted

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
  
def main():
  m = int(input())
  a = LI()
  ans = 0
  if a.count(1) == 1:
    print(1)
    exit()
  n = max(a)
  num = [True]*(n+1)
  num[0] = num[1] = False
  a.sort()
  for i in range(m):
    if (i != m-1 and a[i]==a[i+1]) or (i != 0 and a[i]== a[i-1]): num[a[i]] = False
    for j in range(a[i]*2, n+1, a[i]):
      num[j] = False
  for aa in a:
    if num[aa]:
      ans += 1
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def div(arr, n):
    s = dict()


    max_ele = -10 ** 9
    for i in range(n):
        s[arr[i]] = 1

        max_ele = max(max_ele, arr[i])

    res = dict()
    for i in range(n):

        if (arr[i] != 0):

            for j in range(arr[i] * 2,max_ele + 1, arr[i]):

                if (j in s.keys()):
                    res[j] = 1
    return res


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

b=[]
t=0
c=div(a,n)
for i in range(len(a)):
        if a[i] not in c:
            b.append(a[i])
d={}
for i in b:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
for key,val in d.items():
        if val==1:
            t+=1
print(t)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
m=max(a)
dp=[0 for i in range(m+1)]
ans=0
for i in range(n):
    if dp[a[i]]>=1:
        dp[a[i]]+=1
        continue
    for j in range(2*a[i],m+1,a[i]):
        dp[j]+=1 
    dp[a[i]]=1
for i in range(n):
    if dp[a[i]]==1:
        ans+=1 
print(ans)

Submission status: Accepted

Solution code:
def solve(A,N):
    A.sort()
    if N == 1:
        return 1
    elif N == 2:
        if A[1] == A[0]:
            return 0
        elif A[1] % A[0] == 0:
            return 1
        else:
            return 2
    elif A[0] == 1:
        if A[1] >= 2:
            return 1
        else:
            return 0
    else:
        Col = set()
        if A[0] == A[1]:
            Col.add(A[0])
        for i in range(1,N-1):
            if A[i-1] == A[i] or A[i] == A[i+1]:
                Col.add(A[i])
        if A[N-1] == A[N-2]:
            Col.add(A[N-1])

        Mul = set()
        cand = set()
        for i in range(N):
            if A[i] not in Mul:
                if A[i] not in Col:
                    cand.add(A[i])
                for d in range(1,(A[N-1]//A[i])+1):
                    Mul.add(A[i] * d)

        return len(cand)

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

    print(solve(A,N))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

F=[0]*(M+1)

for i in range(N):
    a=A[i]
    b=a
    while b<=M:
        F[b]+=1
        b+=a
    

T=0
for i in range(N):
    if F[A[i]]==1:
        T+=1

print(T)

Submission status: Accepted

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

A.sort()
A.append(-1)

x = A[0]
if x != 1:
    flag = True
    for a in A:
        if a % x != 0:
            flag = False
    if flag:
        print(0)
        exit()

used = [False] * A[-2]
ans = 0
for idx, a in enumerate(A[:-1]):
    if used[a - 1]:
        continue
    if a != A[idx + 1]:
        ans += 1
    for j in range(a, len(used) + 1, a):
        used[j - 1] = True
print(ans)

Submission status: Accepted

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

cand = set(a)

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

dame_set = set()

a.sort()
ret = 0

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

print(ret)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
A.sort()
A2 = set(A)
c = collections.Counter(A)
# print(A)
a = [0]*((10**6)+1)
ans = 0
for i in A2:
    k = 1
    while k <= A[-1]//i:
        a[i*k] += 1
        k += 1
for i in range(1,A[-1]+1):
    if c[i] == 1:
        if a[i] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
n=int(input())
a=list(map(int,input().split()))
if 1 in a:
  if a.count(1)==1:
    print(1)
    sys.exit()
  else:
    print(0)
    sys.exit()
C=list(collections.Counter(a).items())
t=[] 
for i in range(len(C)):
  if C[i][1]>1:
    t.append(C[i][0])
t=set(t) #カブッタヤツら
b=list(set(a))
m=len(b)
b.sort()
Lst=[]
for i in range(m):
  l=2
  num=b[i]*l
  while num<10**6+1:
    Lst.append(num)
    l+=1
    num=b[i]*l
c=set(Lst)
d=set(b)
e=c&d
print(m-len(e)-len(t)+len(e&t))

Submission status: Accepted

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

ans = 0

baisu = [0]*(a[n-1]+1)
an = a[n-1]

for i in range(n):
    a0 = a[i]
    a1 = a0
    while a1 <= an:
        baisu[a1] += 1
        a1 += a0


for i in range(n):
    if baisu[a[i]] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
#if(n!=1 and len(set(a))==1):print(0);exit()
prime_q = []
for i in range(10**6+2):
    prime_q.append(True)
d = {}
for i in a:
    try:d[i] += 1
    except:d[i] = 1
ans = []
for i in set(a):
    if(prime_q[i] == True):
        ans.append(i)
        c = 1
        while(True):
            try:prime_q[i*c] = False
            except:break
            c+=1

num = 0
for i in ans:
    if(d[i] == 1):num+=1
print(num)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
sys.setrecursionlimit(10**8)
from bisect import bisect_left


def divisors(n):
    ret = set()
    for i in range(1, int(n ** 0.5) + 1):
        d, m = divmod(n, i)
        if m == 0:
            ret.add(i)
            ret.add(d)
    return ret


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

    # 愚直に行うとO(N^2)となる
    # 各要素、約数を列挙(sqrt(N))
    # 約数がこれまでに存在したかをチェックO(1)*約数の個数
    # 存在すれば1を加える

    # print(A)
    ans = 0
    history = [False]*N
    for i in range(N):
        if history[i]:
            continue
        # A[i]を乗じていくとどうか
        k = i
        for j in range(2, A[-1]//A[i] + 1):
            k = bisect_left(A, A[i]*j, lo=k)
            # print(A[i], A[i]*j, k, A[k])
            if A[k] % A[i] == 0:
                history[k] = True
        #
        k = bisect_left(A, A[i])
        if k < i:
            history[i] = True
        if i+1 < N and A[i] == A[i+1]:
            history[i] = True
    print(N-sum(history))

    return


if __name__ == '__main__':
    main()