1000ms

Difficulty: 3

所属公司 : 得物

时间 :2025年9月6日

算法与标签>数学

会员或题库专享

请先，开通会员或购买题库得物机考编程题库，可解锁完整内容。

购买得物机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（得物机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

核心算法

埃拉托斯特尼筛 先在 $[0..N]$ 上做一次筛，得到布尔数组 isPrime[x] 是否为素数。复杂度 $O(N\log\log N)$ ，空间 $O(N)$ 。
枚举切分点（用 10 的幂）

题目内容

小明最近刚刚学习完素数的概念，老师出了一个课后练习。问题是如果将一个 $n(n>=2)$ 位的素数拆分成两部分，其中高 $m$ 位是一个素数，低 $(n-m)$ 位也是一个素数，那么这个素数称为可拆分素数。

例如 $113$ 是一个素数，它可以拆成两部分，高两位 $11$ 是一个素数，低一位 $3$ 也是一个素数，因此 $113$ 是一个可拆分素数。