解题思路

核心算法

1. 埃拉托斯特尼筛 先在 $[0..N]$ 上做一次筛，得到布尔数组 isPrime[x] 是否为素数。 复杂度 $O(N\log\log N)$，空间 $O(N)$。

2. 枚举切分点（用 10 的幂） 对每个素数 $p\in[M,N]$，枚举所有后缀长度 $k=1..n-1$。使用 $10^k$ 来切分：

题目内容

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

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

现在输入两个正整数 $M$ 和 $N(M< N)$ ，请编写一个程序计算 $M$ 到 $N$ 之间有多少个可拆分素数(可以包含 $M$ 和 $N$ ) 。

输入描述

输入两个正整数 $M$ 和 $N(10<=M< N<=10^6)$ ，数字间空格隔开。

输出描述

输出 $M$ 和 $N$ 之间可拆分素数的个数(包含 $M$ 和 $N$ ) 。

样例1

输入

10 100

输出

4