এই সমস্যায়, আমাদের একটি সংখ্যা N দেওয়া আছে। আমাদের কাজ হল [1, n] রেঞ্জের সব সংখ্যার ভাজকের সংখ্যা বের করা।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : N = 7 আউটপুট : 1 2 2 3 2 4 2
সমাধানের পদ্ধতি
এই সমস্যার একটি সহজ সমাধান হল ১ থেকে N পর্যন্ত শুরু করা এবং প্রতিটি সংখ্যার জন্য ভাজকের সংখ্যা গুনে প্রিন্ট করা।
উদাহরণ ১
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#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) আকারের একটি অ্যারে তৈরি করব। তারপর ১ থেকে N পর্যন্ত, প্রতিটি মান i-এর জন্য, i-এর সব গুণিতক যেগুলো n-র চেয়ে ছোট, তাদের জন্য অ্যারে ভ্যালু ইনক্রিমেন্ট করব।
উদাহরণ ২ (অপ্টিমাইজড পদ্ধতি)
আমাদের সমাধানের কাজকাণ্ড ব্যাখ্যা করার প্রোগ্রাম:
#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
