题目214：欧拉函数链

欧拉计划

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 的数列，求这些素数的和。

永恒的蓝色梦想

我觉得这样应该能求出来……

1. //project euler 214
   
2. #include<iostream>
   
3. using namespace std;
   
4. const int MAX = 40000000;
   
5. int phires[MAX], primes[MAX];
   
6. 
   
7. 
   
8. int phi(int n) {
   
9.     if (phires[n]) {
   
10.         return phires[n];
    
11.     }
    
12. 
    
13.     int i, a, b, c, count = 1;
    
14. 
    
15.     for (i = 2; i < n; i++) {
    
16.         a = i;
    
17.         b = n;
    
18.         while (b) {
    
19.             c = a % b;
    
20.             a = b;
    
21.             b = c;
    
22.         }
    
23.         if (a == 1) {
    
24.             count++;
    
25.         }
    
26.     }
    
27. 
    
28.     return phires[n] = count;
    
29. }
    
30. 
    
31. 
    
32. int main() {
    
33.     int i, j, k, sum = 0;
    
34. 
    
35.     for (i = 4; i < MAX; i += 2) {
    
36.         primes[i] = 1;
    
37.     }
    
38. 
    
39.     for (i = 3; i < MAX; i += 2) {
    
40.         if (!primes[i]) {
    
41.             k = i << 1;
    
42.             for (j = i; j < MAX; j += k) {
    
43.                 primes[j] = 1;
    
44.             }
    
45.             k = 3;
    
46.             for (j = i-1; (j = phi(j)) != 1; k++);
    
47.             if (k == 25) {
    
48.                 sum += i;
    
49.             }
    
50.         }
    
51.     }
    
52. 
    
53.     cout << sum << endl;
    
54.     return 0;
    
55. }

复制代码

guosl

可以使用筛法来求一个数的欧拉函数值，非常地快。然后枚举即可。