#1003. [普及~提高]半质数

[普及~提高]半质数

说明

上完体育课,小 T 同学去校园超市买了瓶水,喝完后就直接去机房上编程课了,给创 新实验班上编程课的 Q 教练曾经培养出过世界冠军金斌大神,这可是小 T 和他的小伙伴们 的偶象啊!小 T 同学从小学起就一直在金斌学长亲手开发的在线评测系统上提交程序,一 想起小学编程课眼前立刻浮现出 Q 教练的亲切笑容,想起自己初学编程时有些单词如 continue 等总是记不住,每当遇到这种情况 Q 教练总会不厌其烦地拼给自己听。

自从进入 初三后小 T 已经有很久没写程序了,也很久没见到和蔼可亲的 Q 教练了,今天这节课来得 太及时了,想到这里小 T 不由加快了脚步,走进机房,只见一阵凉风拍面而来,瞬间让人 神清气爽,原来 Q 教练知道我们上一节是体育课,早开好了空调在等我们了。

今天的编程 课 Q 教练一上来就抛给了大家一个高端大气的问题:编程寻找给定范围内的半质数。半质数小 T 还是第一次听说,这个问题明显比找质数档次高多了! 质数的定义小 T 早在小学 就知道了,质数又称素数,指在大于 1 的自然数中,只能被 1 和本身整除的数, 也可定 义为只有 1 和本身两个因数的数。

而半质数的定义是这样的:若对于一个正整数 N,恰好 能够分解成两个质数的乘积,它就被称为半质数。比如,4=2*2,15=3*5 都是半质数,12 不是半质数,它的质因子分解式为 12=2*2*3,分解出的质数共有 3 个,其中有 2 个质数 2, 1 个质数 3。

输入格式

输入数据仅有一行包含两个用空格隔开的正整数 S 和 E,其中 2≤S≤E<5000000。

输出格式

输出数据仅有一行包含一个整数表示在 S 到 E 之间共有多少个半质数。

样例

4 26
10

提示

【样例解释 】

在 4 到 26 之间共有 10 个半质数,分别是 4, 6, 9, 10, 14, 15, 21, 22, 25, 26。

【数据范围 】

30%的数据满足:2≤S≤E<500

60%的数据满足:2≤S≤E<50000

100%的数据满足:2≤S≤E<5000000

【来源】

2014年常州市赛