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 khoảng [1, n].
Hãy xem ví dụ sau để hiểu bài toán:
Input : N = 7 Output : 1 2 2 3 2 4 2
Phương pháp giải
Một giải pháp đơn giản là bắt đầu từ 1 đến N và với mỗi số đếm số ước và in ra.
Ví dụ 1
Chương trình minh họa cho giải pháp
#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; }Kết quả
The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4
Một phương pháp khác để giải bài toán là sử dụng tăng giá trị. Ta tạo mảng kích thước (N+1). Sau đó, từ 1 đến N, với mỗi giá trị i, ta tăng giá trị mảng cho tất cả bội của i nhỏ hơn n.
Ví dụ 2
Chương trình minh họa cho giải pháp,
#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; }Kết quả
The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4