欧拉计划 Project Euler 69（欧拉总计函数与最大值）题解

题干

欧拉总计函数与最大值

小于$n$且与$n$互质的正整数的数量记为欧拉总计函数$\phi (n)$，例如，$1、2、4、5、7$和$8$均小于$9$且与$9$互质，因此$\phi (9)=6$

可以看出，对于$n\le 10$，当$n=6$时$\frac{n}{\phi (n)}$取得最大值。
对于$n\le 1000000$，求使得$\frac{n}{\phi (n)}$取得最大值的$n$。

思路

为了找到在$n\le 1000000$范围内使得$\frac{n}{\phi (n)}$取得最大值的$n$，我们需要理解欧拉函数的性质以及表达式$\frac{n}{\phi (n)}$。

欧拉函数$\phi (n)$计算的是小于或等于$n$且与n互质的正整数的个数。
$\phi (n)$的计算公式与$n$的素因数分解相关。如果$n=p_1^{k_1}{p}_2^{k_2}\dots p_r^{k_r}$是$n$的素因数分解，那么：
$$\phi (n)=n\prod _{p|n}(1-\frac{1}{p})=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_r})$$
因此$\frac{n}{\phi (n)}$可以改写为
$$\frac{n}{\phi (n)}=\frac{n}{n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_r})}=\frac{1}{(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_r})}$$
进一步化简为
$$\frac{n}{\phi (n)}=(\frac{p_1}{p_1-1})(\frac{p_2}{p_2-1})\dots (\frac{p_r}{p_r-1})$$
要使$\frac{n}{\phi (n)}$最大化，我们需要让这个乘积最大化，注意到每一项$\frac{p}{p-1}$都大于$1$，为了使这个乘积尽可能的大，我们应该选择：

1. 尽可能多的不同的素因子。
2. 尽可能小的素因子，因为对于较小的素数$p$，$\frac{p}{p-1}$的值较大。

因此，我们应该选择$n$为最小的若干连续素数的乘积，并且这个乘积不超过$1000000$这种数被称为素连乘数(primorial)。
让我们来计算一下这些素连乘数

1. $2$
2. $2\times 3=6$
3. $2\times 3\times 5=30$
4. $2\times 3\times 5\times 7=210$
5. $2\times 3\times 5\times 7\times 11=2310$
6. $2\times 3\times 5\times 7\times 11\times 13=30030$
7. $2\times 3\times 5\times 7\times 11\times 13\times 17=510510$
8. $2\times 3\times 5\times 7\times 11\times 13\times 17\times 19=9699690$

由于$9699690\ge 1000000$所以我们能取到的最大的数是$510510$。
这个数$n=510510$是由最小的连续素数$2,3,5,7,11,13,17$的乘积得到的。任何其它小于等于$1000000$的数，如果包含更大的素因数或者素因数的幂次（这不会改变$\frac{n}{\phi (n)}$的值，因为$\frac{n}{\phi (n)}$只依赖于不同的素因数），或者包含的因数更少，其$\frac{n}{\phi (n)}$的值都会更小。
因此，对于$n\le 1000000$,使得$\frac{n}{\phi (n)}$取得最大值的n是$510510$。

code

其实根据上诉的思路不需要code了，但是还是给一下把
可以用筛法先筛选一些素数，当然也可以直接打表

// 510510
#include <bits/stdc++.h>using namespace std;using ll = long long;void solve() {ll li = 1000000;vector<int> pri = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};ll n = 1, cur = 1;for (int p : pri) {if (p == 0) continue;if (cur > li / p) {break;}cur *= p;n = cur;}cout << n << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}