সমস্যা বিবরণ
একটি ধনাত্মক পূর্ণসংখ্যা N দেওয়া হয়েছে। আমাদের কাজ হল N কি Frugal সংখ্যা কিনা তা যাচাই করা।
Frugal সংখ্যা: যে সংখ্যার অঙ্কের সংখ্যা তার质因数分解-এ উপস্থিত অঙ্কের সংখ্যা থেকে স্ট্রিক্টলি বড়।
উদাহরণ
ইনপুট: n = 128 আউটপুট: Frugal number ব্যাখ্যা: 128 = 2⁷, অঙ্ক ৩টি। ফ্যাক্টরাইজেশনে অঙ্ক ২টি (2, 7)। ৩ > ২, তাই Frugal।
প্রথম কিছু Frugal সংখ্যা
125, 128, 243, 256, 343, 512, 625, ইত্যাদি।
সমাধানের পদ্ধতি
প্রাইম ফ্যাক্টরাইজেশন করে ফ্যাক্টরের অঙ্ক গণনা করা এবং মূল সংখ্যার অঙ্কের সাথে তুলনা করা।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
vector<long int> calcPrimeNum(long int n) {
vector<bool> isPrime(n+1, true);
for (int i=2; i*i<=n; i++)
if (isPrime[i])
for (int j=i*2; j<=n; j+=i) isPrime[j]=false;
vector<long int> primes;
for (int i=2; i<n; i++) if (isPrime[i]) primes.push_back(i);
return primes;
}
int countDigits(long int n) {
int cnt=0;
while(n){ n/=10; cnt++; }
return cnt;
}
bool isFrugalNum(long int n) {
auto primes = calcPrimeNum(n);
long int num=n, factorDigits=0;
for (long int p: primes) {
if (num%p==0) {
int k=0;
while(num%p==0){ num/=p; k++; }
factorDigits += countDigits(p);
if (k>1) factorDigits += countDigits(k);
}
}
return (countDigits(n) > factorDigits && factorDigits != 0);
}
int main() {
long int n = 625;
cout << n << (isFrugalNum(n) ? " is a Frugal number" : " is not a Frugal number");
return 0;
}
আউটপুট
625 is a Frugal number
