C++에서 자연수 N의 k번째 최소 약수 찾기

이 문제에서는 두 개의 정수 값 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

또 다른 접근 방식

문제를 해결하는 또 다른 방법은 정렬된 두 개의 배열을 사용하는 것입니다.

하나의 저장 값 i, 오름차순으로 정렬됩니다.

기타 저장 값 N/i, 내림차순으로 정렬됨.

두 배열 중 하나에서 k번째로 작은 값을 찾습니다. k가 배열의 크기보다 크면 마지막 배열에서 두 번째 배열에 존재합니다.

그렇지 않으면 첫 번째 배열에 있습니다.

예시

솔루션 작동을 설명하는 프로그램

#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