ในปัญหานี้ เราได้รับจำนวนเต็มบวก N หน้าที่ของเราคือสร้างโปรแกรมเพื่อตรวจสอบว่าตัวเลขที่ระบุนั้นเป็น ตัวเลขประหยัดหรือไม่
ตัวเลขประหยัด − จำนวนที่มีจำนวนหลักมากกว่าจำนวนหลักในการแยกตัวประกอบเฉพาะของตัวเลขที่ระบุอย่างเคร่งครัด
ตัวอย่าง − 625 ตัวประกอบเฉพาะของจำนวน 625 คือ 5 4 .
จำนวนหลักใน 625 คือ 3
จำนวนหลักใน 5 4 คือ 2.
3 มากกว่า 2 อย่างเคร่งครัด ดังนั้น 625 จึงเป็นจำนวนที่ประหยัด
ตัวเลขประหยัดสองสามตัวแรกคือ − 125, 128, 243, 256, 343, 512, 625 เป็นต้น
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input: n = 128 Output: Frugal number Explanation : Factors of 128 are 2^7, number of digits 2. The number of digits in 128 is 3. The number is a frugal number.
แนวทางการแก้ปัญหา
วิธีแก้ไขปัญหาหนึ่งคือการตรวจสอบว่าหมายเลขปัจจุบัน n เป็นตัวเลขที่ประหยัดหรือไม่ สำหรับสิ่งนี้ เราจะหาตัวประกอบเฉพาะของ n และนับจำนวนหลักในการแยกตัวประกอบแล้วนับจำนวนหลักในตัวเลข หากจำนวนหลักในตัวเลขมากกว่าจำนวนตัวประกอบ ตัวเลขนั้นเป็นตัวเลขที่ประหยัด ไม่เช่นนั้นจะไม่ใช่
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include <bits/stdc++.h>
using namespace std;
vector<long int> calcPrimeNum(long int n){
bool primeNos[n + 1];
memset(primeNos, true, sizeof(primeNos));
for (int i = 2; i * i <= n; i++) {
if (primeNos[i] == true) {
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){
long long int num = n;
int digitCount = 0;
while (num != 0) {
num = num / 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 = num / primeNum[i];
k++;
}
if (k == 1)
factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]);
else if (k != 1)
factorDigitCount = factorDigitCount + countNumDigits(primeNum[i]) + countNumDigits(k);
}
}
return (countNumDigits(n) > factorDigitCount && factorDigitCount != 0);
}
int main(){
long int n = 625;
cout<<"The number "<<n<<" is ";isFrugalNum(n)? cout<<"a Frugal number\n" : cout << "not a Frugal number\n";
return 0;
} ผลลัพธ์
The number 625 is a Frugal number
