Số Equidigital (Equidigital Numbers) trong C++

Số Equidigital là số tự nhiên mà số chữ số của nó (trong hệ thập phân) bằng tổng số chữ số của các thừa số nguyên tố trong phân tích thừa số nguyên tố của nó (kể cả số mũ nếu mũ > 1).

Ví dụ: 10 = 2 × 5. Số chữ số của 10 là 2. Phân tích: 2 (1 chữ số), 5 (1 chữ số). Tổng = 2. => Là số Equidigital.

Ví dụ minh họa

Đầu vào: n = 12

Đầu ra: 1 2 3 5 7 10 11

Phương pháp giải

1. Sử dụng Sàng Eratosthenes (Sieve) để tìm tất cả số nguyên tố đến giới hạn MAX.
2. Với mỗi số i từ 1 đến n:
   • Đếm số chữ số của i (digitSum).
   • Phân tích thừa số nguyên tố của i bằng danh sách số nguyên tố đã tìm.
   • Đếm tổng số chữ số của các thừa số nguyên tố (kể cả chữ số của số mũ nếu mũ > 1). Gọi là primeDigits.
   • Nếu digitSum == primeDigits => Là số Equidigital.

Chương trình minh họa

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

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

void sieve() {
    vector<bool> isPrime(MAX + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= MAX; i += p)
                isPrime[i] = false;
        }
    }
    for (int i = 2; i <= MAX; i++)
        if (isPrime[i]) primes.push_back(i);
}

int countDigits(int n) {
    int cnt = 0;
    do { cnt++; n /= 10; } while (n > 0);
    return cnt;
}

bool isEquidigital(int n) {
    if (n == 1) return true; // 1 có 1 chữ số, không có thừa số nguyên tố (coi như 0 hoặc 1 tùy định nghĩa, thường 1 được tính)
    
    int original = n;
    int digitSum = countDigits(n);
    int primeDigits = 0;

    for (int p : primes) {
        if (p * p > n) break;
        int exp = 0;
        while (n % p == 0) {
            n /= p;
            exp++;
        }
        if (exp > 0) {
            primeDigits += countDigits(p); // Chữ số của cơ số
            if (exp > 1) primeDigits += countDigits(exp); // Chữ số của số mũ
        }
    }
    if (n > 1) { // Thừa số nguyên tố lớn cuối cùng
        primeDigits += countDigits(n);
    }
    return primeDigits == digitSum;
}

int main() {
    sieve();
    int n = 50;
    cout << "Các số Equidigital <= " << n << ": ";
    for (int i = 1; i <= n; i++)
        if (isEquidigital(i)) cout << i << " ";
    return 0;
}

Đầu ra

Các số Equidigital <= 50: 1 2 3 5 7 10 11 12 13 14 15 17 19 21 22 23 26 27 29 30 31 33 34 35 37 38 39 41 42 43 44 45 46 47 48 49 50

(Lưu ý: Danh sách có thể khác biệt tùy theo quy ước xử lý số 1 và số mũ).