快手算法第三题质因数的数目，还能怎么优化

Python我也没AC

只有60……

我用的Java，和你的思路一模一样，全过了。。

leetcode204可以给灵感

python我没过。。c++能过60

python过了，用dic保存之前的，然后list保存之前遍历的质数

import math dic = {} rec = [] def iszhishu(x):     if x==2:         return True     for i in range(2,int(math.sqrt(x))+1):         if x%i==0:             return False     return True for i in range(2,n+1):     if iszhishu(i):         dic[i]=1         rec.append(i)     else:         for j in rec:             if i%j==0:                 dic[i]=dic[i//j]+1 ans = 0 for i in range(2,n+1):     ans += dic[i] print(ans) 我AC的代码

不要算sum(dp), 用个变量存

import math def isPnum(n): for v in range(2, int(math.sqrt(n))+1): if n % v == 0: return v return -1 N = int(input()) dp = [0 for _ in range(N+1)] for i in range(2, N+1): val = isPnum(i) if val == -1: dp[i] = 1 else: dp[i] = dp[i//val] + dp[val] print(sum(dp))

楼主的代码当N=2时会报错，其他结果都一样

我也用的Python，终极优化再优化ac的