Số Frugal (Số tiết kiệm) trong C++

Trong bài toán này, chúng ta được cho số nguyên dương N. Nhiệm vụ là kiểm tra xem số đó có phải là số Frugal hay không.

Định nghĩa số Frugal

Số có số chữ số lớn hơn chặt số chữ số trong phân tích thừa số nguyên tố của nó.

Ví dụ

625 = 5⁴. Số chữ số của 625 là 3. Số chữ số của 5⁴ là 2. 3 > 2 → 625 là số Frugal.

Các số Frugal đầu tiên: 125, 128, 243, 256, 343, 512, 625...

Ví dụ minh họa

Input: n = 128 Output: Frugal number
Giải thích: 128 = 2^7 (2 chữ số), 128 có 3 chữ số. 3 > 2 → Frugal.

Phương pháp giải

Tìm thừa số nguyên tố của n, đếm số chữ số trong phân tích thừa số (kể cả số mũ > 1). So sánh với số chữ số của n.

Ví dụ chương trình

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

vector<long int> calcPrimeNum(long int n){
    vector<bool> primeNos(n + 1, true);
    for (int i = 2; i * i <= n; i++) {
        if (primeNos[i]) {
            for (int j = i * 2; j <= n; j += i)
                primeNos[j] = false;
        }
    }
    vector<long int> allPrimeNumbers;
    for (int i = 2; i < n; i++) if (primeNos[i]) allPrimeNumbers.push_back(i);
    return allPrimeNumbers;
}

int countNumDigits(long int n){
    int digitCount = 0;
    while (n != 0) { n /= 10; digitCount++; }
    return digitCount;
}

bool isFrugalNum(long int n){
    vector<long int> primeNum = calcPrimeNum(n);
    long int num = n;
    long int factorDigitCount = 0;
    for (int i = 0; i < primeNum.size(); i++) {
        if (num % primeNum[i] == 0) {
            long int k = 0;
            while (num % primeNum[i] == 0) { num /= primeNum[i]; k++; }
            if (k == 1) factorDigitCount += countNumDigits(primeNum[i]);
            else factorDigitCount += countNumDigits(primeNum[i]) + countNumDigits(k);
        }
    }
    return (countNumDigits(n) > factorDigitCount && factorDigitCount != 0);
}

int main(){
    long int n = 625;
    cout << "Số " << n << (isFrugalNum(n) ? " là số Frugal" : " không phải số Frugal");
    return 0;
}

Kết quả

Số 625 là số Frugal