Pythonを使用してnのk番目の因子を見つけるプログラム

2つの正の値nとkがあるとします。ここで、nのすべての因子のリストが昇順でソートされていると考えて、このリストでk番目の因子を見つける必要があります。 k未満の因子がある場合は、-1を返します。

したがって、入力がn =28 k =4の場合、28の因数は[1,2,4,7,14,28]であり、4番目の因数は7であるため、出力は7になります。

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

• kが1と同じ場合、

  • 1を返す

• cand：=1つの要素を持つリスト[1]

• 2から1の範囲のi+（nの平方根）のフロアの場合、実行

  • n mod iが0と同じ場合、

    • candの最後にiを挿入します

  • m：=カンドのサイズ

• k> 2 * mまたは（kは2 *mおよびn=（カンドの最後の要素）^ 2と同じ）

  の場合

  • -1を返す

• k <=mの場合、

  • cand [k-1]

    を返す

• factor：=cand [2 * m --k]

• n/factorの商を返す

理解を深めるために、次の実装を見てみましょう-

例

from math import floor
def solve(n ,k):
   if k == 1:
      return 1
   cand = [1]
   for i in range(2, 1+floor(pow(n, 0.5))):
      if n%i == 0:
         cand.append(i)
      m = len(cand)
      if k > 2*m or (k == 2*m and n == cand[-1]**2):
         return -1
      if k <= m:
         return cand[k-1]
      factor = cand[2*m - k]
      return n//factor
n = 28
k = 4
print(solve(n ,k))

入力

28, 4

出力

7