সি++-এ ইকুইডিজিটাল নম্বর

ইকুইডিজিটাল নম্বর হলো গাণিতিকভাবে বিশেষ সংখ্যা যেখানে সংখ্যার অঙ্কের সংখ্যা এর প্রাইম ফ্যাক্টরাইজেশনে থাকা অঙ্কের সংখ্যার সমান।

এই সমস্যায় আমাদের একটি পূর্ণসংখ্যা n দেওয়া হয়েছে। আমাদের কাজ হলো n পর্যন্ত সব ইকুইডিজিটাল নম্বর বের করার প্রোগ্রাম তৈরি করা।

উদাহরণ দিয়ে বুঝি

ইনপুট: n = 12

আউটপুট:  ১ ২ ৩ ৫ ৭ ১০ ১১

সমাধানের পদ্ধতি

সমস্যার একটি সহজ সমাধান হলো সংখ্যার ফ্যাক্টর বের করে চেক করা যে প্রাইমের সংখ্যা সংখ্যার অঙ্কের সংখ্যার সমান কিনা। প্রাইম ফ্যাক্টরগুলো সিভ মেথড ব্যবহার করে বের করা যায়।

অ্যালগরিদম:

ধাপ ১: সব প্রাইম নম্বর বের করুন।
ধাপ ২: সংখ্যা n-এর অঙ্কের সংখ্যা গণনা করুন।
ধাপ ৩: সংখ্যার সব প্রাইম ফ্যাক্টর বের করুন এবং সেখানে অঙ্কের সংখ্যা গণনা করুন।
ধাপ ৪: উভয় মান তুলনা করুন।
ধাপ ৫: যদি সত্য হয় তবে সংখ্যাটি ফেরত দিন।

সমাধান minhaj করার প্রোগ্রাম

#include<bits/stdc++.h> 
using namespace std; 

const int MAX = 10000; 
vector <int> primes; 

void findAllPrimes() { 
    bool marked[MAX/2 + 1] = {0}; 
    for (int i=1; i*i<= (MAX -1)/2; i++) 
        for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1) 
            marked[j] = true; 
    primes.push_back(2); 
    for (int i=1; i<=MAX/2; i++) 
        if (marked[i] == false) 
            primes.push_back(2*i + 1); 
} 

bool isEquidigital(int n) { 
    if (n == 1) 
        return true; 
    int number = n; 
    int digitSum = 0; 
    while (number > 0) { 
        digitSum++; 
        number = number/10; 
    } 
    int primeDigits = 0 , expCount = 0, p; 
    for (int i = 0; primes[i] <= n/2; i++) { 
        while (n % primes[i] == 0) { 
            p = primes[i]; 
            n = n/p; 
            expCount++; 
        } 
        while (p > 0) { 
            primeDigits++; 
            p = p / 10; 
        } 
        while (expCount > 1) { 
            primeDigits++; 
            expCount = expCount / 10; 
        } 
    } 
    if (n != 1) { 
        while (n > 0) { 
            primeDigits++; 
            n = n/10; 
        } 
    } 
    return (primeDigits == digitSum); 
} 

int main() { 
    findAllPrimes(); 
    int n = 11; 
    cout << "Printing Equidigital Numbers less than " << n << " : "; 
    for (int i=1; i<n; i++) 
        if (isEquidigital(i)) 
            cout << i << "\t"; 
    return 0; 
}

আউটপুট

Printing Equidigital Numbers less than 11 : 1 2 3 5 7 10 11