python3 终于不超时了

看懂了，我还优化了一下，谢谢大神给的思路 def fun(n): if 2 <= n: while n % 2 == 0: n = n // 2 print(2, end=" ") if n != 1: i = 3 while i * i <= n: while n % i == 0: n = n // i print(i, end=" ") i = i + 2 if n - 1: print(n, end=" ") num = int(input()) fun(num)

关于while i * i <= n我的理解是：每次while n % i == 0内的循环求得是n的最小质因子，找到后再把n值更新，然后再求新n值得最小质因子。而一个非质数的最小质因子的平方是一定小于或等于这个非质数的。运算到最后n的值会更新成原始数的最大质因子，所以最后直接输出就可以（但得注意n不能是1）

关键就在第6行，把搜索次数减小了不少

n-1是为了输出最后一个质因数

n - 1是什么意思...

我懂答主的意思，但不理解n-1是怎么起作用的，我改成了 if n==1: pass else: print(n,end=' ') 这样也对

当n=1时这个是不是就有问题了

好巧妙哦，谢谢分享。

我也是这个思路，超时。

while i * i <= n and n >= i:为啥是这个条件呢？n都大于i的平方了，为啥还要加个n>=i呢？

这里之所以用 n-1 来判断输出是因为最后剩余的数如果不是1,就是不能被之前<=i 的所有数整除,那么这个数也是一个质数. [证明: 反证法, 如果n不是质数,那么他可以被大于等于(i+1)的数整除,商记为b, 又n跳出循环,则说明 i*i>n, 故 b

同样的思路，不同的时长，原来是我判断边界的条件不够严谨，学到了

能不能说下思路 这个思路没理解，怎么想到要i*i<=n 多谢

这个思路很巧妙，用第一层循环用while同时搭配实时更新减小的n，降低了时间复杂度，同时这里：while i * i <= n and n >= i 只写while i * i <= n 即可