C++에서 [1, n] 범위에 있는 모든 숫자의 약수 찾기

이 문제에서는 숫자 N이 주어집니다. 우리의 임무는 [1, n] 범위에 있는 모든 숫자의 약수를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

Input : N = 7
Output : 1 2 2 3 2 4 2

솔루션 접근 방식

문제에 대한 간단한 해결책은 1에서 N까지 시작하여 모든 숫자에 대해 제수를 세고 인쇄하는 것입니다.

예시 1

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

#include <iostream>
using namespace std;
int countDivisor(int N){
   int count = 1;
   for(int i = 2; i <= N; i++){
      if(N%i == 0)
         count++;
   }
   return count;
}
int main(){
   int N = 8;
   cout<<"The number of divisors of all numbers in the range are \t";
   cout<<"1 ";
   for(int i = 2; i <= N; i++){
      cout<<countDivisor(i)<<" ";
   }
   return 0;
}

출력

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4

문제를 해결하는 또 다른 방법은 값의 증분을 사용하는 것입니다. 이를 위해 크기(N+1)의 배열을 생성합니다. 그런 다음 1부터 N까지 각 값 i를 확인하고 n보다 작은 i의 모든 배수에 대해 배열 값을 증가시킵니다.

예시 2

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

#include <iostream>
using namespace std;
void countDivisors(int N){
   int arr[N+1];
   for(int i = 0; i <= N; i++)
      arr[i] = 1;
      for (int i = 2; i <= N; i++) {
         for (int j = 1; j * i <= N; j++)
            arr[i * j]++;
      }
      for (int i = 1; i <= N; i++)
         cout<<arr[i]<<" ";
}
int main(){
   int N = 8;
   cout<<"The number of divisors of all numbers in the range are \t"; countDivisors(N);
   return 0;
}

출력

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4