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

永恒的蓝色梦想

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

//project euler 214
#include<iostream>
using namespace std;
const int MAX = 40000000;
int phires[MAX], primes[MAX];


int phi(int n) {
    if (phires[n]) {
        return phires[n];
    }

    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[n] = count;
}


int main() {
    int i, j, k, sum = 0;

    for (i = 4; i < MAX; i += 2) {
        primes[i] = 1;
    }

    for (i = 3; i < MAX; i += 2) {
        if (!primes[i]) {
            k = i << 1;
            for (j = i; j < MAX; j += k) {
                primes[j] = 1;
            }
            k = 3;
            for (j = i-1; (j = phi(j)) != 1; k++);
            if (k == 25) {
                sum += i;
            }
        }
    }

    cout << sum << endl;
    return 0;
}

guosl

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