我越来越沉迷于项目欧拉问题.然而,因为一周我被#214困住了.
这是问题的简短版本:PHI()是Euler的整数函数,即对于任何给定的整数n,PHI(n)= k <= n的数字,其中gcd(k,n)= 1.
我们可以迭代PHI()来创建一个链.例如从18开始:
PHI(18)= 6 => PHI(6)= 2 => PHI(2)= 1.
所以从18开始我们得到一条长度为4的链(18,6,2,1)
问题是计算小于40e6的所有素数之和,它产生一个长度为25的链.
我构建了一个计算任何数字的链长的函数,并且我测试了它的
小值:它运行良好且快速.
所有素数的总和<= 20,它产生一个长度
为4:12的所有素数<= 1000的总和,产生一个长度为10的链:39383
不幸的是我的算法不能很好地扩展.当我将它应用于问题时,需要几个小时来计算...所以我停止它因为Project Euler问题必须在不到一分钟内解决.
我认为我的主要检测功能可能很慢所以我给程序提供了一个素数列表<40e6以避免素性测试......代码现在运行得更快一些,但仍然无法获得解决方案不到几个小时(我不想要这个).
那么我在这里缺少任何"魔术"吗？我真的不明白如何提高效率......
我不是要求解决方案,因为与优化斗争是Project Euler的所有乐趣.但是,任何可能让我走上正轨的小提示都会受到欢迎.
谢谢 !
抱歉,评论的格式错误,我无法删除它.所以这又是:
为了计算totient函数,我使用以下内容:对于给定的n,让我们调用它的因子列表.
披(N)= N*PROD((P-1)/ p)的
例如:2,3是18 => phi(18)= 18*1/2*2/3 = 6的因子
所以这样我不计算任何gcd.给我这些因素的函数是用MATLAB构建的(是的,我忘了提到我在Matlab中编写代码).也许我应该重写分解功能......
我会大胆猜测，耗时的部分是计算数字的总数。
一种想法可能是尝试以某种巧妙的方式生成这些。想想是否可以一次性计算出所有数字，而不是一次只计算一个数字......
另外，你如何计算 totient 函数？定义（整数 k 的数量，其中 gcd(n,k)==1）并不是一种有用的使用方法。查一下，看看是否能找到更合适的公式。
编辑：是的，这就是我想要的表达方式。但是遍历每个整数、分解它并计算 totient 太慢了。寻找一种无需进行任何因式分解即可计算 totients 的方法......