在Python中查詢將N減少到1的最大操作次數

假設我們有兩個數字P和Q，它們構成一個數字N = (P!/Q!)。我們必須透過執行儘可能多的操作來將N減少到1。在每次操作中，當N可被X整除時，可以將N替換為N/X。我們將返回可能的最大操作次數。

因此，如果輸入類似於A = 7，B = 4，則輸出將為4，因為N為210，除數為2、3、5、7。

為了解決這個問題，我們將遵循以下步驟：

  • N := 1000005

  • factors := 一個大小為N的陣列，並填充0

  • 從主方法中執行以下操作：

  • 對於範圍從2到N的i，執行

    • 如果factors[i]等於0，則

      • 對於範圍從i到N的j，每次遞增i，執行

        • factors[j] := factors[j / i] + 1

  • 對於範圍從1到N的i，執行

    • factors[i] := factors[i] + factors[i - 1];

  • 返回factors[a] - factors[b]

示例

讓我們看看下面的實現，以便更好地理解：

 線上演示

N = 1000005
factors = [0] * N;
def get_prime_facts() :
   for i in range(2, N) :
      if (factors[i] == 0) :
         for j in range(i, N, i) :
            factors[j] = factors[j // i] + 1
   for i in range(1, N) :
      factors[i] += factors[i - 1];
get_prime_facts();
a = 7; b = 4;
print(factors[a] - factors[b])

輸入

7,4

輸出

4

更新於：2020年8月25日

193 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始
廣告