第三筛式

发布时间: 2018年12月8日 23:24   最后更新: 2018年12月8日 23:27   时间限制: 8000ms   内存限制: 128M

定义积性函数 $f(x)$ :

$$f(x) = \begin{cases}1 & (x = 1)  \\3e+1 & (x = p^e,p \equiv 1(mod 4),e \geq 1) \\1 & (x = p^e,p \not \equiv 1(mod 4), e \geq 1) \end{cases}$$

其中 $p$ 为质数。

试求 $\Sigma_{i=1}^{n}f(i)$ 。

第一行一个数字 $T$ 代表测试数据组数, 接下来 $T$ 行每行一个数 $n$ 。 $T \leq 5$ , $n \leq 10^{9}$

对于每组数据,输出 $\Sigma_{i=1}^{n}f(i)$ 。

复制
2
9
11
12
17

筛法

D_Tesla