相关疑难解决方法(0)

我正在寻找一种有效的算法来计算任何给定整数的乘法分区.例如,12的这种分区的数量是4,即

12 = 12×1 = 4×3 = 2×2×3 = 2×6

我已经阅读了维基百科文章,但这并没有真正给我一个生成分区的算法(它只讨论了这些分区的数量,说实话,即使这对我来说也不是很清楚!) .

我正在看的问题要求我为非常大的数字(> 10亿)计算乘法分区,所以我试图为它提出一种动态编程方法(以便找到所有可能的分区,用于较小的数字可以是当较小的数字本身是一个较大数字的因素时重复使用),但到目前为止,我不知道从哪里开始!

任何想法/提示将不胜感激 - 这不是一个家庭作业问题,只是我试图解决的问题,因为它看起来很有趣!

我编写了以下函数,它找到给定自然数的所有除数,并将它们作为列表返回:

def FindAllDivisors(x):
    divList = []
    y = 1
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return divList

它的效果非常好,除了当输入是一个18位数字时它真的很慢.你对我如何加快它有什么建议吗？

更新:

我有以下方法来检查基于费马小定理的素数:

def CheckIfProbablyPrime(x):
    return (2 << x - 2) % x == 1

检查单个数字时,此方法非常有效,但是我不确定是否应该使用它来编译所有素数到一定的边界.