Open xehoth opened 6 years ago
https://blog.xehoth.cc/Extended-Eratosthenes-Sieve/
扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ （这里以实际运行效果估计，实际复杂度据说和洲阁筛一样）求出一般积性函数的前缀和，消耗 $O(\sqrt{n})$ 的空间。
筛等幂质数前缀和的公式打错辣~
Cydiater
commented
6 years ago Cydiater
commented
6 years ago
https://blog.xehoth.cc/Extended-Eratosthenes-Sieve/
扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ （这里以实际运行效果估计，实际复杂度据说和洲阁筛一样）求出一般积性函数的前缀和，消耗 $O(\sqrt{n})$ 的空间。