Tìm số ước của tất cả các số trong phạm vi [1, n] trong C ++

Trong bài toán này, chúng ta được cho một số N. Nhiệm vụ của chúng ta là tìm số ước của tất cả các số trong phạm vi [1, n].

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là bắt đầu từ 1 đến N và với mọi số, hãy đếm số ước và in ra.

Ví dụ 1

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

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

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng gia số của các giá trị. Đối với điều này, chúng tôi sẽ tạo một mảng có kích thước (N + 1). Sau đó, bắt đầu từ 1 đến N, chúng ta sẽ kiểm tra từng giá trị i, chúng ta sẽ tăng giá trị mảng cho tất cả các bội số của i nhỏ hơn n.

Ví dụ 2

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

#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;
}

Đầu ra

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