Frugal Number: ตรวจสอบเลขประหยัดใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวก N งานของเราคือตรวจสอบว่า N เป็น Frugal Number หรือไม่

Frugal Number คืออะไร?

ตัวเลขที่จำนวนหลัก (digits) ของมัน มากกว่า จำนวนหลักในการแยกตัวประกอบเฉพาะ (prime factorization) อย่างเคร่งครัด

ตัวอย่าง

625 → ตัวประกอบเฉพาะ = 5⁴

• หลักของ 625 = 3 หลัก
• หลักของ 5⁴ = 2 หลัก (5 และ 4)
• 3 > 2 → เป็น Frugal Number

Frugal Numbers แรกๆ: 125, 128, 243, 256, 343, 512, 625, ...

ตัวอย่างเพื่อเข้าใจปัญหา

Input: n = 128 Output: Frugal number

128 = 2⁷ → หลักของ 128 = 3, หลักของ 2⁷ = 2 → 3 > 2 ✓

วิธีการแก้ปัญหา

1. หาตัวประกอบเฉพาะทั้งหมดของ n (Sieve of Eratosthenes)
2. แยกตัวประกอบ n และนับจำนวนหลักใน factorization
3. เปรียบเทียบกับจำนวนหลักของ n

ตัวอย่างโค้ด

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

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

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

bool isFrugalNum(long n) {
    vector primes = calcPrimeNum(n);
    long num = n, factorDigits = 0;
    
    for (long p : primes) {
        if (num % p == 0) {
            int k = 0;
            while (num % p == 0) { num /= p; k++; }
            factorDigits += countDigits(p);
            if (k > 1) factorDigits += countDigits(k);
        }
    }
    return (countDigits(n) > factorDigits && factorDigits != 0);
}

int main() {
    long n = 625;
    cout << n << (isFrugalNum(n) ? " is a Frugal number" : " is not a Frugal number");
    return 0;
}

ผลลัพธ์

625 is a Frugal number