相关疑难解决方法(0)

我写了一个试图找到Amicable Pairs的程序.这需要找到数字的适当除数的总和.

这是我目前的sumOfDivisors()方法:

int sumOfDivisors(int n)
{  
    int sum = 1;
    int bound = (int) sqrt(n);
    for(int i = 2; i <= 1 + bound; i++)
    {
        if (n % i == 0)
            sum = sum + i + n / i;
    } 
    return sum;
}

所以我需要做很多因子分解,这开始成为我应用程序的真正瓶颈.我在MAPLE中输入了一个巨大的数字,它将它快速地考虑在内.

什么是更快的分解算法？

对于问题https://leetcode.com/problems/perfect-squares/我已经使用以下算法解决了它。问题是

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

它所做的基本上是尝试通过减去每个可能的数字（[1, 4, 9, .. sqrt(n)] 来从目标数字变为 0，然后对获得的每个数字进行相同的工作。我很难理解这个算法的时间复杂度，因为每个级别的分支都是 sqrt(n) 次，但有些分支注定要提前结束......

def numSquares(n):


        squares = [i**2 for i in range(1, int(n**0.5)+1)]

        step = 1
        queue = {n}

        while queue:
            tempQueue = set()

            for node in queue:
                for square in …