kainster

never too late
posts - 33, comments - 3, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

原来世界上有欧拉函数这种东西

Posted on 2008-10-28 08:41 kainster 阅读(215) 评论(0)  编辑  收藏

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?

Euler这周的新题，发现我很没文化，居然不知道有欧拉函数这种现成的东西，还自己推了半天没推出来，最后还是觉得肯定有这么个函数才百度出来的。代码没优化的时候大概用了两个小时算出来结果，现在优化以后的大概一分钟。优化的方法就是一直用跟Eratosthems筛选法类似的思想，从小到大对每个素数的所有倍数做处理

using System;
using System.Collections.Generic;
using System.Text;

namespace Numberkksk
{
    class Program
    {
        static long NUM = 40000000;
        //为了方便，以下数组都从1开始计数

        // 转移数组，存储的是每个数的互质数的个数
        static int[] tars = new int[NUM + 1];
        // 步数数组，存储的是每个数到1所需要的步数
        static int[] steps = new int[NUM + 1];
        static void Prob214()
        {
            //初始化tar数组，令i位置的值为i
            for (int i = 1; i < NUM + 1; i++)
                tars[i] = i;

            for (int i = 2; i < NUM + 1; i++)
            {
                // 如果i位置的数为i的话说明i没有被操作过，是素数
                if (tars[i] != i)
                    continue;

                // 如果i是素数，则对i的所有在范围内的倍数做 乘以(i-1)/i的操作（根据欧拉函数） 
                int num = 2 * i;
                while (num < NUM + 1)
                {
                    tars[num] /= i;
                    tars[num] *= i - 1;
                    num += i;
                }
                // 最后，对于i本身，素数的互质数数目为i-1个（其实也可以直接放到循环里面）
                tars[i] = i - 1;
            }
            Console.WriteLine("Tars builds successful");

            steps[1] = 1;
            long count = 0;
            // 从小到大为步数数组赋值（也可以放到上面的循环里）
            for (int i = 2; i < NUM + 1; i++)
            {
                steps[i] = steps[tars[i]] + 1;

                if (steps[i] == 25 && tars[i] == i - 1)
                {
                    count += i;
                }
            }

            Console.WriteLine(count);
        }

        static void Main(string[] args)
        {
            Prob214();
            Console.Read();
        }

    }
}

只有注册用户登录后才能发表评论。
网站导航: