C++で自然数Nのk番目に小さい約数を見つけます

この問題では、2つの整数値Nとkが与えられます。私たちの仕事は、自然数Nのk番目に小さい約数を見つけることです。 。

問題を理解するために例を見てみましょう

Input : N = 15, k = 3
Output : 5

説明 −

Factors of 15 are 1, 3, 5, 15
3rd smallest is 5

ソリューションアプローチ

この問題の簡単な解決策は、数値の因数を見つけて並べ替えて保存し、k番目の値を出力することです。

ソートでは、root（N）までループし、Nがiで割り切れるかどうかを確認します。そして、iと（N / i）の値を配列に格納し、それをソートします。このソートされた配列から、k番目の値を出力します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
   int factors[n/2];
   int j = 0;
   for (int i = 1; i <= sqrt(n); i++) {
      if (n % i == 0) {
         factors[j] = i;
         j++;
         if (i != sqrt(n)){
            factors[j] = n/i;
            j++;
         }
      }
   }
   sort(factors, factors + j);
   if (k > j)
      cout<<"Doesn't Exist";
   else
      cout<<factors[k-1];
}
int main(){
   int N = 16,
   k = 3;
   cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
   findFactorK(N, k);
   return 0;
}

出力

3-th smallest divisor of the number 16 is 4

別のアプローチ

この問題を解決する別のアプローチは、ソートされた2つの配列を使用することです。

値iを格納し、昇順で並べ替えたもの。

その他の保存値N/i、降順でソート。

2つの配列のいずれかからk番目に小さい値が見つかります。 kが配列のサイズより大きい場合、最後から2番目の配列に存在します。

それ以外の場合は、最初の配列に存在します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
void findFactorK(int n, int k){
   int factors1[n/2];
   int factors2[n/2];
   int f1 = 0,f2 = 0;
   for (int i = 1; i <= sqrt(n); i++) {
      if (n % i == 0) {
         factors1[f1] = i;
         f1++;
         if (i != sqrt(n)){
            factors2[f2] = n/i;
            f2++;
         }
      }
   }
   if (k > (f1 + f2))
      cout<<"Doesn't Exist";
   else{
      if(k <= f1)
         cout<<factors1[f1-1];
      else
         cout<<factors2[k - f2 - 1];
   }
}
int main(){
   int N = 16,
   k = 3;
   cout<<k<<"-th smallest divisor of the number "<<N<<" is ";
   findFactorK(N, k);
   return 0;
}

出力

3-th smallest divisor of the number 16 is 4