当前位置：首页 > news >正文

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

news 来源：原创 2025/8/3 11:14:11

欧拉计划 Project Euler 69 题解

题干
- 欧拉总计函数与最大值
思路
code

题干

欧拉总计函数与最大值

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

n	Relatively Prime	phi(n)	n/phi(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

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

思路

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

欧拉函数 $\varphi(n)$ 计算的是小于或等于 $n$ 且与n互质的正整数的个数。
$\varphi(n)$ 的计算公式与 $n$ 的素因数分解相关。如果 $p_{1}^{k_{1}}p_{2}^{k_{2}}\dots p_{r}^{k_{r}}$ 是 $n$ 的素因数分解，那么：
$\varphi(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}{\varphi(n)}$ 可以改写为
$\frac{n}{\varphi(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}{\varphi(n)} = (\frac{p_{1}}{p_{1} -1})(\frac{p_{2}}{p_{2}-1})\dots(\frac{p_{r}}{p_{r}-1})$
要使 $\frac{n}{\varphi(n)}$ 最大化，我们需要让这个乘积最大化，注意到每一项 $\frac{p}{p-1}$ 都大于 $1$ ，为了使这个乘积尽可能的大，我们应该选择：

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

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

$2$
$2\times3=6$
$\times 3 \times 5 = 30$
$\times 3 \times 5 \times 7 = 210$
$\times 3 \times 5 \times 7 \times 11 = 2310$
$\times 3 \times 5 \times 7 \times 11 \times 13 =30030$
$\times 3 \times 5 \times 7 \times 11 \times 13 \times17=510510$
$\times 3 \times 5 \times 7 \times 11 \times 13\times17\times19=9699690$

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

欧拉计划 Project Euler 69 题解

题干

欧拉总计函数与最大值

思路

code

相关文章：