หมายเลข Equidigital เป็นตัวเลขพิเศษทางคณิตศาสตร์ โดยจำนวนหลักในตัวเลขนั้นเท่ากับตัวเลขในการแยกตัวประกอบเฉพาะ
ในปัญหานี้ เราได้รับค่าจำนวนเต็ม n หน้าที่ของเราคือสร้างโปรแกรมสำหรับจำนวนเลขเท่ากันทั้งหมดไม่เกิน n
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: n =12
ผลลัพธ์:1 2 3 5 7 10 11
แนวทางการแก้ปัญหา:
วิธีแก้ปัญหาอย่างง่ายคือการหาตัวประกอบของตัวเลขและตรวจสอบว่าจำนวนเฉพาะเท่ากับจำนวนหลักในตัวเลขนั้นหรือไม่
สามารถหาปัจจัยเฉพาะได้โดยใช้วิธีตะแกรง
อัลกอริทึม:
ขั้นตอนที่ 1: หาจำนวนเฉพาะทั้งหมด
ขั้นตอนที่ 2: นับจำนวนหลักในจำนวน n.
ขั้นตอนที่ 3: หาตัวประกอบเฉพาะของตัวเลขทั้งหมดแล้วนับจำนวนหลักในจำนวนนั้น
ขั้นตอนที่ 4: เปรียบเทียบทั้งสองค่า
ขั้นตอนที่ 5: ส่งคืนหมายเลขหากเป็นจริง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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=j+2*i+1)
marked[j] = true;
primes.push_back(2);
for (int i=1; i<=MAX/2; i++)
if (marked[i] == false)
primes.push_back(2*i + 1);
}
bool isEquidigital(int n) {
if (n == 1)
return true;
int number = n;
int digitSum = 0;
while (number > 0)
{
digitSum++;
number = 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 = n/p;
expCount++;
}
while (p > 0) {
primeDigits++;
p = p / 10;
}
while (expCount > 1) {
primeDigits++;
expCount = expCount / 10;
}
}
if (n != 1)
{
while (n > 0)
{
primeDigits++;
n = 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
