求 \([L, R]\) 之间的素数之和 . \(L≤10^{10},2×10^{10} \le R \le 10^{11}\)
一个有点裸的 min_25筛 ? 现在我只会筛素数的前缀和 , 合数的过几天再学吧 .
首先推荐一波 yyb大佬博客 这个人很强 , 别那么fake就好啦
令 \(F(x) = x\) 显然此处 \(F(x)\) 是完全积性函数 .
我们需要求的就是 \[\displaystyle \sum_{i=1}^{n} [i \in Prime] F(i)\] .
这个就是 min_25筛的预处理部分 啦.
由 yyb博客 可得 .
对于下面这个表达式 ,
\[\displaystyle g(n,j)=\sum_{i=1}^ni[i\in P\ or \ min(p)>P_j,p|i,p\in P\ ]\]
有如下一个递推式 :
\[g(n,j)=\begin{cases} g(n,j-1)&P_j^2\gt n\\ g(n,j-1)-P_{j}[g(\frac{n}{P_j},j-1)-g(P_j-1,j-1)]&P_j^2\le n\end{cases}\]
这个直接实现是 \(\displaystyle O(\frac{n^{\frac{3}{4}}}{\log n})\) 的复杂度 qwq
然后考虑代码实现 . 我不太会非递归的 , 只会递归 ....
首先预处理前 \(\sqrt n\) 的素数 , (假设处理到了 \(lim\) )
以及 \(i=1 \sim lim\) 的 \(F(x)\) 前缀和 . (此处可适当处理多一点 , 时间效率会提高)
然后假设我们当前考虑的是 \(g(n, m)\) .
直观上共有三步 .
然后实现就特别容易啦 . 非递归常数似乎要小一点 , 到时候再学 ...
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ‘:‘ << x << endl
using namespace std;
void File() {
#ifdef zjp_shadow
freopen ("6202.in", "r", stdin);
freopen ("6202.out", "w", stdout);
#endif
}
const int N = 1e7 + 1e3, Lim = 1e7;
typedef __int128 ll;
inline ll read() {
ll x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == ‘-‘) fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * fh;
}
inline void Out(ll x, bool fir = true) {
if (!x) { if (fir) puts("0"); return ; }Out(x / 10, false); putchar (x % 10 + 48); if (fir) putchar (‘\n‘);
}
int prime[N], cnt = 0; bitset<N> is_prime;
ll sump[N];
void Init(int maxn) {
is_prime.set(); is_prime[0] = is_prime[1] = false;
For (i, 2, maxn) {
sump[i] = sump[i - 1];
if (is_prime[i])
prime[++ cnt] = i, sump[i] += i;
For (j, 1, cnt) {
register int res = i * prime[j];
if (res > maxn) break;
is_prime[res] = false;
if (!(i % prime[j])) break;
}
}
}
inline ll Sum(ll x) { return x * (x + 1) / 2 - 1; }
int tot = 0;
ll Sump(ll n, int m) {
if (n <= Lim && n < (ll)prime[m + 1] * prime[m + 1]) return sump[n];
for (; n < (ll)prime[m] * prime[m]; -- m);
ll res = Sum(n);
for (; m; -- m)
res -= (Sump(n / prime[m], m - 1) - /*Sump(prime[m] - 1, m - 1)*/ sump[prime[m] - 1]) * prime[m];
return res;
}
inline ll Calc(ll x) { return Sump(x, cnt - 1); }
int main () {
File();
Init(Lim);
ll l = read(), r = read(); Out(Calc(r) - Calc(l - 1));
return 0;
}原文：https://www.cnblogs.com/zjp-shadow/p/9190865.html