题目214：欧拉函数链
本帖最后由 欧拉计划 于 2016-11-25 04:37 编辑Totient Chains
Let φ be Euler's totient function, i.e. for a natural number n, φ(n) is the number of k, 1 ≤ k ≤ n, for which gcd(k,n) = 1.
By iterating φ, each positive integer generates a decreasing chain of numbers ending in 1.
E.g. if we start with 5 the sequence 5,4,2,1 is generated.
Here is a listing of all chains with length 4:
5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1
Only two of these chains start with a prime, their sum is 12.
What is the sum of all primes less than 40000000 which generate a chain of length 25?
题目：
定义 φ 为欧拉函数：对于任意自然数 n，φ(n) 就是 1 到 n 之间，与 n 互质的数的个数。
如果对 φ 进行迭代，则任一正整数都会生成一个递减到 1 的数列。
比如，我们从 5 开始，则可以得到 5,4,3,2,1 的数列。
下面是所有长度为 4 的数列：
5,4,2,1
7,6,2,1
8,4,2,1
9,6,2,1
10,4,2,1
12,4,2,1
14,6,2,1
18,6,2,1
上面的数列中，只有两个的初始值是质数，它们（初始值）的总和为 12（5+7）。
请问，小于 40000000 的素数中，哪些能生成长度为 25 的数列，求这些素数的和。
本帖最后由 永恒的蓝色梦想 于 2020-4-21 13:23 编辑
我觉得这样应该能求出来……{:10_277:}//project euler 214
#include<iostream>
using namespace std;
const int MAX = 40000000;
int phires, primes;
int phi(int n) {
if (phires) {
return phires;
}
int i, a, b, c, count = 1;
for (i = 2; i < n; i++) {
a = i;
b = n;
while (b) {
c = a % b;
a = b;
b = c;
}
if (a == 1) {
count++;
}
}
return phires = count;
}
int main() {
int i, j, k, sum = 0;
for (i = 4; i < MAX; i += 2) {
primes = 1;
}
for (i = 3; i < MAX; i += 2) {
if (!primes) {
k = i << 1;
for (j = i; j < MAX; j += k) {
primes = 1;
}
k = 3;
for (j = i-1; (j = phi(j)) != 1; k++);
if (k == 25) {
sum += i;
}
}
}
cout << sum << endl;
return 0;
} 可以使用筛法来求一个数的欧拉函数值，非常地快。然后枚举即可。
页:
[1]