Số lớn nhất < N chỉ chứa chữ số nguyên tố C++

Cho số N (chuỗi). Tìm số lớn nhất < N chỉ chứa các chữ số nguyên tố {2,3,5,7}.

Thuật toán

• Duyệt chữ số từ trái sang phải.
• Gặp chữ số không phải {2,3,5,7}:
  • Giảm chữ số đó xuống chữ số nguyên tố gần nhất nhỏ hơn.
  • Điền tất cả chữ số sau bằng 7 (lớn nhất).
  • Nếu chữ số đó ≤ 2: phải quay lui (borrow) sang trái.

Triển khai C++

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

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

char prevPrimeDigit(char c) {
    if (c > '7') return '7';
    if (c > '5') return '5';
    if (c > '3') return '3';
    if (c > '2') return '2';
    return '0'; // cần borrow
}

string largestPrimeDigits(string s) {
    int n = s.size();
    for (int i = 0; i < n; i++) {
        if (!isPrimeDigit(s[i])) {
            // giảm tại i
            int j = i;
            while (j >= 0) {
                char np = prevPrimeDigit(s[j]);
                if (np != '0') {
                    s[j] = np;
                    for (int k = j+1; k < n; k++) s[k] = '7';
                    // bỏ leading zero
                    int pos = 0; while (pos < n && s[pos]=='0') pos++;
                    return pos==n ? "0" : s.substr(pos);
                }
                j--;
            }
            return "0"; // không tìm thấy
        }
    }
    return s; // N đã chỉ có chữ số nguyên tố
}

int main() {
    cout << largestPrimeDigits("7464") << endl; // 7377
    return 0;
}

Kết quả

7377