【python】高效找因数算法，竞赛题因数算法优化。

​做练习题的时候没查到python版的教程，于是自己写了一个

先看没过的代码：

def fdy(n):
    lis = []
    for i in range(1,n):
        if n % i == 0:       #判断是否能整除（是否为因数）
            lis.append(i)
    t = lis
    return t
print(fdy(int(input())))

这个是基础版，相信大家都看的懂

优化后的：

def cf(n):
    li = []                             #创建空列表用于存储因数
    for i in range(1, int(n**0.5) + 1): #因数从一开始算，算到原本的数的平方根停止
        if n % i == 0:                  #检测是i是否能被n整除（是否为因数）
            li.append(i)                #将因数 i 加入列列表
            li.append(int(n/i))         #加入 i 所对应的另一个因数
    li = list(set(li))                  #去个重（i恰好为平方根时会重复）
    li.sort()                           #排序（可以不用）
    return li                           #返回处理好的列表
print(cf(int(input())))                 #调用

首先先看这个图——16的因数【1，2，4，8，16】

1	16
2	8
4	4
5	2
16	1

可以看出16的因数是成对存在的，而且到平方根的时候就会开始重复

其他数字也遵循这个规律，它们的因数对开始重复的数字也都小于等于他们的平方根，大家可以试试试看

因此，只需要算到即可，对应的数字可以用 n / i 计算得出。

    for i in range(1, int(n**0.5) + 1): #因数从一开始算，算到原本的数的平方根停止
        if n % i == 0:                  #检测是i是否能被n整除（是否为因数）
            li.append(i)                #将因数 i 加入列列表
            li.append(int(n/i))         #加入 i 所对应的另一个因数

它的效率在数字大的时候就能很好的体现出来，例如基础版要检测一万次的时候，优化版只要检测一百次就能达到同样的效果。这个数字越大效果越明显

有不懂的地方可以在评论区留言，我看到的话会回复的。（第一次写，可能写的不是很清楚）

​