提出 #14367718

---

ソースコード 拡げる

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

U = 10**6 + 10

def main(A, primes):
    B = np.zeros(U + 1, np.int64)
    for x in A:
        B[x] += 1
    for p in primes:
        for i in range(U // p + 1):
            B[p * i] += B[i]
    ret = 0
    for x in A:
        ret += B[x] == 1
    return ret

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('main', '(i8[::1],i8[::1])')(main)
    cc.compile()
    exit()
from my_module import main

def prime_table(N):
    is_prime = np.zeros(N, np.int64)
    is_prime[2:3] = 1
    is_prime[3::2] = 1
    for p in range(3, N, 2):
        if p * p >= N:
            break
        if is_prime[p]:
            is_prime[p * p::p + p] = 0
    return is_prime, np.where(is_prime)[0]

A = np.array(read().split(), np.int64)[1:]
_, primes = prime_table(U)

print(main(A, primes))

提出情報

ジャッジ結果