#6202. 叶氏筛法

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: xmcp

题目描述

计算给定区间内所有质数之和。

输入格式

输入一行两个整数 L,R

输出格式

输出一个整数,表示 L R 之间(包括 L R )所有质数的和。

评分方式

假设你的输出是 x ,正确答案是 y ,那么:

如果 y \times ( 1 - 10^{-10} ) - 1 \leq x \leq y \times ( 1 + 10^{-10} ) + 1 ,你能得到该测试点的全部分数;

否则,该测试点你不得分。

(说人话就是:若果你不想写高精的话,可以用 double 存答案)

样例输出保证是准确的。

样例

样例输入 1

3 16

样例输出 1

39

样例解释 1

3 + 5 + 7 + 11 + 13 = 39

样例输入 2

1 9876547210

样例输出 2

2167522859485863766

数据范围与提示

测试点 数据范围与约定
1 L, R \leq 10^6
2 L, R \leq 10^9
3, 4 L, R \leq 2.5\times 10^9
5 L, R \leq 10^{10}, R - L \leq 10^6
6 L = 1, R = 9\times 10^9
7, 8 L = 1,R \leq 10^{10}
9, 10 L \leq 10^{10}, 2\times 10^{10} \leq R \leq 10^{11}

对于所有测试点,有 1 \leq L \leq R

代码长度限制是 10 KiB。