CodewarsBuddyPairsKata優化Python解決方案

這是卡塔鏈接：https : //www.codewars.com/kata/59ccf051dcc4050f7800008f/shell

好友對 你知道一個數的除數是什么。當你只考慮除 n 本身以外的除數時，正整數 n 的除數被稱為適當的。在以下描述中，除數將意味著適當的除數。例如，對于 100，它們是 1、2、4、5、10、20、25 和 50。

讓 s(n) 是這些 n 的真除數的總和。給好友打電話兩個正整數，使得每個數字的真除數之和比另一個數字多一個：

(n, m) 是一對伙伴，如果 s(m) = n 1 且 s(n) = m 1

例如 48 & 75 就是這樣一對：

48 的除數是：1, 2, 3, 4, 6, 8, 12, 16, 24 --> sum: 76 = 75 1 75 的除數是：1, 3, 5, 15, 25 --> sum : 49 = 48 1 任務 給定兩個正整數 start 和 limit，函式 buddy(start, limit) 應該回傳第一對 (nm) buddy 對，使得 n（正整數）介于 start（含）和 limit（包括的）; m 可以大于 limit 并且必須大于 n

如果沒有滿足條件的伙伴對，則回傳“Nothing”或（對于 Go lang）nil 或（對于 Dart）null；（對于 Lua、Pascal、Perl）[-1，-1]。

test.assert_equals(buddy(10, 50), [48, 75])

test.assert_equals(buddy(2177, 4357), "Nothing")

test.assert_equals(buddy(57345, 90061), [62744, 75495])

test.assert_equals(buddy(1071625, 1103735), [1081184, 1331967])

這是我的解決方案，但我收到Execution Timed Out錯誤花了太多時間：

def sum_divisors(num):
    sum = 0
    for i in range(1, num):
        if num % i == 0:
            sum  = i

    return sum


def buddy(start, limit):
    for i in range(start, limit   1):
        sum = sum_divisors(i)
        sum_minus_one = sum_divisors(sum - 1)

        if start > sum - 1:
            continue

        if i == (sum_minus_one - 1):
            return [i, sum - 1]

    return "Nothing"

uj5u.com熱心網友回復：

下面是一種根據一個數的質因數分解找到一個數的除數之和的快速方法：

from math import isqrt

def sum_of_divisors(n):
    result = 1
    div = 1
    while True:
        for div in range(div   1, isqrt(n)   1):
            if not n % div:
                mul = 1
                while not n % div:
                    n //= div
                    mul = 1   mul * div
                result *= mul
                break
        else:
            if n > 1:
                result *= 1   n
            return result

考慮例如 n=100。除數是質因數的乘積，例如除數 50 是 2×52。

最初已知的質因數：無 質因數的
可能乘積：只有值為 1 的空乘積
。這些乘積的總和：1

找到質因子 2（兩次）后：
可能的乘積：先前乘積乘以 2 ⁰、2 ¹或 2 ²。
乘積之和：前面的和乘以(1 2 4)，即1×7=7。

找到質因數 5（兩次）后：
可能的乘積：先前乘積乘以 5 ⁰、 5 ¹或 5 ²。
乘積之和：前面的和乘以(1 5 25)，即7×31=217。

如果你減去 n 本身，你會得到 117，這也是 1、2、4、5、10、20、25 和 50（任務描述中列出的適當除數串列）的總和。

我的buddy功能使用上述內容：

def buddy(start, limit):
    def s(n):
        return sum_of_divisors(n) - n
    for n in range(start, limit   1):
        m = s(n) - 1
        if m > n and s(m) == n   1:
            return [n, m]
    return 'Nothing'

在 Codewars 的最大案例中將我的與 gimix 進行比較buddy(145_809_719, 145_812_719)：

Kelly:  0.84 seconds
gimix: 10.57 seconds

你的需要大約 18 秒buddy(145_811_219, 145_811_219，這只是 3001 的中位數候選者。如果這是有代表性的，那么所有 3001 需要大約 15 小時。

uj5u.com熱心網友回復：

一些優化：

要找到除數的總和：

• 1 總是一個除數，所以只需計算它并從 2 開始回圈
• 只需回圈到 N 的平方根，并計算您找到的兩個除數（例如，4 是 100 的除數，所以100//4= 25 也是一個除數）；但記住避免計算平方根兩次

def divisors(n):
    divsum = 1
    for i in range(2,int(sqrt(n)) 1):
        d,m = divmod(n,i)
        if m == 0:
            divsum  = i
            if i != d:
                divsum  = n // i
    return divsum

尋找好友：

• 在計算第二個和之前檢查 N 的除數之start和是否小于（如果是continue）
• 還要檢查 N 的除數之和是否低于 M（如果continue是）

def buddy(start,limit):
    for i in range(start, limit 1):
        sum1 = divisors(i)
        if start > sum1-1 or i > sum1:
            continue
        sum_minus1 = divisors(sum1 - 1)
        if i == (sum_minus1 - 1):
            return [i, sum1 - 1]
    else:
        return "Nothing"

標籤：Python 算法

上一篇：找到通過頂點u和v的最小權重回路

下一篇：兩個騎士相遇的最少步數