3360幸运数

3360   幸运数

题目描述

幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成 。
首先从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, 27,  31,  33,  37,  43, 45, 49,  51,55,57, 63,  67,  69,  73,  75,  79,  ...

输入格式:

输入两个正整数m  n,  用空格分开  (m  <   n  <   1000*1000) 

输出格式:

程序输出  位于m和n之间的幸运数的个数(不包含m和n)。 
输入样例 复制
30 69
输出样例 复制
8

说明

另一组样例:
样例输入1 
1  20 
样例输出1 
7
37
通过提交
时空限制1000ms/128mb
题目来源
评测方式在线评测
题目类型
难        度