求约数和的三重境界
一、先上结论
| 数据量/办法 | 暴力\(O(N^2)\) | 普通筛法\(O(N\cdot logN)\) | 欧拉筛法\(O(N)\) |
|---|---|---|---|
| \(n=1e5\) | \(13402ms\) | \(4ms\) | \(2ms\) |
| \(n=1e6\) | 无法忍受，不能出结果 | \(67ms\) | \(15ms\) |
考虑到\(O(N^2)\)的复杂度，按\(C++\)一秒\(1e8\)的运算能力，\(1e6*1e6=1e12\),应该是需要\(1e12 /1e8=1e4=10000\)秒，三个小时，去死吧！太垃圾了~
注意：
- 普通筛法:代码极短，性能足够，推荐使用
- 欧拉筛法：代码太长，性能优秀，不推荐使用
二、暴力法
//暴力大法 , 不包含自己
int bforce(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
if (n % i == 0)
sum = sum + i;
}
return sum;
}
时间复杂度\(O(N^2)\)
三、普通筛法
for (int i = 1; i <= n; i++) // O(n)
for (int j = 2; j <= n / i; j++) // 调和级数O(logn) = n + n / 2 + n / 3 + ... + n/n = lnn + c
sum2[i * j] += i;
时间复杂度\(O(N\cdot logN)\)
四、线性筛法
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
int num[N]; // i的最小质因子构成的一个等比数列求和的结果
int sd[N]; //约数和
void get_primes(int n) {
sd[1] = 1; // 1的约数和是1
for (int i = 2; i <= n; i++) { //遍历 2~n,筛质数的同时，筛出每个数字的约数和
if (!st[i]) { //如果i是质数
primes[cnt++] = i; //记录i到质数数组中
sd[i] = num[i] = 1 + i; //质数的约数和是1+自身
}
for (int j = 0; primes[j] * i <= n; j++) {
st[i * primes[j]] = true; //记录primes[j]的整数倍(i倍)是合数
if (i % primes[j]) { //如果i不包含primes[j]这个质数因子
sd[i * primes[j]] = sd[i] * sd[primes[j]];
num[i * primes[j]] = primes[j] + 1;
} else { //如果i包含了primes[j]这个质数因子
sd[i * primes[j]] = sd[i] / num[i] * (num[i] * primes[j] + 1);
num[i * primes[j]] = num[i] * primes[j] + 1;
break;
}
}
}
}
五、附：测试对比的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int sum1[N], sum2[N], sd[N];
int n = 1e5;
//暴力大法 , 不包含自己
int bforce(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
if (n % i == 0)
sum = sum + i;
}
return sum;
}
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
int num[N]; // i的最小质因子构成的一个等比数列求和的结果
int sd[N]; //约数和
void get_primes(int n) {
sd[1] = 1; // 1的约数和是1
for (int i = 2; i <= n; i++) { //遍历 2~n,筛质数的同时，筛出每个数字的约数和
if (!st[i]) { //如果i是质数
primes[cnt++] = i; //记录i到质数数组中
sd[i] = num[i] = 1 + i; //质数的约数和是1+自身
}
for (int j = 0; primes[j] * i <= n; j++) {
st[i * primes[j]] = true; //记录primes[j]的整数倍(i倍)是合数
if (i % primes[j]) { //如果i不包含primes[j]这个质数因子
sd[i * primes[j]] = sd[i] * sd[primes[j]];
num[i * primes[j]] = primes[j] + 1;
} else { //如果i包含了primes[j]这个质数因子
sd[i * primes[j]] = sd[i] / num[i] * (num[i] * primes[j] + 1);
num[i * primes[j]] = num[i] * primes[j] + 1;
break;
}
}
}
}
int main() {
//记录开始时间
clock_t begin = clock();
// 1、暴力计算 O(n^2)
// for (int i = 1; i <= n; i++) sum1[i] = bforce(i);
// for (int i = 1; i <= n; i++) printf("%d ", sum1[i]);
puts("");
//记录结束时间
clock_t end = clock();
cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
// 2、通过筛法求出1到n的所有约数之和
//记录开始时间
begin = clock();
for (int i = 1; i <= n; i++) // O(n)
for (int j = 2; j <= n / i; j++) // 调和级数O(logn) = n + n / 2 + n / 3 + ... + n/n = lnn + c
sum2[i * j] += i;
// for (int i = 1; i <= n; i++) printf("%d ", sum2[i]);
puts("");
//记录结束时间
end = clock();
cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
// 3、利用欧拉定理筛出约数和
//记录开始时间
begin = clock();
get_primes(n);
// for (int i = 1; i <= n; i++) printf("%d ", sd[i]-i);
puts("");
//记录结束时间
end = clock();
cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
return 0;
}