欧拉计划第70题：Euler's Totient function Python实现性能优化求助

问题背景 #

我在解决欧拉计划第70题时，自己实现的欧拉函数（Euler's Totient function）运行速度太慢，导致10个测试用例里有5个无法通过，求优化思路。

欧拉计划第70题描述 #

Euler's Totient function，φ(n)（有时称为phi函数）用于计算小于等于n且与n互质的正整数的数量。例如，1、2、4、5、7、8均小于9且与9互质，因此φ(9)=6。数字1被认为与所有正整数互质，故φ(1)=1。

有趣的是，φ(87109)=79180，且87109是79180的排列。

找出满足1 < n < N，且φ(n)是n的排列，同时n/φ(n)比值最小的n值。

输入格式：输入一个整数N
约束条件：1<=N<=10^7
输出格式：输出对应测试用例的答案
示例输入：100
示例输出：21

当前代码（存在性能瓶颈） #

from math import gcd
from itertools import permutations

def totatives(n):
    phi = int(n > 1 and n)
    for p in range(2, int(n ** .5) + 1):
        if not n % p:
            phi -= phi // p
            while not n % p:
                n //= p
    #if n is > 1 it means it is prime
    if n > 1: phi -= phi // n 
    return phi

def permute(num,phi_num):
    temp="".join(sorted(str(num)))
    phi_num="".join(sorted(str(phi_num)))
    return temp==phi_num

N=int(input())
d={}
for n in range(12,N):
    if permute(n,totatives(n)):
        #print(permute,phi(n))
        d[n]=(n/totatives(n))
    
#print(d)
min_b=min(d.values())
for a,b in d.items():
    if b==min_b:
        print(a)
        break

优化方案 #

1. 用欧拉筛预计算所有φ(n)值 #

单个计算φ(n)的时间复杂度为O(√n)，对于N=1e7来说，逐个计算会导致O(N√N)的时间复杂度，完全无法在时限内完成。改用**欧拉筛（线性筛）**预计算1到N-1的所有φ值，时间复杂度降至O(N)，这是核心优化点。

实现逻辑：

• 初始化数组phi，令phi[i] = i
• 维护质数列表，遍历每个数i：
  • 若phi[i] == i，说明i是质数，将其加入质数列表，同时更新phi[i] = i-1
  • 对每个已找到的质数p，计算j = i*p：
    • 若i能被p整除，说明p是i的质因子，此时phi[j] = phi[i] * p
    • 若i不能被p整除，说明p是j的新质因子，此时phi[j] = phi[i] * (p-1)

2. 实时维护最小值，避免冗余存储 #

不需要用字典保存所有符合条件的n和比值，遍历过程中直接记录当前最小比值对应的n，大幅节省内存（尤其N=1e7时）。

3. 小幅度优化排列判断 #

原判断逻辑已经够用，若想进一步提升，可缓存数字的排序字符串结果，但对整体性能影响有限，优先级低于筛法优化。

优化后的代码 #

def main():
    import sys
    input = sys.stdin.read().strip()
    N = int(input)
    if N <= 2:
        print(0)
        return
    
    # 欧拉筛预计算phi数组
    phi = list(range(N))
    primes = []
    for i in range(2, N):
        if phi[i] == i:  # i是质数
            primes.append(i)
            phi[i] = i - 1
        for p in primes:
            if i * p >= N:
                break
            if i % p == 0:
                phi[i * p] = phi[i] * p
                break
            else:
                phi[i * p] = phi[i] * (p - 1)
    
    min_ratio = float('inf')
    result = 0
    
    for n in range(12, N):
        phi_n = phi[n]
        # 判断是否为排列
        if sorted(str(n)) == sorted(str(phi_n)):
            ratio = n / phi_n
            if ratio < min_ratio:
                min_ratio = ratio
                result = n
    
    print(result)

if __name__ == "__main__":
    main()

额外优化细节 #

• 使用sys.stdin.read()代替input()，处理大输入更高效
• 欧拉筛生成的phi数组占用内存约40MB（N=1e7时，每个元素为4字节整数），完全在常规内存承受范围内

内容的提问来源于stack exchange，提问作者vijayalakshmi_bhagat