常见数列
调和级数
满足调和级数 \(\mathcal O\left( \dfrac{N}{1} +\dfrac{N}{2}+\dfrac{N}{3}+\dots + \dfrac{N}{N} \right)\)，可以用 $ \approx N\ln N$ 来拟合，但是会略小，误差量级在 \(10\%\) 左右。本地可以在500ms内完成 \(10^8\) 量级的预处理计算。
| N的量级 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 累加和 | 27 | 482 | 7’069 | 93‘668 | 1’166‘750 | 13‘970’034 | 162‘725’364 | 1‘857’511‘568 | 20’877‘697’634 |
下方示例为求解 \(1\) 到 \(N\) 中各个数字的因数值。
const int N = 1E5;
vector<vector<int>> dic(N + 1);
for (int i = 1; i <= N; i++) {for (int j = i; j <= N; j += i) {dic[j].push_back(i);}
}
素数密度与分布
| N的量级 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 素数数量 | 4 | 25 | 168 | 1‘229 | 9’592 | 78‘498 | 664’579 | 5‘761’455 | 50‘847’534 |
除此之外，对于任意两个相邻的素数 \(p_1,p_2 \le 10^9\) ，有 \(|p_1-p_2|<300\) 成立，更具体的说，最大的差值为 \(282\) 。
因数最多数字与其因数数量
| N的量级 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 因数最多数字的因数数量 | 4 | 25 | 32 | 64 | 128 | 240 | 448 |
| 因数最多的数字 | - | - | - | 7560, 9240 | 83160, 98280 | 720720, 831600, 942480, 982800, 997920 | - |