সি++-এ প্রাইম অঙ্ক দিয়ে বনানো দত্ত সংখ্যা চেয়ে ছোট সর্ববৃহৎ সংখ্যা

একটি সংখ্যা n দেওয়া থাকলে, শুধু প্রাইম অঙ্ক (২, ৩, ৫, ৭) ব্যবহার করে n চেয়ে ছোট সবচেয়ে বড় সংখ্যা বের করতে হবে।

উদাহরণ

ইনপুট: 7464 → আউটপুট: 7377

অ্যালগরিদম

স্ট্রিং হিসেবে প্রসেস করুন।
বাম থেকে ডানে যান: প্রথম অ-প্রাইম অঙ্ক পাওয়া গেলে, সেটির বাম পাশে যান।
সেটিকে আগের প্রাইম অঙ্কে নামিয়ে দিন (৭→৫, ৫→৩, ৩→২, ২→০ হলে মুছে দিন)।
পরে বাকি সব অঙ্ক ৭ দিয়ে পূরণ করুন।

সি++ ইমপ্লিমেন্টেশন

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

bool isPrimeDigit(char c) {
    return c=='2' || c=='3' || c=='5' || c=='7';
}

void decrease(string& s, int i) {
    if (s[i] <= '2') { s.erase(i,1); s[i] = '7'; }
    else if (s[i] == '3') s[i] = '2';
    else if (s[i] <= '5') s[i] = '3';
    else if (s[i] <= '7') s[i] = '5';
    else s[i] = '7';
}

string getLargestPrimeDigitNumber(string n) {
    for (int i = 0; i < n.length(); i++) {
        if (!isPrimeDigit(n[i])) {
            while (i >= 0 && n[i] <= '2') i--;
            if (i < 0) i = 0;
            decrease(n, i);
            for (int j = i + 1; j < n.length(); j++) n[j] = '7';
            break;
        }
    }
    return n;
}

int main() {
    string n = "7464";
    cout << getLargestPrimeDigitNumber(n) << endl; // 7377
    return 0;
}