เลข Equidigital ใน C++

ปัญหา

เลข Equidigital คือจำนวนที่จำนวนหลักของมัน เท่ากับจำนวนหลักในการแยกตัวประกอบเฉพาะ (Prime Factorization) ของมัน

ได้รับจำนวน n ต้องพิมพ์เลข Equidigital ทั้งหมดที่น้อยกว่าหรือเท่ากับ n

ตัวอย่าง

อินพุต: n = 12

เอาต์พุต: 1 2 3 5 7 10 11

แนวทางแก้ปัญหา

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

โปรแกรมตัวอย่าง

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

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

void findAllPrimes() {
    bool marked[MAX/2 + 1] = {0};
    for (int i = 1; i*i <= (MAX-1)/2; i++)
        for (int j = (i*(i+1))<<1; j <= MAX/2; j += 2*i+1)
            marked[j] = true;
    primes.push_back(2);
    for (int i = 1; i <= MAX/2; i++)
        if (!marked[i]) primes.push_back(2*i + 1);
}

bool isEquidigital(int n) {
    if (n == 1) return true;
    int number = n, digitSum = 0;
    while (number > 0) { digitSum++; number /= 10; }
    
    int primeDigits = 0, expCount = 0, p;
    for (int i = 0; primes[i] <= n/2; i++) {
        while (n % primes[i] == 0) {
            p = primes[i];
            n /= p;
            expCount++;
        }
        while (p > 0) { primeDigits++; p /= 10; }
        while (expCount > 1) { primeDigits++; expCount /= 10; }
    }
    if (n != 1) {
        while (n > 0) { primeDigits++; n /= 10; }
    }
    return (primeDigits == digitSum);
}

int main() {
    findAllPrimes();
    int n = 11;
    cout << "Printing Equidigital Numbers less than " << n << " : ";
    for (int i = 1; i < n; i++)
        if (isEquidigital(i)) cout << i << "\t";
    return 0;
}

ผลลัพธ์

Printing Equidigital Numbers less than 11 : 1 2 3 5 7 10 11