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:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

print(ans)

Submission status: Accepted

Solution code:
#! env python
# -*- coding: utf-8 -*-

import os
import sys
from itertools import repeat


# atcoder.main
# Date: 2020/06/19
# Filename: main 
# Author: acto_mini

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

    A.sort()
    max = A[N - 1]
    check = list(repeat(0, max + 1))

    for i in A:
        if check[i] != 0:
            check[i] += 1
            continue
        for j in range(i, max + 1, i):
            if check[j] == 0: check[j] += 1

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

    # print(len(check))
    # print(check)
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)
#amax = 10**6

cnt = [0 for i in range(amax+1)]
for num in a:
    for i in range(1,amax//num + 1):
        tmp = num * i
        cnt[tmp] += 1

ans = 0
for num in a:
    if cnt[num]==1: ans += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
key=max(A)+1 #最大値もrange(a,key,a)で計算させるため
B=[0]*key #0~Aの最大値までのlistを作成
for a in A:
    for b in range(a,key,a):
        B[b]+=1 #aの倍数を全てにBリストで1を足す
ans=0
for a in A:
    if B[a]==1: #自身しか倍数にならなかった物
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [True for _ in range(maxp+1)]
    count =[0 for _ in range(maxp+1)]
    for a in p:
        count[a]+=1
        t =2
        while a*t <= maxp:
            if dp[a*t] == True :
                dp[a*t] = False
            t+=1
    k=0
    for d in p:
        if count[d] == 1 and dp[d] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def Not_Divisible(n,p):
    maxp = max(p)
    dp = [[True,0] for _ in range(maxp+1)]
    for a in p:
        dp[a][1]+=1
        t =2
        while a*t <= maxp:
            if dp[a*t][0] == True :
                dp[a*t][0] = False
            t+=1
    k=0
    for d in p:
        if dp[d][1] == 1 and dp[d][0] == True:
            k+=1
    return k


def main():
    input = sys.stdin.readline
    
    inp1 = input().rstrip().split()
    n = int(inp1[0])

    inp2 = input().rstrip().split()
    p = tuple(map(int,inp2))
    print(Not_Divisible(n,p))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

A.sort()
maxA = A[-1]
DP = [-1 for i in range(maxA+1)]
for a in A:
  if DP[a] != 0:
    if DP[a] == 1:
      DP[a] = 0
      continue
    for i in range(2*a, maxA+1, a):
      DP[i] = 0
    DP[a] = 1
  
    
ans = 0
for i in DP:
  if i == 1:
    ans += 1
    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
M = 10**6+1
cnt = [0 for _ in range(M)]

for i in A_list:
    if cnt[i] != 0:
        cnt[i] = 2
        continue
    for j in range(i, M, i): cnt[j] += 1

ans = 0
for k in A_list:
    if cnt[k] == 1: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(input())
list_input = list(map(int, sys.stdin.readline().split()))

list_input.sort()

# 倍数判断用のリストを作成
list_div = [0]*(max(list_input))

for i in list_input:
    # print(i)
    a = list_div[i-1]
    # list_div[i-1::i] = [1]*(len(list_div[i-1::i]))
    list_div[i-1::i] = map(lambda x: x+1, list_div[i-1::i])
    if a == 1:
        pass
    else:
        # list_div[i-1] = 0
        pass

ans = 0
for i in list_input:
    if list_div[i-1] == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

A.sort()
maxA = A[-1]
dp = [-1 for i in range(maxA+1)]
for a in A:
  if dp[a] != 0:
    if dp[a] == 1:
      dp[a] = 0
      continue
    dp[a] = 1
    for i in range(2*a, maxA+1, a):
      dp[i] = 0
ans = 0
for a in A:
  if dp[a] == 1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX = max(A)
    dp = [True] * (MAX+1)
    A.sort()
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a]:
            if cnt[a] == 1:
                ans += 1
            x = a
            while x <= MAX:
                dp[x] = False
                x += a
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
Amax = a[-1]
dp = [0]*Amax
ans = 0
for i in a:
    for j in range(i,Amax+1,i):
        dp[j-1] += 1
for i in a:
    if dp[i-1] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
key=max(A)+1
B=[0]*key
for a in A:
  for b in range(a,key,a):
    B[b]+=1
ans=0
for a in A:
  if B[a]==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ex=[0]*1000001
for a in A:ex[a]+=1
cnt=0
for i in range(1,1000001):
    if ex[i]>0:
        for j in range(i+i,1000001,i):ex[j]=0
        if ex[i]==1:
            cnt+=1
print(cnt)

Submission status: Accepted

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

maxa = max(a)
l = [0] * (maxa+1)


for i in a:

    c = 1
    while True:
        if i*c >= maxa+1:
            break
        l[i*c - 1] += 1
        c += 1







ans = 0

for i in set(a):
    if l[i-1] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
 
maxA = max(A)
ans = 0
flag = [0]*(maxA+1)
 
# print(flag)
for a in A:
    for ax in range(a,maxA+1,a):
        flag[ax] +=1
 
# print(flag)
for a in set(A):
    if flag[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

maxA = max(A)
ans = 0
flag = [0]*(maxA+1)

# print(flag)
for a in A:
    for ax in range(a,maxA+1,a):
        flag[ax] +=1

# print(flag)
for a in set(A):
    if flag[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
    if mark[n] < 2:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

print(count)

Submission status: Accepted

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

for x in s:
    t=x*2
    while t<=10**6:
        p[t]=False
        t+=x
ans=0
for x in a:
    if c[x]==1 and p[x]==True:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def undivisible(A):
    m = max(A)
    dp = [True] * (m+1)
    A.sort()
    for a in A:
        if dp[a]:
            k = a * 2
            while k <= m:
                dp[k] = False
                k += a
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a] and cnt[a] == 1:
            ans += 1
    return ans

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

Submission status: Accepted

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

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

for i in a:
    for j in range(i, max_a + 1, i):
        dp[j] += 1

out = 0
for i in a:
    if dp[i] == 1:
        out += 1

print(out)

Submission status: Accepted

Solution code:
import numpy as np
s = int(input())
l = list(map(int, input().split()))
a = np.zeros(max(l)+1,dtype=int)
n = 0
for i in l:
    a[:: i] += 1

for i in l:
    if a[i] == 1:
        n += 1
print(n)

Submission status: Accepted

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

a.sort()
dp = [True for i in range(a[-1]+1)]
count=0

for i in range(n):
    if dp[a[i]]:
        count+=1
        for j in range(1,n-i):
            if a[i]!=a[i+j]:
                break
            elif j==1:
                count-=1
            dp[a[i+j]]=False
        for j in range(a[i], a[-1]+1, a[i]):
            dp[j]=False
        # for j in range(i + 1, n):
        #     if not a[j] % a[i]:
        #         dp[j] = False
        #     if a[j] == a[i]:
        #         dp[i] = False

#print(dp.count(True))
print(count)

Submission status: Accepted

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


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

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    divisor=[False]*(1000010)
    n=int(input())
    d=defaultdict(int)
    ar=inpt()
    for i in ar:
        d[i]+=1

    ar.sort()
    for i in range(n):
        if(not divisor[ar[i]]):
            temp=2*ar[i]
            while(temp<=ar[n-1]):
                divisor[temp]=True
                temp+=ar[i]
    ct=0
    for i in ar:
        if(divisor[i]==False and d[i]==1):
            ct+=1
    print(ct)













BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

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

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

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

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


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


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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

m = np.zeros(max(a)+1, dtype=int)
cnt = 0

for i in a:
    m[::i] += 1
for i in a:
    if m[i] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
ans=0
cnt=[0]*((10**6)+1)
b=[]
for i in a:
    cnt[i]+=1
for i in range((10**6)+1):
    if cnt[i] ==1:
        b.append(i)

cnt=[0]*((10**6)+1)
for s in list(set(a)):
    for i in range(s*2,(10**6)+1,s):
        cnt[i]=1
for s in b:
    if cnt[s]==0:
        ans+=1
print(ans)

Submission status: Accepted

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

for i in a:
    for j in range(i, ln, i):
        l[j] += 1

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

print(ans)

Submission status: Accepted

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

# D - Not Divisible
n = int(input())
a = list(map(int, input().split()))
dic = dict()

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

multiples = set()
upper = 10 ** 6

for k in dic.keys():
  i = 2
  
  while True:
    if k * i <= upper:
      multiples.add(k * i)
      i += 1
    else:
      break

ans = 0

for k, v in dic.items():
  if v == 1:
    if not k in multiples:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = Counter(A)
divs = set()
for i in range(N):
  if A[i] in divs: ### Aiが含まれるならAiの倍数も含まれる
    continue
  if cnt[A[i]]>=2:
    divs.add(A[i]) ### 同じ値はdivリストに格納→最後の判定でカウントされなくなる
  for j in range(2, 10**6//A[i]+1):
    divs.add(A[i]*j) ### 倍数列挙の時点でAiを含めない
ans = 0
for i in range(N):
  if A[i] in divs:
    continue
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

non_divisible = np.ones(a[-1]+1, dtype=np.int8)
non_divisible[0] = 0
for i in range(n):
    if i != 0 and a[i] == a[i-1]:
        non_divisible[a[i]] = 0
    elif non_divisible[a[i]]:
        non_divisible[a[i]*2::a[i]] = 0

res = 0
for aa in a:
    if non_divisible[aa]:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
A.sort()
cnt = Counter(A)
divs = set()
for i in range(N):
  if A[i] in divs:
    continue
  if cnt[A[i]]>=2:
    divs.add(A[i])
  for j in range(2, 10**6//A[i]+1):
    divs.add(A[i]*j)
ans = 0
for i in range(N):
  if A[i] in divs:
    continue
  ans += 1
print(ans)

Submission status: Accepted

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

for i in a:
    for j in range(i, ln, i):
        l[j] += 1

for i in a:
    if l[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)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

if True:

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

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

    a.sort()

    dp = [True] * (a[-1] + 1)
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

            for j in range(2 * a[i], a[-1] + 1, a[i]):
                dp[j] = False

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

if True:

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

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

    a.sort()

    dp = [True] * (a[-1] + 1)
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

            for j in range(2 * a[i], a[-1] + 1, a[i]):
                dp[j] = False

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

def main():

    n = int(stdin.readline().strip())
    a = list(map(int, stdin.readline().strip().split()))

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

    a.sort()

    dp = [True] * (a[-1] + 1)
    ans = 0

    for i in range(n):

        if a[i] == a[i-1]:
            continue

        if dp[a[i]]:

            for j in range(2 * a[i], a[-1] + 1, a[i]):
                dp[j] = False

            if i == n-1 or a[i] != a[i+1]:
                ans += 1

    print(ans)

main()

Submission status: Accepted

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

a.sort()

c = [0]*a[-1]

for ai in a:
    if c[ai-1] >= 1:
        c[ai-1] += 1
        continue
    i = ai
    while i <= a[-1]:
        c[i-1] += 1
        i += ai
print(sum(c[ai-1] == 1 for ai in a))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
M = max(A)
cnt = [0 for i in range(M)]
for i in range(N):
    if cnt[A[i]-1] != 0:
        cnt[A[i]-1] = 2
    else:
        j = A[i]-1
        while j<M:
            cnt[j] += 1
            j += A[i]

ans = 0
for i in range(N):
    if cnt[A[i]-1] == 1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
## 動画見てアルゴリズムを知った
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;

lis=listA[1]
m=max(lis)
lis0=[0]*(m+1)
for i in lis:
    if lis0[i]!=2: 
        j=1
        while i*j<=m:
            lis0[i*j]+=1
            j+=1
            
count=0
for i in lis:
    if lis0[i]==1: count+=1
print(count)

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():

    def gcd(a, b):
        while b: a, b = b, a % b
        return a
    def isPrimeMR(n):
        d = n - 1
        d = d // (d & -d)
        L = [2]
        for a in L:
            t = d
            y = pow(a, t, n)
            if y == 1: continue
            while y != n - 1:
                y = (y * y) % n
                if y == 1 or t == n - 1: return 0
                t <<= 1
        return 1
    def findFactorRho(n):
        m = 1 << n.bit_length() // 8
        for c in range(1, 99):
            f = lambda x: (x * x + c) % n
            y, r, q, g = 2, 1, 1, 1
            while g == 1:
                x = y
                for i in range(r):
                    y = f(y)
                k = 0
                while k < r and g == 1:
                    ys = y
                    for i in range(min(m, r - k)):
                        y = f(y)
                        q = q * abs(x - y) % n
                    g = gcd(q, n)
                    k += m
                r <<= 1
            if g == n:
                g = 1
                while g == 1:
                    ys = f(ys)
                    g = gcd(abs(x - ys), n)
            if g < n:
                if isPrimeMR(g): return g
                elif isPrimeMR(n // g): return n // g
                return findFactorRho(g)
    def primeFactor(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k

        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret

    #[(p1,n1),(p2,n2),...]の形で返す
    def primeFactor2(n):
        i = 2
        ret = {}
        rhoFlg = 0
        while i*i <= n:
            k = 0
            while n % i == 0:
                n //= i
                k += 1
            if k: ret[i] = k
            i += 1 + i % 2
            if i == 101 and n >= 2 ** 20:
                while n > 1:
                    if isPrimeMR(n):
                        ret[n], n = 1, 1
                    else:
                        rhoFlg = 1
                        j = findFactorRho(n)
                        k = 0
                        while n % j == 0:
                            n //= j
                            k += 1
                        ret[j] = k

        if n > 1: ret[n] = 1
        if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
        return ret

    #約数列挙
    #10^6以下で約数の数が最大なのは720720の時(240個しかない！)
    def divisors(N):
        pf = primeFactor(N)
        ret = [1]
        for p in pf:
            ret_prev = ret
            ret = []
            for i in range(pf[p]+1):
                for r in ret_prev:
                    ret.append(r * (p ** i))
        return sorted(ret)
        
        
    
    mod=10**9+7
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        dd[A[i]]+=1
        
    A.sort()
    
    ans=0
    for i in range(N):
        if dd[A[i]]<2:
            L=divisors(A[i])
            flag=1
            for v in L[:-1]:
                if dd[v]:
                    flag=0
                    break
            if flag:
                ans+=1
                
    if A.count(1)==1:
        ans=1
    
                
    print(ans)
                    
        
        

                
    
    


main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(2*i,ml+1,i):
            if m[j]>0:
                m[j]=0
                #print(j)
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))

Submission status: Accepted

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

A.sort()
C = [0] * A[-1]
for Ai in A:
    if C[Ai - 1] >= 1:
        C[Ai - 1] += 1
        continue
    i = Ai
    while i <= A[-1]:
        C[i - 1] += 1
        i += Ai
print(sum([C[Ai - 1] == 1 for Ai in A]))

Submission status: Accepted

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

a.sort()
am = a[-1]

memo = [0] * (am+1)

for ai in a:
    memo[ai] = 1

p = -1

for ai in a:
    if ai == p:
        memo[ai] = 0
        continue
    for j in range(2, am // ai + 1):
        memo[ai * j] = 0
    p = ai

print(sum(memo))

Submission status: Accepted

Solution code:
N = 1000001
a = [0]* N
input()
for x in input().split():
  a[int(x)] += 1
for i in range(1, N):
  if a[i]:
    for j in range(i + i, N, i):
      a[j] = 0
print(a.count(1))

Submission status: Accepted

Solution code:
N = int(input())
(*A,) = map(int, input().split())
maxA = max(A)

C = {a: 0 for a in A}
for a in A:
    C[a] += 1

D = {a: 0 for a in A}
for a in A:
    if C[a] > 0:
        t = 2
        while a * t <= maxA:
            D[a * t] = 1
            t += 1

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

Submission status: Accepted

Solution code:
n = int(input())

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

ans = 0
d = {}


for i in range(len(a)):
    if a[i] in d.keys():
        d[a[i]] += 1
    else:
        d[a[i]] = 1
max_ = max(a)
arr = [True] * (max_+1) 
ans = 0

for i in range(1, max_+1):
    if i in d.keys() and arr[i]:
        temp = i
        # print("i: ", i)
        while (temp + i) <= (max_):
            # print(temp+i)
            arr[(temp+i)] = False

            temp += i

        if d[i] == 1:
            ans += 1
# print(arr)
print(ans)

Submission status: Accepted

Solution code:
# 一番シンプルな code
# このパターンで約数を計算で求めると TLE_※がミソ

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

num = max(l)+1
rcd = [0 for _ in range(num)]

for x in l: #※ 重複、自信を含めて約数調査
    for y in range(x, num, x): #※ 計算ではなく倍数で約数をカウントして...
            rcd[y] += 1

ans = 0
for k in l: # 各要素について...
    if rcd[k] == 1: # 約数の数が'1'の場合, 'ans'としてカウント
        ans += 1

print(ans)

Submission status: Accepted

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

num = max(l)+1
rcd = [0 for _ in range(num)]

for x in l:
    for y in range(x, num, x):
            rcd[y] += 1

ans = 0
for k in l:
    if rcd[k] == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque,Counter

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

memo = [0] * (10**6+10)
cnt = Counter(A)
for k,v in cnt.items():
    if memo[k] > 1:
        continue
    for j in range(k,10**6+1,k):
        memo[j] += v 

# print(memo[:max(A)+1])

ans = 0
for num in cnt:
    ans += (memo[num] == 1)

print(ans)

Submission status: Accepted

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

num = max(l)+1
rcd = [0 for _ in range(num)] # indexを数列Aと読み替え可能な配列として初期化

for v in l: # 重複する配列を区別するため各要素数をカウントして...
    rcd[v] += 1

unq = []
for w in range(num): # 1個の場合は重複がない要素として'unq'に集約
    if rcd[w] == 1:
        unq.append(w)
#print(unq)

rcd = [0 for _ in range(num)] # 再度初期化
#l = set(l)
for x in l: # 自身以外の約数の有無を確認 ※ここでは重複を考慮しない
    for y in range(2*x, num, x): # ※自身を約数としてカウントしない工夫！
        rcd[y] = 1 # 自身以外の約数がある場合は'1'が代入される
#print(rcd)

ans = 0
for z in unq: # 'unq'の中で...
    if rcd[z] == 0: # 自身以外に約数を持たない要素のみを...
        ans += 1 # カウント
print(ans)

Submission status: Accepted

Solution code:
import math


def main():
    amax = int(1e6+1)
    n = int(input())
    a = [int(v) for v in input().split()]
    dp = [0 for _ in range(amax)]
    dup = {}
    a.sort()
    for v in a:
        if dup.get(v) is None:
            dup[v] = 0
        else:
            dup[v] = 1
            continue
        if dp[v] == 0:
            for i in range(2, amax):
                if i * v > 1e6:
                    break
                dp[i*v] = 1
    ans = 0
    for v in a:
        if dp[v] == 0 and dup[v] == 0:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
import numpy as np
 
n, *aaa = map(int, sys.stdin.buffer.read().split())
cnt = Counter(aaa)
duplicated = {x for x, c in cnt.items() if c > 1}
aaa.sort()
 
can = np.ones(aaa[-1] + 1, np.int8)
 
ans = 0
for a in aaa:
    if can[a] == 0:
        continue
    if a not in duplicated:
        ans += 1
    can[a * 2::a] = 0
print(ans)

Submission status: Accepted

Solution code:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    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] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    N = int(input())
    A = list(map(int, input().split()))
    max_A = max(A)
    ans = [0] * (max_A + 1)
    A.sort()
    for a in A:
        tmp = 1
        b = 0
        while b <= max_A:
            b = a * tmp
            if b > max_A:
                break
            ans[b] += 1
            tmp += 1
    cnt = 0
    for a in A:
        if ans[a] == 1:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve(n,a):
    m = max(a)
    dp = [False]*(m+1)
    dup = []
    for ai in a:
        if dp[ai]:
            dup.append(ai)
        dp[ai] = True
    for ai in a:
        for i in range(2,m//ai+1):
            dp[ai*i] = False
    for ai in dup:
        dp[ai] = False
    return dp.count(True)




if __name__ == '__main__':
    n = int(input())
    a = list(map(int,input().split()))
    print(solve(n,a))

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict, Counter

INF = int(1e10)
MOD = int(1e9 + 7)
M = 10 ** 6 + 5

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * M

    for a in A:
        if cnt[a] != 0:
            cnt[a] = 2
            continue
        for i in range(a, M, a):
            cnt[i] += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# '重複する要素があると条件から逸脱する' と '他の要素が約数になると条件から逸脱する' 
# 上記2つの問題を 前半と後半に分けて処理する、

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

# 重複問題
num = max(l)+1
rcd = [0 for _ in range(num)] # indexを数列Aと読み替え可能な配列として初期化

for v in l: # 重複する配列を区別するため各要素数をカウントして...
    rcd[v] += 1

unq = []
for w in range(num): # 重複がない要素のみ'unq'に集約
    if rcd[w] == 1: # 1個の場合のみが該当
        unq.append(w)
#print(unq)

# 約数問題
rcd = [0 for _ in range(num)] # 再度初期化
l = set(l) # ここでは重複を考慮しないため集合化
for x in l: # 自身以外の約数の有無を確認するためのループ
    for y in range(2*x, num, x): # ※自身を約数としてカウントしない工夫！
        rcd[y] = 1 # 自身以外の約数がある場合は'1'が代入される
#print(rcd)

# まとめ
ans = 0
for z in unq: # 'unq'の中で...
    if rcd[z] == 0: # 自身以外に約数を持たない要素のみを...
        ans += 1 # カウント
print(ans)