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:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key

# from numpy import gcd


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    # ds = set(mulinputs())

    # if len(ds) <= 1:
    #     print(0)
    #     exit()
    # ds = list(ds)
    # # ds.sort()
    # if ds[0] == 1:
    #     print(0)
    #     exit()
    # p = []
    # l = int(sqrt(len(ds)))
    # # for _ in range(l):
    # #     if not ds:
    # #         break
    # while ds:
    #     tmp = ds.pop(0)
    #     p.append(tmp)
    #     ds = [ d for d in ds if d % tmp != 0]
# 
    # # 出力
    # print(len(p)+len(ds))


    # ======
    # 参考:https://atcoder.jp/contests/abc170/submissions/14360996
    # ======
    # N <= 2*10**5なので6乗あれば絶対安心
    M = 10**6+1
    # 0 は 0個という意味とfalseという意味
    memo = [0] * M
    ds = list(mulinputs())
    # Trueという意味と、iがいくつあるか(同値の個数をカウント)
    for i in ds: memo[i] += 1
    ds.sort()
    ans = []
    for i in ds:
        if not memo[i]:
            continue
        if memo[i] == 1:
            ans += [i]
        # iの倍数のフラグを落としていく
        for j in range(i, M, i): memo[j] = 0
    # 出力
    print(len(ans))

Submission status: Accepted

Solution code:
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

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

c=Counter(a)

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

print(cnt)

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort()
    cho=set()
    for i in range(len(A)-1):
        if A[i]==A[i+1]:
            cho.add(A[i])
    A=list(set(A))
    SUGOI=[False]*(10**6+1)
    for a in A:
        for j in range(2*a,10**6+1,a):
            SUGOI[j]=True
    cnt=0
    A=list(set(A)-cho)
    for a in A:
        if SUGOI[a]==False:
            cnt+=1
    print(cnt)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)
M = max(a)
isprime = [0]*(M+1)

for i in range(n):
    if isprime[a[i]]==0:
        isprime[a[i]] = 1
        tmp = 2
        while a[i]*tmp < M+1:
            isprime[a[i]*tmp] = 2
            tmp += 1
    elif isprime[a[i]] == 1:
        isprime[a[i]] = 2

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

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    max_a = max(A)
    m = set()
    checked = set()
    duplicated = set()

    for a in A:
        if a in checked:
            duplicated.add(a)
            continue

        i = 2
        while a*i <= max_a:
            m.add(a*i)
            i += 1

        checked.add(a)

    ans = 0
    for a in A:
        if a in duplicated: continue

        if a not in m:
            ans += 1
    
    print(ans)
 
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter

def main():
  n, *A = map(int, open(0).read().split())
  A.sort()
  n = A[-1]
  isPrime = [True] * (n + 1)
  prep = 0
  for i in A:
    if prep == i:
      isPrime[prep] = False
      continue
    if isPrime[i]:
      for j in range(i * 2, n + 1, i):
        isPrime[j] = False
    prep = i

  prep = res = 0
  for i in A:
    if prep == i:
      continue
    if isPrime[i]:
      res += 1
    prep = i
  print(res)
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)+1

numbers = [0] * m

for i in a:
    numbers[i] += 1

    if numbers[i] == 1:
        for j in range(2*i, m, i):
            numbers[j] += 2

print(numbers.count(1))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    list.sort(A)
    pre_A = -1
    dp = [True for i in range(A[-1]+1)]
    for i in range(N):
        if pre_A != A[i]:
            for j in range(2,A[-1]+1):
                x = j*A[i]
                if x <= A[-1]:
                    dp[x] = False
                else:
                    break
            pre_A = A[i]
        else:
            dp[A[i]] = False
            
    count = 0
    for i in range(N):
        if dp[A[i]]:
            count += 1
    print(count)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
n = int(input())
a = list(map(int, stdin.readline().split()))
a.sort()
amax = max(a)+1
e = [0]*amax
ans = 0

for i in range(n):
    e[a[i]] += 1
    if e[a[i]] == 1:
        for j in range(2*a[i], amax, a[i]):
            e[j] += 2

print(e.count(1))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

d = {}
for i in a:
    if i in d: d[i] += 1
    else: d[i] = 1

M = 10**6+1
sieve = [0]*(M)
for k,v in d.items():
    for i in range(k,M,k):
        sieve[i] += v


ans = 0
for ai in a:
    if sieve[ai] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
n = int(input())
a = list(map(int,input().split()))
max_a = 10**6 +1 
a = sorted(a)
dic = defaultdict(lambda: False)

count = 0 
for i in range(n):
    ai = a[i]
    if dic[ai] == True:
        count+=1
    else:
        for j in range(1,math.ceil(max_a/ai)):
            dic[j*ai] = True
        if (i+1) < n and a[i]==a[i+1]:
            count+=1
print(n-count)

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np

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

@njit
def main(A):
  count = np.zeros(10**6 + 10, np.int32)
  
  for i in range(N):
    a = A[i]
    if count[a] > 1:
      continue
    count[::a] += 1
    
  ans = 0
  for i in range(N):
    ans += count[A[i]] == 1
    
  #print(count[:100])
  return ans
  
print(main(np.array(A, np.int32)))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
counter = [0]*(maxA+1)
for ai in A:
    for m in range(ai, maxA+1, ai):
        counter[m] += 1
ans = 0
for ai in A:
    ans += (counter[ai] == 1)
print(ans)

Submission status: Accepted

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

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

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

        
    
    print(ans)
main()

Submission status: Accepted

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

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

    for idx in range(len(a)):
        if idx + 1 != len(a) and a[idx] == a[idx + 1]:
            dp[a[idx]] = False
        i = a[idx]
        x = 2
        while i * x < max_a:
            dp[i * x] = False
            x += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(map(int,input().split()))
m=max(A)
ans=0
dp=[True]*(m+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i==N-1:
        ans+=1
    elif i<N-1 and A[i+1]!=A[i]:
        ans+=1
    for j in range(1,m//A[i]+1):
        dp[A[i]*j]=False
print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort()
    maxa = aa[-1]
    dp = [False]*(maxa+1)
    for a in aa:
        dp[a] = True
    dup = set()
    for a in aa:
        if a in dup:
            dp[a] = False
            continue
        else:
            dup.add(a)
        if dp[a]:
            for j in range(a*2,maxa+1,a):
                dp[j] = False
    print(sum(1 for d in dp if d))



if __name__ == '__main__':
    main()

Submission status: Accepted

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

ndiv_sum = 0
max_num = A[-1]
no_div = [True] * (max_num+1)
for i in range(len(A)-1):
    if no_div[A[i]]:
        for j in range(A[i], max_num+1, A[i]):
            no_div[j] = False
        if A[i]!=A[i+1]:
            ndiv_sum += 1
if no_div[A[-1]]:
    ndiv_sum += 1
print(ndiv_sum)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = list(set(A))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)

Submission status: Accepted

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

a = sorted(a)

max = a[len(a)-1]
line = [0]*(max+1)

for x in a:
    line[x] += 1
    
for x in a:
    if line[x] == 0:
        continue
    xx = x * 2
    j = 3
    while xx <= max:
        if line[xx] != 0:
            line[xx] = 0
        xx = x * j
        j += 1
for i in range(max+1):
    if line[i] == 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
from collections import Counter

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

m=a[-1]+1
dp=[True]*m
c=Counter(a)
ans=0
for x in a:
    if dp[x] and c[x]==1:
        ans+=1
    
    for j in range(2*x, m, x):
        dp[j]=False

print(ans)

Submission status: Accepted

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

ans=0
dp=[True]*(10**6+1)
for i in range(N):
    if not dp[A[i]]:
        continue
    if i==N-1:
        ans+=1
    elif i<N-1 and A[i+1]!=A[i]:
        ans+=1
    for j in range(1,10**6//A[i]+1):
        dp[A[i]*j]=False
print(ans)

Submission status: Accepted

Solution code:
# # -*- coding: utf-8 -*-
import collections
N = int(input())
A = list(map(int, input().split(' ')))

a_frq_dict = collections.Counter(A)
A = sorted(a_frq_dict.keys())

bads = set()
max_a = max(A)
n = len(A)
for i in range(n):
    if A[i] in bads:
        pass

    elif a_frq_dict[A[i]] > 1:
        bads.add(A[i])
        for a in range(A[i]*2, max_a+1, A[i]):
            if a in a_frq_dict:
                bads.add(a)

    else:
        for a in range(A[i]*2, max_a+1, A[i]):
            if a in a_frq_dict:
                bads.add(a)

answer = set(A) - bads
# print(answer)
print(len(answer))

Submission status: Accepted

Solution code:
# D - Not Divisible
from collections import Counter

N = int(input())
A = list(int(a) for a in input().split())
c = Counter(A)
ng = set([i[0] for i in c.items() if i[1] >= 2])
A.sort()

M = max(A)
primes = []
is_prime = [True] * (M+1)
for i, a in enumerate(A):
    if is_prime[a]:
        if a not in ng:
            primes.append(a)
        for j in range(a*2, M+1, a):
            is_prime[j] = False
print(len(primes))

Submission status: Accepted

Solution code:
import numpy as np
import math
import collections
import bisect
from collections import Counter


N = int(input())

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

A.sort()
Set = set()

Amax = A[len(A) - 1]

counter = Counter(A)
ans = 0
for a in A:
    if a in Set:
        continue
    x = a
    while(x <= Amax):
        Set.add(x)
        x += a

    if counter[a] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
dp = [1 for i in range(10**6+10)]
for i in range(n):
    if dp[a[i]] == 1:
        dp[a[i]] = 2
        for j in range(2*a[i], 10**6+10, a[i]):
            dp[j] = 0
    elif dp[a[i]] == 2:
        dp[a[i]] = 0
res = 0
for i in range(n):
    if dp[a[i]] == 2:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    n=int(input())
    A=list(map(int,input().split()))
    A.sort()
    C=Counter(A)
    m=A[-1]
    Flag=[True]*(m+1)
    ans=0
    for i,a in enumerate(A):
        if Flag[a]:
            ans+=int(C[a]==1)
            for i in range(a*2,m+1,a):
                Flag[i]=False
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# D

N = int(input())

d = [0] * (10**6 + 1) 
A = list(map(int, input().split()))

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

ans = 0
maxa = max(A) + 1
for i in range(1,maxa):
  if d[i] == 1:
    ans += 1

  if d[i] > 0:
    # d[i]の倍数は含めない
    for j in range(i*2,maxa,i):
      d[j] = 0

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

is_p=[1 for i in range(10**6+1)]

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

c=Counter(a)

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

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque, defaultdict, Counter
N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
s = list(set(c))

dp = [True] * (10 ** 6 + 1)

for x in s:
  num = x * 2
  while num <= 10 ** 6:
    dp[num] = False
    num += x

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

Submission status: Accepted

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

A.sort()
S = set(A)
M = max(A)

preA = 0
for i in A :
  if preA == i :
    S.discard(i)
  if i in S :
    num = i * 2
    while num <= M :
      S.discard(num)
      num += i    
  preA = i
  
print(len(S))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
from collections import Counter
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    count = Counter(A)
    S = list(set(A))
    S.sort()
    max_A = max(A)

    bl = [True] *(max_A+1)

    for x in S:
        if bl[x] == False:
            continue
        t = x*2
        while t<=max_A:
            bl[t] = False
            t += x

    ans = 0
    for x in S:
        if count[x]==1 and bl[x]==True:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()

list_a = [0] * (10 ** 6 + 1)
list_b = [0] * (10 ** 6 + 1)

for i in A:
    list_a[i] += 1

ans = 0
for i in range(1, 10 ** 6 + 1):
    if not list_a[i]:
        continue
    if list_a[i] == 1 and not list_b[i]:
        ans += 1
    for j in range(1, 10 ** 6 + 1):
        if i * j >= 10 ** 6 + 1:
            break
        list_b[i * j] = 1
print(ans)

Submission status: Accepted

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

A.sort()
V = set()

ans = 0
mx = max(A)
for a in A:
    if a in V:
        continue
    if cntA[a] == 1:
        ans += 1

    p = a
    while p <= mx:
        V.add(p)
        p += a

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = set()
C = set()
for a in A:
    if a in B:
        C.add(a)
    else:
        B.add(a)
M = max(B)
bool = [1]*(M+1)
for c in C:
    bool[c] = 0
for b in B:
    for i in range(b*2, M+1, b):
        bool[i] = 0
ans = 0
for a in A:
    if bool[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

dp = [0] * (10**7)

cnt = 0
for i in range(n):
    if dp[arr[i]] == 0:
        for j in range(1, (10**6 + 10) // arr[i] + 1):
            dp[arr[i] * j] += 1
        if i < n - 1:
            if arr[i] == arr[i + 1]:
                continue
        cnt += 1
    else:
        continue

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]

c = [0] * (m + 1)
for i in range(n):
    for j in range(a[i], m + 1, a[i]):
        c[j] += 1

ans = 0
for e in list(set(a)):
    if c[e] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6

c = Counter(a)
arr = np.zeros(MAX + 1, np.int64)
st = set()
for k, v in c.items():
    if v != 1:
        st.add(k)
    arr[k] = 1

for i in range(MAX + 1):
    if arr[i]:
        arr[i*2::i] = 0

    if i in st:
        arr[i] = 0

print(arr.sum())

Submission status: Accepted

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

A_max = max(A)
L = [0]*(A_max+1)
A.sort()

for a in A:
    temp = a
    while temp < A_max+1:
        L[temp] += 1
        temp += a

ans = 0
for a in A:
    if L[a] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N = I()
A = LI()
A = sorted(A)

if A[0] == 1:
    if N >= 2 and A[1] == 1:
        print(0)
        exit()
    else:
        print(1)
        exit()

B = [0]*(10**6+1)  # B[i] = iがAの元の倍数になっていたら1
C = [0]*(10**6+1)  # C[i] = iが条件を満たすとき1
for i in range(len(A)):
    if B[A[i]] == 0:
        C[A[i]] = 1
    for j in range(A[i],10**6+1,A[i]):
        B[j] = 1

from collections import Counter

c = Counter(A)

for i in c.keys():
    if c[i] >= 2:
        C[i] = 0

print(sum(C))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        pass
    elif bl[a]:
        answer += 1
    if bl[a]:
        bl[a] = False
        next = a + a
        while next <= A[-1]:
            bl[next] = False
            next += a

print(answer)

Submission status: Accepted

Solution code:
import itertools
from collections import Counter
h = int(input())
if h == 1:
	print(1)
	exit()
a = list(map(int,input().split()))
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def sieve(n):
	ret = []
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.append(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

k = sieve(1000)

def pfact(m):
	pf = {}
	cnt = 0
	i = k[cnt]
	st = len(k)
	while m > 1 and cnt < st:
		i = k[cnt]
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
		cnt += 1
	if m>1 : pf[m]=1
	return pf

def makediv(n):
	s = pfact(n)
	k = [range(i+1) for i in s.values()]
	ansl = []
	for i in itertools.product(*k):
		ans = 1
		for n, j in enumerate(s.keys()):
			ans *= (j**i[n])
		ansl.append(ans)
	ansl.sort()
	return ansl

ans = 0
for i in b:
	t=makediv(i)
	t.remove(i)
	mode = 1
	for l in t:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    N=I()
    A=LI()
    M=10**6+5
    dp=[1]*M
    A.sort()
    L=[A[0]]
    L2=set([])
    for i in range(1,N):
        if A[i]!=L[-1]:
            L.append(A[i])
        else:
            L2.add(A[i])
            
    for i in range(len(L)):
        temp=L[i]
        if dp[temp]==1:
            temp+=L[i]
            while temp<M:
                dp[temp]=0
                temp+=L[i]
        
    ans=0    
    for i in L2:
        dp[i]=0
        
    for i in range(len(L)):
        if dp[L[i]]==1:
            ans+=1
            
            
    

         
            
    print(ans)
                
    
    


main()

Submission status: Accepted

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

used = [False] * a[-1]
res = 0
for i in range(n):
    if used[a[i]-1]:
        continue
    if i == n - 1 or a[i] != a[i+1]:
        res += 1
    for j in range(a[i], a[-1]+1, a[i]):
        used[j-1] = True

print(res)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
c = Counter(ns)
ans = 0

l = [True] * (max(ns)+1)
for i in sorted(set(ns)):
    if l[i]:
        j = i*2
        while j < len(l):
            l[j] = False
            j += i

a = set([key for key, value in c.items() if value == 1])
for i in a:
    if l[i]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
a = sorted(list(a))
ma = max(a)

div = defaultdict(bool)
count = 0
for i in range(n):
    b = a[i]
    if div[b]:
        count += 1
    else:
        for j in range(1,ma//b+1):
            div[j*b] = True
        if(i+1<n and a[i] == a[i+1]):
            count += 1

print(n-count)

Submission status: Accepted

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

import numpy as np
from numba import njit


def main():
    @njit('i8(i4[::1],)', cache=True)
    def f(A):
        count = np.zeros((A.max() + 1))
        for a in A:
            if count[a] > 1:
                continue
            count[::a] += 1

        ret = 0
        for a in A:
            ret += count[a] == 1

        return ret

    N = int(input())
    A = np.array(readline().split(), np.int32)

    print(f(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D

N = int(input())

d = [0] * (10**6 + 1) 

for a in map(int, input().split()):
  d[a] += 1

ans = 0

for i in range(1,10**6+1):
  if d[i] == 1:
    ans += 1

  if d[i] > 0:
    # d[i]の倍数は含めない
    for j in range(i*2,10**6+1,i):
      d[j] = 0

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
C = Counter(A)
s = []
dp = [True] * (10 ** 6 + 1)

for a, b in C.items():
    if b == 1:
        s.append(a) 

a = set(A)
for ss in a:
    for m in range(2 * ss, 10 ** 6 + 1, ss):
        dp[m] = False

res = 0
for ss in s:
    if dp[ss] is True:
        res += 1

print(res)

Submission status: Accepted

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

a.sort()

m = a[-1]
dp = [True] * m
for i in range(n):
    if dp[a[i]-1]:
        t = a[i]
        j = 2
        while True:
            if t*j-1 < m:
                dp[t*j-1] = False
                j += 1
            else:
                break
a = Counter(a)
ans = 0
for i, j in a.items():
    if j == 1 and dp[i-1]:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N = int(input())
    A = list(map(int,input().split()))

    seen = set()
    dup = set()
    ng = 0
    B = []

    for a in A:
        if not a in seen:
            B.append(a)
            seen.add(a)
        else:
            dup.add(a)


    out = set()
    mx = max(B)
    for b in B:
        c = 2
        while c * b <= mx:
            out.add(c * b)
            c += 1

    for a in A:
        if a in out or a in dup: ng += 1


    print(N-ng)






if __name__ == "__main__":
  main()