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:
n = int(input())
A = sorted(list(map(int, input().split())))
from collections import Counter
c = Counter(A)

MAX = 10 ** 6 + 1000
dp = [True] * MAX

for k, v in c.items():
    if dp[k] == False: continue
    if v > 1: dp[k] = False
    for x in range(k + k, MAX, k):
        dp[x] = False

res = 0
for x in range(n):
    if dp[A[x]]: res += 1
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
 
m = [0]*(max(a)+1)
lm = len(m)
cnt = 0
 
for i in a:
    j = 1
    while i*j < lm:
        m[i*j] += 1
        j += 1
for i in a:
    if m[i] == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

def make_divisors(n):
    result = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            result.append(i)
            if i != n // i:
                result.append(n//i)
    result.sort()
    return result

def main():
    N = i_input()
    A = i_list()
    ans = 0
    max_a = max(A)
    p = [0] * (max_a + 1)
    for i in A:
        for j in range(i , max_a + 1, i):
            p[j] += 1
    for i in A:
        if p[i] < 2:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n,*a = map(int,open(0).read().split())
s = set(a)
c = Counter(a)
m = max(s)
l = [True]*(m+1)
ans = 0
for i in range(1,m+1):
  if i in s and l[i]:
    if c[i] == 1:
      ans += 1
    for j in range(1,m//i+1):
      l[i*j] = False
print(ans)

Submission status: Accepted

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

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

seen = set()
for a in A:
    for mul_a in range(a, maxA+1, a):
        if a not in seen and mul_a == a: 
            continue
        memo[mul_a] += 1
    seen.add(a)

ans = 0
seen = set()
for a in A:
    if memo[a] == 0 and a not in seen:
        seen.add(a)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
M = max(A)
X = [1]*(M+1)
for a in A:
  X[a]-=1
  for i in range(a*2,M+1,a):
    X[i]=-2 

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
B = (10**6+1)*[0]

for a in A:
  B[a]+=1
  if B[a]==1:
    for n in range(2*a,10**6+1,a):
      B[n]+=2

print(B.count(1))

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
li_a = list(map(int, input().split()))
m = max(li_a)
e = np.zeros(m)
dup = []
for a in li_a:
    if(e[a-1]==1):
        dup.append(a-1)
        continue
    e[a-1] = 1

for i in dup:
    e[i] = 0

for a in set(li_a):
    origin = a
    while a <= m:
        if a==origin:
            a += origin
            continue
        e[a-1]=0
        a += origin
print(int(sum(e)))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
from collections import Counter
c = Counter(a)
vals = [True]*(max(a)+1)
ans = 0
m = max(a)+1
for i in range(1, m):
    if i not in c:
        continue
    if c[i]>=2:
        vals[i] = False
    for j in range(2*i, m, i):
        vals[j] = False
ans = 0
for i in range(1, max(a)+1):
  if vals[i] and i in c:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
M = 10**6 + 1
 
cnt = [0] * M
 
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
 
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
As.sort()
M = 1000001
array = [0]*M
for a in As:
    if array[a] != 0:
        array[a] = 2
        continue
    for i in range(a,M,a):
        array[i] += 1

ans = 0
for a in As:
    if array[a] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math
 
def INT(): return int(input())
def MAPINT(): return map(int, input().split())
def LMAPINT(): return list(map(int, input().split()))
def STR(): return input()
def MAPSTR(): return map(str, input().split())
def LMAPSTR(): return list(map(str, input().split()))
 
f_inf = float('inf')
 
n = INT()
a = sorted(LMAPINT())

length = (max(a) + 1)

ans = [0] * length
for x in a:
  # 重複
  if ans[x] != 0:
    ans[x] = 2
    continue
  for j in range(x, length, x):
    ans[j] += 1
 
count = 0
for x in a:
  if ans[x] == 1:
    count += 1
print(count)

Submission status: Accepted

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

  ans = [0] * (max(a) + 1)
  length = max(a) + 1
  for x in a:
    if ans[x] == 0:
      for j in range(x, length, x):
        ans[j] += 1
    else:
      ans[x] += 1

  print(len(list(filter(lambda x: ans[x] == 1, a))))

  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
xs = [0] * (max(a) + 1)
 
for v in a:
    if xs[v] == 0:
        for j in range(v, len(xs), v):
            xs[j] += 1
    else:
        xs[v] += 1
print(len(list(filter(lambda v: xs[v] == 1, a))))

Submission status: Accepted

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

M = 10**6 + 1

cnt = [0] * M

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

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = sorted(A)
L = [0] * (A[-1]+1)
for a in A:
    L[a] = 1

for p in A:
    if not L[p]: continue 
    L[p] += 1
    n = 2
    while p*n <= A[-1]:
        L[p*n] = 0
        n += 1

ans = L.count(2)
print(ans)

Submission status: Accepted

Solution code:
import copy

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    A_max = A[N-1]

    div_count = [0] * (A_max + 1)

    for a in A:
        for n in range(a, A_max+1, a):
            div_count[n] += 1

    exists = [False] * (A_max + 1)
    for a in A:
        exists[a] = True

    result = 0
    for i, d in enumerate(div_count):
        if d == 1 and exists[i]:
            result += 1

    print(result)

main()

Submission status: Accepted

Solution code:
import numpy as np
import random

rand = False
if rand:
    N = 10 ** 5
    A = random.choices(range(1, 10**6), k=N)
else:
    N = int(input())
    A = list(map(int, input().split()))

A.sort()
MX = max(A)
ret = np.zeros(MX+1, dtype=np.bool)
A = np.array(A, dtype=np.int32)
ret[ A ] = True

for i in range(N-1):
    m = A[i] * 2
    if A[i] == A[i+1]: m = A[i]
    ret[ np.arange(m, MX+1, A[i]) ] = False

print(np.sum(ret))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    A.sort()
    D = [True] * (10**6 + 1)
    ans = 0

    for i, a in enumerate(A):
        if not D[a]:
            continue
        if (i < n-1 and a != A[i+1]) or i == n-1:
            ans += 1

        j = a
        while (j < 10**6 + 1):
            D[j] = False
            j += a

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=sorted(LI())

    MAX=10**6
    divible=[False]*(MAX+1)

    ans = 0
    for i,a in enumerate(A):
        if(i+1<N and A[i+1]==a or divible[a]):
            pass
        else:
            ans += 1
            
        b = a
        if(not divible[a]):#エラトステネスの篩と同じ計算量解析.
            while(b<=MAX): 
                divible[b] = True
                b += a
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
M = 10**6+5
cnt = [0]*M
for x in A:
    if cnt[x] != 0:
        cnt[x] = 2
        continue
    for i in range(x,M,x):
        cnt[i] += 1
ans = 0
for i in A:
    if cnt[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import math
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
ans = 0
numset = set(a)
maxval = 10**6
dp = [0]*(maxval+1)
for i in range(n):
    if dp[a[i]] >= 1: continue
    if dp[a[i]] == 0 and (i == n-1 or a[i] != a[i+1]):
        ans += 1
    j = a[i]
    while j <= maxval:
        dp[j] += 1
        j += a[i]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import math
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
a.sort()
ans = 0
maxval = a[-1]
seen = set()
for i in range(n):
    if a[i] not in seen and (i == n-1 or a[i] != a[i+1]):
        ans += 1
    j = a[i]
    while j <= maxval:
        seen.add(j)
        j += a[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
MAX = 10**6
table = [0]*(MAX+1)
for x in map(int,input().split()):
    table[x] += 1
for i in range(MAX+1):
    if table[i]:
        for j in range(2*i if table[i] == 1 else i, MAX+1, i):
            table[j] = 0
print(sum(table))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる

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

z=[0]*(10**6+1)
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

ans=0
for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,0]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]
    m=len(w)

    def s(d,y):
        global m
        global i
        global f
        if d==m-1:
            p=y
            if p!=i and z[p]>=1:
                f=1
        else:
            for j in range(w[d+1][1]+1):
                s(d+1,y*(w[d+1][0]**j))

    s(0,1)
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,1]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)

    def s(d,y):
        global m
        global i
        global f
        if d==m-1:
            p=y
            if p!=i and z[p]>=1:
                f=1
        else:
            for j in range(w[d+1][1]+1):
                s(d+1,y*(w[d+1][0]**j))

    s(0,1)
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[[1,1]]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)

    def s(d,h,y):
        global m
        global i
        global f
        if d==m-1:
            p=y*(w[d][0]**h)
            if p!=i and z[p]>=1:
                f=1
        else:
            y*=w[d][0]**h
            for j in range(w[d+1][1]+1):
                s(d+1,j,y)

    s(0,1,1)
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline #文字列入力はするな！！
sys.setrecursionlimit(10**9) #再帰の上限をあげる
n=int(input())
a=list(map(int,input().split()))
z=[0]*(10**6+1)
ans=0
for i in a:
    z[i]+=1

x=[-1]*(10**6+1) #2以上の自然数に対して最小の素因数を表す
x[0]=0
x[1]=1
i=2
prime=[]
while i<=10**6:
    if x[i]==-1:
        x[i]=i
        prime.append(i)
    for j in prime:
        if i*j>10**6 or j>x[i]:break
        x[j*i]=j
    i+=1

for i in a:
    f=0
    u=i
    if z[u]>=2:
        f=1
    w=[]
    p=x[u]
    cnt=1
    while u>1:
        if p==x[u//p]:
            cnt+=1
            u=u//p
        else:
            w.append([p,cnt])
            cnt=1
            u=u//p
            p=x[u]

    m=len(w)
    y=1
    def s(d,h,y):
        global m
        global i
        global f
        if d==m-1:
            p=y*(w[d][0]**h)
            if p!=i and z[p]>=1:
                f=1
        else:
            y*=w[d][0]**h
            for j in range(w[d+1][1]+1):
                s(d+1,j,y)
    if m==0:
        if z[1]>=2:
            f=1
    else:
        for j in range(w[0][1]+1):
            s(0,j,1)
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 12 00:21:05 2020

@author: liang
"""

N = int(input())
A = [int(x) for x in input().split()]

A.sort()
A += [-1]
dp = [0] + [True]*10**6
def Solve():
    if A[0] == 1:
        if len(A) >= 2 and A[1] == 1:
            return 0
        else:
            return 1
    k = 0
    for i in range(1,10**6+1):
        if i == A[k]:
            #print("A",i)
            #kの処理
            tmp = A[k]
            cnt = 0
            while k <= N-1 and A[k] == tmp:
                #print("B",k,tmp)
                cnt += 1
                if cnt == 2:
                    dp[tmp] = False
                k += 1
            #倍数の消去
            for j in range(2*i,10**6+1,i):
                #print("C")
                dp[j] = False
    ans = 0
    for a in A[:-1]:
        if dp[a]:
            ans += 1
    return ans

ans = Solve()
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
from numba import njit
def main():

    @njit
    def solve(a):
        count = np.zeros(10 ** 6 + 1, np.int32)
        for ae in a:
            if count[ae] <= 1:
                count[::ae] += 1
        r = 0
        for ae in a:
            r += count[ae] == 1
        return r

    a = np.array(read().split(), np.int32)[1:]
    print(solve(a))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
def main():
    a = np.array(read().split(), np.int32)[1:]
    count = np.zeros(10**6+1, np.int32)
    for ae in a:
        if count[ae] <= 1:
            count[::ae] += 1
    r = 0
    for ae in a:
        r += count[ae] == 1
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np
from collections import Counter
def main():
    n, *a = map(int, read().split())

    if 1 in a:
        count1 = a.count(1)
        if count1 == 1:
            print(1)
            sys.exit()
        else:
            print(0)
            sys.exit()
    a = np.array(a)
    maxa = a.max()
    seq = np.zeros(maxa + 1, np.int32)
    u, cnt = np.unique(a, return_counts=True)
    for ue, cnte in zip(u, cnt):
        if cnte == 1:
            seq[ue] = 1
    for ae in a:
        t = ae * 2
        while t <= maxa:
            seq[t] = 0
            t += ae
    r = seq.sum()
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
nums = list(map(int,input().split()))
nums.sort()
ans = 0
cnt = {}
flag = [0]*1000005
for i in nums:
  cnt[i] = cnt.get(i,0) + 1

for i in nums:
  if flag[i] == 0 and cnt[i] == 1:
    ans += 1
  if flag[i] == 1:
    continue
  for j in range(i,1000001,i):
    flag[j] = 1

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#import numpy as np
from collections import Counter
def main():
    n, *a = map(int, read().split())
    if 1 in a:
        count1 = a.count(1)
        if count1 == 1:
            print(1)
            sys.exit()
        else:
            print(0)
            sys.exit()
    maxa = max(a)
    seq = [0] * (maxa + 1)
    ac = Counter(a)
    for ae in ac.items():
        if ae[1] == 1:
            seq[ae[0]] = 1
    for ae in a:
        t = ae * 2
        while t <= maxa:
            seq[t] = 0
            t += ae
    r = sum(seq)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX

for x in a:
    cnt[x] += 1

ans = 0

for i in range(1,MAX):
    if cnt[i] > 0:
        for j in range(i*2, MAX, i):
            ok[j] = False
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int,input().split())))
lim = max(A)
B = [0] * (lim+1)
for i in range(N):
    B[A[i]] += 1
ans = N
for i in range(1,lim+1):
    if B[i] == 0:
        continue
    if B[i] >= 2:
        ans -= B[i]
        B[i] = 0
    for j in range(i*2,lim+1,i):
        ans -= B[j]
        B[j] = 0

print(ans)

Submission status: Accepted

Solution code:
import math , sys

N = int( input() )
A = list( map( int, input().split() ))
A.sort()
Cs = [0 for _ in range(10**6+1)]
M = A[-1]
#print(A)
i=0
M = max(A)
for i in range(N):
    e = A[i]
    if Cs[e]==1:
        Cs[e]=2
    elif Cs[e]==0:
        Cs[e]=1

for i in range(len(Cs)):
    Cs[i] = Cs[i]%2

for e in A:
    i = 2
    while e*i <= M:
        Cs[e*i] = 0
        i+=1
ans = sum(Cs)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n = int(input())
    A = list(map(int,input().split()))
    A.sort()
    max_A = max(A)
    dp = [True] * (max_A+1) # iより小さいiの約数がAに存在しない
    multi = [0] * (max_A+1) #重複個数
    for a in A:
        multi[a] += 1
        if multi[a] > 1: continue
        x = a
        while x + a <= max_A:
            x += a
            dp[x] = False
    ans = 0
    for a in A:
        if dp[a] and multi[a]==1:
            ans += 1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX
for x in a:
    cnt[x] += 1
ans = 0
for i in range(1, MAX):
    if cnt[i] > 0:
        for j in range(i * 2, MAX, i):
            ok[j] = False       
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 5
cnt = [0] * MAX
ok = [True] * MAX
for x in a:
    cnt[x] += 1
ans = 0
for i in range(1, MAX):
    if cnt[i] > 0:
        for j in range(i * 2, MAX, i):
            if cnt[j] > 0:
                ok[j] = False       
        if ok[i] and cnt[i] == 1:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = Counter(A)
A = set(A)
B = [True] * (10 ** 6 + 1)
for a in A:
    for i in range(2 * a,10**6 + 1 ,a):
        B[i] = False
cnt = 0
for a in A:
    if (B[a] == True) and (C[a] == 1):
        cnt += 1
print(cnt)

Submission status: Accepted

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

F=[0]*(10**6+11)
# 0:OK/未調査 1:NG 2:調査した頂点 3:二度調査した頂点

for a in A:
    if F[a]==1:
        continue
    if F[a]==2:
        F[a]=1
        continue
    elif F[a]==0:
        F[a]=2
    k=2*a
    while k<=10**6+1:
        F[k]=1
        k+=a
            
res=0
for a in A:
    if F[a]==2:
        res+=1
print(res)

Submission status: Accepted

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

ma = max(a)
m = [0]*(ma + 1)

for i in a:
    if m[i] == 1:
        m[i] = 2
        continue
    for j in range(i,ma+1,i):
        m[j]+=1
ans = 0
for i in a:
    if m[i] == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

a = sorted(a)
ma = a[-1]
div = [0 for _ in range(ma+1)]

for i in range(n):
    for j in range(a[i], ma+1, a[i]):
        div[j] += 1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ma = a[-1]

dup = [0 for _ in range(ma+1)]
div = [0 for _ in range(ma+1)]

for i in range(n):
    dup[a[i]] += 1
#print('dup =', dup)

for i in range(n):
    for j in range(a[i], ma+1, a[i]):
        div[j] += 1
#print('div =', div)

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

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #小さい順にソートしておく
s=set()
cnt=collections.Counter(arr) #各要素の個数を事前に数えておく
for i in range(n):
 if arr[i] in s: #Aiがすでに列挙した数に含まれていれば処理を行わない
   continue
 if cnt[arr[i]]>=2: #Aiが2個以上含まれているとき、Ai自身を列挙した数に加える
   s.add(arr[i])
 for j in range(2,10**6//arr[i]+1): #Ai自身を除くAiの倍数を列挙する
   s.add(arr[i]*j)
ans=0
for i in range(n): #列挙した数に含まれないAiの個数を数える
 if arr[i] in s:
   continue
 ans+=1
print(ans)

Submission status: Accepted

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

sieve = [True] * 1000001

prev = 0

for i in range(N):
    if As[i] == prev:
        sieve[As[i]] = False
        continue
    else:
        prev = As[i]
        try:
            for j in range(2, 1000000 // prev + 1):
                sieve[prev * j] = False
        except:
            continue

count = 0
As = list(set(As))
for i in range(len(As)):
    if sieve[As[i]] is True:
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
'''
Created on 2020/08/23

@author: harurun
'''
def main():
  from collections import Counter
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  ans=0
  N=int(pin())
  A=list(map(int,pin().split()))
  c=Counter(A)
  t=max(A)
  dp=[True]*t
  for i in A:
    if dp[i-1]:
      n=2*i
      while n<=t:
        dp[n-1]=False
        n+=i
  for k in A:
    if c[k]==1 and dp[k-1]:
      ans+=1
  print(ans)
  return
main()

Submission status: Accepted

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

x=[0]*(10**6+1)
for i in a:
    x[i]+=1


for i in range(10**6+1):
    if x[i]>=1:
        j=2
        while i*j<=10**6:
            x[i*j]=0
            j+=1
print(x.count(1))

Submission status: Accepted

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

p=[0]*(10**6+1)
for i in b:
    if p[i]==0:
        j=2
        while i*j<=10**6:
            p[i*j]=1
            j+=1
a.append(-1)
a.insert(0,-1)
ans=0
for i in range(1,n+1):
    if a[i]!=a[i+1] and a[i]!=a[i-1] and p[a[i]]==0:
        ans+=1
print(ans)

Submission status: Accepted

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

cnt = {}

for item in a:
    if item not in cnt:
        cnt[item] = 0
    cnt[item] += 1

A = list(set(a))

candidate = []

for item in A:
    if cnt[item] == 1:
        candidate.append(item)

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

for item in A:
    for i in range(2, ((10**6)//item) + 1):
        judge[item*i] = False

ans = 0

for item in candidate:
    if judge[item]:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
def input(): return sys.stdin.readline().rstrip()
from decimal import Decimal

M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))

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

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

Submission status: Accepted

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

    ans = n
    A.sort()
    table = [True]*(A[-1]+1)
    for k,a in enumerate(A):
        if table[a]:
            if k+1<n and A[k+1]==a:
                ans-=1
            for i in range(a,A[-1]+1,a):
                table[i] = False
        else:
            ans-=1
    
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int, input().split()))
a.sort()
m=max(a)
arr=[0]*(m+1)
flag=[True]*(m+1)
ans=0
for i in range(n):
    if flag[a[i]]:
        arr[a[i]]+=1
        if not arr[a[i]]==1:
            continue
        for j in range(a[i]*2,m+1,a[i]):
            flag[j]=False
print(arr.count(1))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = max(A)
sieve = [True]*(m+1)
sieve[0] = False
ct = 0
for i in range(N):
    n = A[i]
    if sieve[n] == False:
        continue
    if i < N-1 and n == A[i+1]:
        sieve[n] = False
    if sieve[n] == True:
        ct += 1
    for k in range(n*2, m+1, n):
        sieve[k] = False
print(ct)

Submission status: Accepted

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

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

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
def cal(n,li):
    lis=[True]*(n+1)
    for item in li:
        if lis[item]:
            for i in range(item*2,n+1,item):
                lis[i]=False
    return lis
from collections import Counter

n=int(input())
a=list(map(int,input().split()))
a.sort()
l=cal(a[-1],a)
ll=Counter(a)
#print(l,ll)
ans=0
for i in range(n):
    if ll[a[i]]==1:
        if l[a[i]]:
            ans+=1

print(ans)

Submission status: Accepted

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

dp = [0]*(ma+1)

for i in range(1,n):
    if a[i]==a[i-1]:
        dp[a[i]]=1

for i in a:
    for j in range(i*2,ma+1,i):
        #if dp[j]==1:
            #break
        dp[j]=1
        
ans = 0
for i in a:
    if dp[i]==0:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	A.sort()
	l = A[-1]
	p = [1] * l
	for i in range(len(A)):
		a = A[i]
		if p[a-1] == 1:
			p[a-1] = 2
			for j in range(2 * a - 1, l, a):
				p[j] = 0
		elif p[a-1] == 2:
			p[a-1] = 0
	print(len([x for x in A if p[x - 1] in [1, 2]]))

main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(sorted(map(int,input().split())))
d=[0 for i in range(a[-1]+1)]
c=0
for i in range(len(a)):
  if d[a[i]]:
    continue
  if i==len(a)-1 or a[i]!=a[i+1]:
    c+=1
  for j in range(a[i],a[-1]+1,a[i]):
    d[j]=1
print(c)

Submission status: Accepted

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

A.sort()

furui = [0] * (max(A) + 1)

for i in A:
    if furui[i] >= 2:
        continue
    
    for j in range(i,len(furui),i):
        furui[j] += 1

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
# print(A)
multiple = [0]*(A[-1]+1)
for i in range(n):
    now = A[i]
    while(now <= A[-1]):
        multiple[now] += 1
        now += A[i]
ans = 0
for i in range(n):
    if(multiple[A[i]] == 1):
        ans += 1
# print(multiple)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    import collections
    counter = collections.Counter(A)
    maxA = max(A)
    dp = [True for _ in range(max(A)+1)]
    for a in A:
        if counter[a] > 1:
            dp[a] = False
        for j in range(a+a, maxA+1, a):
            dp[j] = False
    #print(dp)
    print(sum(1 for a in A if dp[a]))

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(a)
k = sorted(list(c.keys()))

kl =k[-1]
b = [1] * kl
cnt = 0
for i in k:
    if c[i] == 1 and b[i-1] == 1:
        cnt += 1
    for j in range(1, kl+1):
        if i*j > kl:
            break
        else:
            b[i*j-1] = 0
print(cnt)

Submission status: Accepted

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

A = max(a)

cnt = [0]*(A+1)
uq = []

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

for i in range(A+1):
    if cnt[i] == 1:
        uq.append(i)

cnt = [0]*((10**6)+1)
cnt1 = 0


a = list(set(a))

# for i in a:
#     for j in range(2,A+1):
#         if i*j<=A+1:
#             cnt[i*j] = 1

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

for i in uq:
    if cnt[i] == 0:
        cnt1 += 1

print(cnt1)