PythonでNを1に減らす最大の操作を見つける

2つの数PとQがあり、それらが数N =（P！/ Q！）を形成するとします。可能な最大数の操作を実行して、Nを1に減らす必要があります。各操作で、NがXで割り切れる場合、NをN/Xに置き換えることができます。可能な最大数の操作を返します。

したがって、入力がA =7、B =4の場合、Nは210、除数は2、3、5、7であるため、出力は4になります。

これを解決するには、次の手順に従います-

• N：=1000005

• 因数：=サイズNの配列で、0で埋める

• メインの方法から、次のようにします-

• 2からNの範囲のiの場合、実行します

  • factor [i]が0と同じ場合、

    • iからNの範囲のjについては、各ステップでiずつ更新します。

      • ファクター[j]：=ファクター[j / i] + 1

• 1からNの範囲のiの場合、実行します

  • ファクター[i]：=ファクター[i]+ファクター[i-1];

• リターンファクター[a]-ファクター[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