একটি সংখ্যা n দেওয়া আছে; কাজ হল সেই সংখ্যার মবিয়াস ফাংশন মান নির্ণয় করা।
মবিয়াস ফাংশন কী?
মবিয়াস ফাংশন হল একটি সংখ্যা তত্ত্ব ফাংশন যা নিচের মত definiert করা হয়েছে:
μ(n) = 0, যদি n-এ এক বা একাধিক পুনরাবৃত্ত প্রাইম ফ্যাক্টর থাকে
μ(n) = 1, যদি n = 1 হয়
μ(n) = (-1)ᵏ, যদি n হল k টি ভিন্ন প্রাইম সংখ্যার গুণফল
উদাহরণ
ইনপুট: N = 17 আউটপুট: -1 ব্যাখ্যা: প্রাইম ফ্যাক্টর: 17, k = 1, (-1)ᵏ = (-1)¹ = -1 ইনপুট: N = 6 আউটপুট: 1 ব্যাখ্যা: প্রাইম ফ্যাক্টর: 2 এবং 3, k = 2, (-1)² = 1 ইনপুট: N = 25 আউটপুট: 0 ব্যাখ্যা: প্রাইম ফ্যাক্টর ৫ দুবার আছে, তাই উত্তর ০
সমাধানের পদ্ধতি
- ইনপুট N নিন।
- ১ থেকে N পর্যন্ত ইটারেট করে N-এর ভাজ্য সংখ্যাগুলো চেক করুন এবং সেগুলো প্রাইম কিনা তা যাচাই করুন।
- যদি দুটি শর্ত পূরণ হয়, তবে চেক করুন যে সংখ্যার বর্গও N কে ভাগ করে কিনা। যদি হয় তবে ০ রিটার্ন করুন।
- অন্যথায় প্রাইম ফ্যাক্টরের কাউন্ট বাড়ান। যদি কাউন্ট জোড় হয় তবে ১, বিজোড় হলে -১ রিটার্ন করুন।
- ফলাফল প্রিন্ট করুন।
অ্যালগরিদম
Start
Step 1→ ফাংশন bool isPrime(int n) এ
i ডিক্লেয়ার করুন
If n < 2 হয় Return false
For i = 2; i * i <= n; i++ লুপ
If n % i == 0 হয় Return false
Return true
Step 2→ ফাংশন int mobius(int N) এ
i এবং p = 0 ডিক্লেয়ার করুন
If N == 1 হয় Return 1
For i = 1; i <= N; i++ লুপ
If N % i == 0 && isPrime(i) হয়
If N % (i * i) == 0 হয় Return 0
Else p বাড়ান
Return (p % 2 != 0) ? -1 : 1
Step 3→ ফাংশন int main() এ
N = 17 ডিক্লেয়ার ও সেট করুন
mobius(N) থেকে ফলাফল প্রিন্ট করুন
Stop
সি++ কোড উদাহরণ
#include <iostream>
using namespace std;
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
int mobius(int N) {
int p = 0;
if (N == 1) return 1;
for (int i = 2; i <= N; i++) {
if (N % i == 0 && isPrime(i)) {
if (N % (i * i) == 0)
return 0;
else
p++;
}
}
return (p % 2 != 0) ? -1 : 1;
}
int main() {
int N = 17;
cout << mobius(N) << endl;
return 0;
}
আউটপুট
-1
