Euler 214项目，我如何使它更有效率？

Question

我越来越沉迷于Euler项目的问题。然而，从一周以来，我就被#214困住了。

下面是问题的一个简短版本: PHI()是Euler's totient函数，即对于给定的整数n，PHI(N)= gcd(k，n)=1的k<=n数。

我们可以迭代PHI()来创建一个链。例如，从18开始：

PHI(18)=6 => PHI(6)=2 => PHI(2)=1。

从18开始，我们得到了一条长度为4 (18,6,2,1)的链。

问题是计算所有小于40e6的素数之和，这些素数产生一个长度为25的链。

我构建了一个计算任何数字的链长度的函数，并测试了它

小值:它运行良好，速度快。

生成长度为4: 12的链的所有primes<=20之和

生成长度为10: 39383的链的所有primes<=1000之和

不幸的是，我的算法没有很好的扩展。当我把它应用于这个问题时，需要几个小时来计算.所以我停止它，因为Euler项目的问题必须在不到一分钟内解决。

我认为我的主要检测功能可能很慢，所以我给程序提供了一个素数<40e6的列表，以避免原始性测试。代码现在运行得稍微快一点，但是仍然没有办法在不到几个小时的时间内找到解决方案(我不想这样做)。

我在这里错过了什么“魔术”吗？我真的不明白如何在这个问题上更有效率.

我并不是在要求解决方案，因为与优化进行斗争是Euler项目的全部乐趣。然而，任何能让我走上正轨的小提示都是值得欢迎的。

谢谢！

对不起，注释的格式错误，我无法删除它。所以这里又是这样：

为了计算totient函数，我使用如下方法:对于给定的n，让我们调用它的因子列表。

phi(n)=n*prod((p-1)/p)

ex: 2,3是18 => phi( 18 ) =18* 1/2 * 2/3 =6的因子

所以用这种方法我不计算任何gcd。给我因子的函数是在MATLAB中构建的(是的，我忘了提到我在Matlab中编码)。也许我该重写分解函数..。

Answer 1

我会胡思乱想，花时间的部分是计算数字的乘数。

一种想法可能是尝试以某种聪明的方式生成这些信息。想一想是否有可能同时计算它们，而不是一次只计算一个数字.

另外，你是如何计算函数的呢？定义(整数数k，其中gcd(n，k)==1)不是处理它的有用方法。查一查，看看你能不能找到一个更合适的配方。

编辑:是的，这就是我想要的表达。但是，遍历每一个整数，分解它，计算这个整数太慢了。寻找一种不用做任何因子计算的方法.

Answer 2

试着倒退..。(从1，2等开始，往上爬，而不是往下走，连接到链子上)

编辑:还请注意totient( x )有一个特殊结构，即totient(x) =x*，它是(1-(1/p))的乘积，其中p是划分x的不同的素因子。

Answer 3

提示：

1. 使用回忆录，不计算phi(n)不止一次。
2. 在计算phi( n )时，phi()尝试使用您已经为较小的n计算了的的值。像phi(m*n) = phi(m) * phi(n)这样的东西，m和n应该拥有哪些属性？
3. 当p是素数时，你知道phi(p) 是什么吗？