寛神的幸运数
题号:NC220010
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

寛神有一堆的幸运数,因为他非常善于学习,只要听到有人用哪个数做幸运数,就会把这个数加到自己的幸运数集合。
直到有一天他听说了波兰数学家乌拉姆的幸运数。它采用与生成素数类似的“筛法”生成

首先从1开始写出自然数1,2,3,4,5,6,....

1就是第一个幸运数。

我们从2这个数开始。把所有序号能被2整除的项删除,变为:

1 _ 3 _ 5 _ 7 _ 9 ....

把它们缩紧,重新记序,为:

1 3 5 7 9 ....。这时,3为第2个幸运数,然后把所有能被3整除的序号位置的数删去。注意,是序号位置,不是那个数本身能否被3整除!!删除的应该是5,11, 17, ...

此时7为第3个幸运数,然后再删去序号位置能被7整除的(19,39,...)

最后剩下的序列类似:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, ...

输入描述:

输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
众所周知,寛神经常算错时间复杂度,所以实际上是(m<n<15*1000)

输出描述:

程序输出位于m和n之间的幸运数的个数(不包含m和n)。

示例1

输入

复制
1 20

输出

复制
5
示例2

输入

复制
30 69

输出

复制
8

备注:

程序输出位于m和n之间的幸运数的个数(不包含m和n)。