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:
import sys
sys.setrecursionlimit(4100000)

import math

import logging

logging.basicConfig(level=logging.DEBUG)

logger = logging.getLogger(__name__)

import numpy as np


def resolve():
    # S = [x for x in sys.stdin.readline().split()][0]  # 文字列 一つ
    N = [int(x) for x in sys.stdin.readline().split()][0]  # int 一つ
    # N, D = [int(x) for x in sys.stdin.readline().split()]  # 複数int
    a_list = [int(x) for x in sys.stdin.readline().split()]  # 複数int

    # grid = [list(sys.stdin.readline().split()[0]) for _ in range(N)]  # 文字列grid
    # v_list = [int(sys.stdin.readline().split()[0]) for _ in range(N)]
    # grid = [[int(x) for x in sys.stdin.readline().split()]
    #         for _ in range(N)]  # int grid

    logger.debug('{}'.format([]))

    MAX = 10**6
    count_list = np.array([0 for _ in range(MAX + 1)])
    for a in a_list:
        count_list[a] += 1

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

    print(count_list.sum())


if __name__ == "__main__":
    resolve()

# AtCoder Unit Test で自動生成できる, 最後のunittest.main は消す
# python -m unittest template/template.py で実行できる
# pypy3 -m unittest template/template.py で実行できる

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
24 11 8 3 16"""
        output = """3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
5 5 5 5"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """10
33 18 45 28 8 19 89 86 2 4"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """2
1000000 1000000"""
        output = """0"""
        self.assertIO(input, output)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.sort()
max=l[n-1]
dp=[0]*(max+1)
for i in l:
  if dp[i]!=0:
    dp[i]+=1
    continue
  for j in range(i,max+1,i):
    dp[j]+=1
sum=0
for i in l:
  if dp[i]==1:
    sum+=1
print(sum)

Submission status: Accepted

Solution code:
# Problem D - Not Divisible
# input
N = int(input())
a_nums = list(map(int, input().split()))

# initialization
max_a = max(a_nums)
fact_list = [0] * (max_a + 1)
ans = 0

# count
for a in a_nums:
    tmp = max_a // a
    for i in range(tmp):
        fact_list[a*(i+1)] += 1

# count 2
for a in a_nums:
    if fact_list[a]==1:
        ans += 1

# output
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = sorted(list(map(int, input().split())))
    C = Counter(A)
    dp = [False] * 1100000
    ans = 0
    for a, cnt in C.items():
        if dp[a]:
            continue
        for i in range(2*a, 1100000, a):
            dp[i] = True
        if cnt == 1:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
from collections import Counter as co
l=co(list(map(int,input().split())))
ans=len(l)
ng=set()
for k in l:
    if l[k]>=2:ng.add(k)
    for i in range(2*k,10**6+1,k):
        if i in l:
            ng.add(i)
print(ans-len(ng))

Submission status: Accepted

Solution code:
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


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


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]

n = int(input())
a = readints()
tmp = [False]*(10**6+100)
a_so = sorted(a)
# print(a_so)
cnt = 0
for i in range(len(a_so)):
    if tmp[a_so[i]]:
        continue
    if (i+1 >= len(a_so)) or (a_so[i] != a_so[i+1]):
        cnt += 1
    for j in range(1, len(tmp)):
        if a_so[i]*j >= len(tmp):
            break
        tmp[a_so[i]*j] = True
print(cnt)

Submission status: Accepted

Solution code:
def find(A):
    nums=[0]*(10**6+1)
    bad = [0]*(10**6+1)
    count = 0
    for x in A:
        nums[x] += 1
    for i in range(1,10**6+1):
        if nums[i]==0:
            continue
        for j in range(2,10**6+1):
            temp = i*j
            if temp<10**6+1:
                bad[temp] = 1
            else:
                break
    
    ans = 0
    for x in A:
        if bad[x] == 0 and nums[x] == 1:
            ans +=1
    return ans

input()
A = list(map(int,input().strip().split()))
print(find(A))

Submission status: Accepted

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

from collections import Counter
C = Counter(A)
#print(C)

M = max(A)
X = [0]*(M+1)
for i in A:
    j = i*2
    while j <= M:
        X[j] = 1
        j += i
#print(X)

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

Submission status: Accepted

Solution code:
import numpy as np

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

arr = np.zeros(MAX + 1, np.int64)
for e in a:
    arr[e] += 1

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

    arr[i] = arr[i] == 1

ans = arr.sum()
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
f=[1]*(10**6+10)
from collections import Counter
c=Counter(a)
ans=0
for ai in a:
  if c[ai]==1 and f[ai]==1:ans+=1
  if f[ai]==1:
    for i in range(ai,10**6+10,ai):
      f[i]=0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
N = len(A)
amax = A[-1]
P = [0 for _ in range(amax+1)]
for i in range(N):
    P[A[i]] = 1
for i in range(N):
    a = A[i]
    for j in range(a*2,amax+1,a):
        P[j] = 0
C = {}
for i in range(N):
    a = A[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
for i in range(N):
    a = A[i]
    if P[a]==1 and C[a]>1:
        P[a] = 0
print(sum(P))

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
lis=list(set(lis))
m=10**6+1
dp=[0 for i in range(m)]
#print(dp)
for i in range(len(lis)):
    x=lis[i]
    #print(x)
    for j in range(2,((m-1)//x)+1):
        dp[x*j]=1
        #print(x*j)
#print(5*j)
#print(dp)
ans=0
#print(dp[10**6])
for y in lis:
    if c[y]<=1:
        ans+=1-dp[y]
print(ans)
#print(dp)
#print(dp[2*(10**5)])

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))
A.sort()
B = [0] * (A[-1] + 1)
C = Counter(A)

res = 0
for a in A:
    if B[a] == 0 and C[a] == 1:
        res += 1
    for i in range(a, A[-1] + 1, a):
        B[i] += 1

print(res)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A.sort()
check = [0]*(10**6+1)
for a in A:
    if check[a] != 0:
        check[a] += 1
        continue
    for i in range(10**6+1)[a::a]:
        check[i] += 1
cnt = 0
for a in A:
    if check[a] == 1: cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def main():

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

    from collections import Counter
    C = Counter(A)
    #print(C)

    M = max(A)

    X = [0]*(M+1)
    for i in A:
        j = i*2
        while j <= M:
            X[j] = 1
            j += i
    #print(X)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
A.sort()
C = Counter(A)
MAX = 1010101
B = [0]*MAX

ans = 0
for a, cnt in C.items():
    if B[a]:
        continue
    for i in range(2*a, MAX, a):
        B[i] = 1
    if cnt == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
s = set(A)
flag = [False]*(10**6+100)

for i in range(10**6+100):
    if i in s:
        flag[i] = True
        
for i in range(10**6+100):
    if i in s:
        for j in range(2*i, 10**6+100, i):
            flag[j] = False

cnt = Counter(A)
ans = 0

for i in range(10**6+100):
    if flag[i] and cnt[i]==1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
m = A[-1]+1
dp = [0]*(m*2)
ans = 0

for a in A:
    for i in range(0, m//a+1):
        dp[a*i] += 1
for a in A:
    if dp[a] == 1:
        ans += 1

print(ans)

Submission status: Accepted

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

dp = [0]*(10**6 + 1)
ans = 0

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

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


print(ans)

Submission status: Accepted

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

max_number = max(A) + 1
ng = [False] * max_number
counter = 0
prev = 0
for ai in A:
    if ai == prev:
        counter -= 1
        prev = 0
    if not ng[ai]:
        counter += 1
        prev = ai
    for i in range(ai, max_number, ai):
        ng[i] = True
print(counter)

Submission status: Accepted

Solution code:
import sys

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_max = a[-1]
    sive = [True] * (a_max + 1)

    def sived(x):
        for non_ans in range(x, a_max+1, x):
            sive[non_ans] = False
    ans = 0
    for i in range(len(a)-1):
        if sive[a[i]]:
            sived(a[i])
            if a[i] != a[i+1]:
                ans += 1
    if sive[a_max]:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def ii(): return int(sys.stdin.readline())
def li(): return list(map(int, sys.stdin.readline().split()))

if __name__ == "__main__":
    n = ii()
    a = li()
    a = sorted(a)
    a_max = a[-1]
    sive = [True] * (a_max + 1)

    def sived(x):
        for non_ans in range(x, a_max+1, x):
            sive[non_ans] = False
    ans = 0
    for i in range(len(a)-1):
        if sive[a[i]]:
            sived(a[i])
            if a[i] != a[i+1]:
                ans += 1
    if sive[a_max]:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import math

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

    A.sort(reverse=True)

    Amax=max(A)

    dp=[0]*Amax

    tmp=-1
    res=0
    for i in range(len(A)):
        a=A.pop()
        if a==tmp:
            continue
        if dp[a-1]==0:
            if len(A)>0:
                if A[len(A)-1]!=a:
                    res+=1
            else:
                res+=1
            m=2
            while (a*m)<=Amax:
                dp[a*m-1]=1
                m+=1
        tmp=a

    print(res)
if __name__=="__main__":
    main()

Submission status: Accepted

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

check = [0]*(a_max+1)

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

print(check.count(1))

Submission status: Accepted

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

M=max(A)
check=[0]*(M+1)
#A.sort()
for i in range(N):
    a=A[i]
    if check[a]>1:
        continue
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)

Submission status: Accepted

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

M=max(A)
check=[0]*(M+1)
for i in range(N):
    a=A[i]
    while a<=M:
        check[a]+=1
        a+=A[i]
ans=0
for i in range(N):
    if check[A[i]]==1:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
M = 10**6 + 1
L = [0]*M
for a in A:
    L[a] += 1
    if L[a] == 1:
        # k>=2として k*aは全て不適
        for i in range(2*a, M, a):
            L[i] += 2
# flagの数が答え
print(L.count(1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()
A = sorted(A)

kasanari = []
count = [0]*(10**6+1)
for a in A:
    count[a] += 1
    if (count[a] > 1):
        kasanari.append(a)
ref = list(set(A) - set(kasanari))

erasut = np.ones(A[-1]+1, dtype=np.int64)
for a in set(A):
    if(a*2 < A[-1]+1):
        erasut[a*2::a] = 0
erasut = erasut[ref]
# kasanari = set(kasanari)
print(sum(erasut))
# print(int(sum()) - len(set(kasanari)))

Submission status: Accepted

Solution code:
import sys

from collections import defaultdict

I=sys.stdin.readline

n=int(I())
arr=sorted(list(map(int,I().split())))
d=defaultdict(int)

for i in arr:
	d[i]+=1

ans=0
visited=[0]*(arr[-1]+1)
for i in arr:
	if d[i]==1 and visited[i]==0:
		ans+=1

	for j in range(i,arr[-1]+1,i):
		visited[j]=1

print(ans)

Submission status: Accepted

Solution code:
import sys, io, os, re
import bisect
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby

n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n): return [0] * n
def array2(n, m): return [[0] * m for x in range(n)]
def array3(n, m, l): return [[[0] * l for y in xrange(m)] for x in xrange(n)]

N = n1()
A = nn()

A.sort()
#print(A)

max_num = A[-1]
t = array1(max_num+1)
ans = 0

for i, n in enumerate(A):
    if t[n] == 0:
        if i < len(A) - 1 and A[i] == A[i+1]:
            pass
        else:
            ans += 1

    j = n
    while j <= max_num:
        t[j] = 1
        #print(t)
        j += n
    
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    M = 10 ** 6
    _ = int(input())
    A = list(map(int,input().split()))
    erato = [True] * (M+10)
    m = sorted(Counter(A).items())
    ans = 0
    for t in m:
        if t[1] == 1 and erato[t[0]]:
            ans += 1
        for i in range(t[0],M+1,t[0]):
            erato[i] = False
            
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

sortList = sorted(AList)
Amax = max(sortList)
dp = [0] * (Amax+1)

for n in sortList:
  dp[n] += 1
  if dp[n] == 1:
    for j in range(n*2, Amax+1, n):
      dp[j] += 2
print(dp.count(1))

Submission status: Accepted

Solution code:
def abc170_d():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    Amax = A[-1]
    check = [False] * (Amax + 1)
    ans = 0
    for i in range(N):
        if check[A[i]]: continue
        if not(i < N-1 and A[i] == A[i+1]): ans += 1
        k = 1
        while k*A[i] <= Amax:
            check[k*A[i]] = True
            k += 1
    print(ans)

abc170_d()

Submission status: Accepted

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

# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")

readline = sys.stdin.readline

# did it after reading editorial
# nice one
def proc():
    _ = int(readline().rstrip())
    a = list(map(int, readline().rstrip().split()))

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

#for _ in range(int(readline().rstrip())):
print(proc())

Submission status: Accepted

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


mx = max(A)
x = [0] * (mx + 1) # len(x)
for i in A:
    x[i] += 1
for i in range(1, mx + 1):
    if x[i] != 0:
        for j in range(2 * i, mx + 1, i):
            x[j] = 0
    if x[i] > 1:
        x[i] = 0
print(sum(x))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
MAX = max(A)+1#A[-1]+1
num_tmp = [0]*MAX

for a in A:
    num_tmp[a] += 1
    if num_tmp[a] == 1:
        for i in range(2*a,MAX,a):
            num_tmp[i] = 2

print(num_tmp.count(1))

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter

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

max=list[-1]
dp=[0]*(max+1)
dp=np.array(dp,int)

for num in list:
    dp[num]=1

for num in list:
    if dp[num]==1:
        dp[2*num::num]=0

count=Counter(list)

for num,cnt in count.items():
    if cnt>1:
        dp[num]=0

print(dp.sum())

Submission status: Accepted

Solution code:


def submit():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    max_a = max(a)
    sieve = [0] * (max_a + 1)

    for e in a:
        sieve[e] += 1

    if sieve[1] == 1:
        print(1) # 他は全て1で割り切れてしまう
        return
    
    if sieve[1] > 1:
        print(0) # 全て割り切れる
        return

    # エラトステネスの篩風に計算する
    for e in range(1, max_a + 1):
        if sieve[e] == 0:
            continue

        coef = 2
        while e * coef <= max_a:
            sieve[e * coef] = 0
            coef += 1
        
    # 数が1の要素を数える
    ans = 0
    for e in sieve:
        if e == 1:
            ans += 1

    print(ans)


submit()

Submission status: Accepted

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

a.sort()

M = 1000005
cnt = [0] * M

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
amax = a[-1]
isok = [True]*(amax+1)
ans = 0
if n == 1:
    print(1)
    exit()
for i in range(n):
    x = a[i]
    if isok[x]:
        if i == 0 and a[i] != a[i+1]:
            ans += 1
        elif i == n-1 and a[i] != a[i-1]:
            ans += 1
        elif a[i] != a[i+1] and a[i] != a[i-1]:
            ans += 1
        orix = x
        while x<=amax:
            isok[x]=False
            x+=orix
print(ans)

Submission status: Accepted

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

INF = 10**6

A.sort()
check = [False] + [True]*(INF)

setA = list(set(A))
length = len(setA)
for i in range(length):
    x = setA[i]
    for j in range(2, int(INF/x)+1):
        check[x*j] = False

prev = 0
count = 0
flag = False #重複チェック
for i in range(N):
    x = A[i]
    if check[x]:
        if x != prev:
            count += 1
            flag = True
        elif flag:
            count -= 1
            flag = False
        prev = x
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()

	A.sort()
	zyuufuku = {}
	for i,val in enumerate(A):
		if i == 0:
			continue
		if val == A[i-1]:
			if val in zyuufuku:
				pass
			else:
				zyuufuku[val] = 1

	refd = [0 for i in range(1000000 + 1)]
	for i,val in enumerate(A):
		if val in zyuufuku:
			if zyuufuku[val] > 2:
				continue
			else:
				zyuufuku[val] += 1
		for j in range(val,1000000 + 1,val):
			refd[j] += 1

	ans = 0
	for i,val in enumerate(A):
		if val in zyuufuku:
			continue
		if refd[val] < 2:
			ans += 1

	print(ans)

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
M = max(a)+1
t=[True]*M
a.sort()
s=set(a)
pre = 0
for i in a:
    if t[i] == 0:
        continue
    if pre == i:
        t[i] = False
    for j in range(2*i,M,i):
        t[j] = False
    pre = i
ans = 0
for k in a:
    if t[k] == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def func(n, a):
    mx = max(a)
    x = [0] * (mx + 1) # len(x)
    for i in a:
        x[i] += 1
    for i in range(1, mx + 1):
        if x[i] != 0:
            for j in range(2 * i, mx + 1, i):
                x[j] = 0
        if x[i] > 1:
            x[i] = 0
    print(sum(x)) # 31401

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_3
# CreatedDate:  2020-06-19 15:09:52 +0900
# LastModified: 2020-06-19 15:27:30 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    _ = int(input())
    a_s = list(map(int, input().split()))
    m = max(a_s)+1
    cnt = [0 for _ in range(m)]

    for a in a_s:
        if cnt[a] != 0:
            cnt[a] = 2
            continue
        for n in range(a, m, a):
            cnt[n] += 1

    print(sum(cnt[a] for a in a_s if cnt[a]==1))


if __name__ == "__main__":
    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())
As = list(map(int, input().split()))
M = max(As)+1
cnt = [0 for _ in range(M)]

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

ans = 0
for A in As:
  if cnt[A] == 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
A=sorted((map(int,input().split())))
maxA=max(A)
L=[0]*(maxA+1)
AD=defaultdict(int)
for a in A:
	L[a]=1
	AD[a]+=1
for a in A:
	if AD[a]>=2:
		L[a]=0
	for i in range(2*a,maxA+1,a):
		L[i]=0
print(sum(L))

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
M = max(A_list)+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 glob
import os

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

        N = int(self.input_data())
        A = list(map(int, self.input_data().split()))
        A_sorted = sorted(A)

        check_list = [-1]*1000001

        for a in A:
            for i in range(a, 1000001, a):
                if i == a:
                    if check_list[i] == -1:
                        check_list[i] = 0
                    elif check_list[i] == 0:
                        check_list[i] = 1
                    else:
                        break
                    continue

                check_list[i] = 1


        result = 0
        for i in A_sorted:
            if check_list[i] < 1:
                result += 1

        print(str(result))

solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Accepted

Solution code:

n=int(input())
a=sorted(map(int,input().split()))
m=max(a)+1
t=[0]*m
cnt=0
for i in a:
    if t[i]==0:
        cnt+=1
    elif t[i]==1:
        cnt-=1
    if t[i]<2:
        t[i]+=1
        for j in range(i*2,m,i):
            t[j]=2
print(cnt)

Submission status: Accepted

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

m = max(a)+1
dp = [1]*m
for i in a:
  if dp[i-1] == 1:
    dp[i-1] = 2 # 整数列にも存在せず、整数列の値の倍数でもない値はすべて"1"のまま
    for j in range(i*2, m, i):
      dp[j-1] = 0
  elif dp[i-1] == 2: # 数列内に複数同じ値がある場合はそれもNGになる
    dp[i-1] = 0

print(sum([1 for i in a if dp[i-1]])) # 判定の対象が"2"であればOK

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
d = {}
for x in arr:
  d[x] = d.get(x,0)+1

mxN = 10**6 + 1
rp = [True]*mxN

if 1 in d:
  if d[1] > 1:
    print(0)
    exit()
  else:
    print(1)
    exit()
for i in range(2,len(rp)):
  if i not in d or not rp[i]:continue
  for j in range(i+i,mxN,i):
    if j in d: rp[j] = False

#reason for tle



for k,v in d.items():
  if v > 1:rp[k] = False

ans = sum([(1 if rp[x] else 0) for x in arr])
print(ans)

Submission status: Accepted

Solution code:
# エラトステネスの篩を使う！O(nloglogn)
N = int(input())
A = list(map(int,input().split()))

listA = [0] * (10**6+10)
ans = 0
for i in A:
    if listA[i] != 0:
            listA[i] = 2
            continue
    for j in range(i,10**6+10,i):
        listA[j] += 1

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

print(ans)

Submission status: Accepted

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

n=int(input())
L=list(map(int,input().split()))
L.sort()
hb = L[-1]
dp = [-1 for i in range(hb+1)] 
for i in L:
    if dp[i]!=0:
        if dp[i]==1:
            dp[i]=0
            continue
        dp[i]=1
        for j in range(2*i,hb+1,i):
            dp[j]=0
ans=0
for i in L:
    if dp[i]==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ints = list(map(int, input().split()))
m = max(ints)
x = [0] * m
cnt = 0

for i in ints:
    if x[i-1] >= 2:
        continue
    for j in range(m // i):

        x[i * (j + 1) - 1] += 1

for i in ints:
    if x[i - 1] == 1:
        cnt += 1

print(cnt)

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)

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1):
        tmp = num * i
        if dp[tmp]: dp[tmp] = 0

# カウンター
cnt = col.Counter(a)

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for key,val in cnt.items():
    if dp[key] and val==1: ans += 1

print(ans)