আমাদের একটি ধনাত্মক ইন্টিজার N দেওয়া আছে। লক্ষ্য হল N-কে ০ করার জন্য কতটি অপারেশন লাগবে। প্রতিটি অপারেশনে N = N - P করা হয়, যেখানে P হল N-এর ন্যূনতম প্রাইম ভাজক (smallest prime divisor)।
উদাহরণ
ইনপুট: N = 17
আউটপুট: ১
ব্যাখ্যা: ১৭ প্রাইম, তাই ন্যূনতম প্রাইম ভাজক ১৭। একবার বিয়োগে ০।
ইনপুট: N = 20
আউটপুট: ১০
ব্যাখ্যা: ন্যূনতম প্রাইম ভাজক ২। বারবার ২ বিয়োগ করলে: ২০→১৮→১৬→...→২→০। মোট ১০ বার।
অ্যালগরিদম
- সব জোড়
N-এর ন্যূনতম প্রাইম ভাজক ২। ২ বিয়োগ করলে আবার জোড় হয়। - বিজোড়
N-এর ন্যূনতম প্রাইম ভাজক বিজোড়। বিজোড় থেকে বিজোড় বিয়োগ করলে জোড় হয়, এরপর ২-দিয়ে চলে। i=2থেকেi*i <= Nপর্যন্ত চেক করুনN%i==0। পাওয়া গেলে সেটিই ন্যূনতম প্রাইম ভাজক।- পাওয়া না গেলে
Nপ্রাইম, তাইi = N। - মোট অপারেশন =
1 + (N - i) / 2।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
int N_to_Zero(int N) {
int i = 2;
while ((i * i) <= N && (N % i)) {
i++;
}
if ((i * i) > N) i = N;
return 1 + (N - i) / 2;
}
int main() {
int N = 10;
cout << "Count of operations of the given type required to reduce N to 0 are: "
<< N_to_Zero(N);
return 0;
}
আউটপুট
Count of operations of the given type required to reduce N to 0 are: 5
