이 문제에서 양의 정수 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