資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究欺詐數
問題陳述包括檢查給定的數字 N（這將是使用者輸入）是否為欺詐數。
欺詐數是一個合數，其不同質因數的數字和等於合數本身的數字和。由於 1 不是質數，因此我們不將 1 視為不同質數的數字和。如果一個質數是合數的因數超過一次，則在取質因數的數字和時只考慮一次。
在這個問題中，我們將得到一個大於 1 的正整數，我們的任務是檢查提供的數字是否為欺詐數。我們將檢查一個數成為欺詐數的條件，如果該數滿足所有條件，則它是一個欺詐數。
讓我們透過以下示例瞭解問題。
輸入
N= 18
輸出
No
解釋− 給定數字 18 的質因數分解為 2*3*3。不同的質因數為 2 和 3，其數字和為 2+3=5。
給定數字的數字和為 1+8=9。由於數字的數字和不等於不同質數的數字和，因此給定數字不是欺詐數。
輸入
N=58
輸出
Yes
解釋− 輸入中的給定數字為 58，其質因數分解為 2*29。該數字的不同質因數的數字和為 2+2+9=13，給定數字的數字和為 5+8=13。由於和相等，因此給定數字是欺詐數，因為它滿足成為欺詐數的所有條件。
輸入
N=19
輸出
No
解釋− 輸入中給定的數字為 19。欺詐數始終為合數，但此處 19 為質數，因此 19 不是欺詐數。
讓我們瞭解透過檢查一個數成為欺詐數的條件來檢查該數是否為欺詐數的演算法。
演算法
對於一個數成為欺詐數，該數的數字和必須等於其不同質因數的數字和。我們將簡單地計算該數的所有不同質因數以獲得不同質因數的數字和。
計算一個數的不同質因數
我們將建立一個函式，該函式返回包含該數的不同質因數的向量。為了儲存該數的所有不同質因數，我們將遵循以下步驟
如果該數可被 2 整除，我們將用 2 除以該數，直到它成為奇數，並將 2 儲存在向量中。
到目前為止，N 必須是奇數，因此我們將從 i=3 到 i<=sqrt(N) 迭代僅針對奇數的 for 迴圈。
現在，如果 N 可被 i 整除，則繼續用 i 除以 N，直到餘數等於零，然後將 i 的值儲存在向量中。
每次 N 可被 i 整除時更新 N 的值。
如果 N 是質數且大於 2，則它不能透過上述步驟變為 1，因此我們將使用 if 語句檢查 N 的值，如果它大於 2，則將該值儲存在向量中。
按照這些步驟，我們將獲得給定數字的不同質因數。該數字只能是合數，因此我們將檢查向量中儲存的值是否不等於數字，以防 N 為質數。
否則，我們將迭代向量並使用模運算子計算該數字的不同質因數的數字和。然後，我們將計算數字 N 的數字和。如果兩者之和相等，我們將返回 true，因為它是一個欺詐數，否則我們將返回 false。
為了檢查數字是否為欺詐數，我們將在我們的方法中使用此演算法。
方法
以下是要遵循的步驟，以實現用於檢查數字是否為欺詐數的演算法
我們將建立一個布林函式來檢查數字是否為欺詐數。
初始化一個向量來儲存數字 N 的不同質因數。
我們將透過呼叫另一個函式來更新向量，我們將建立該函式以根據演算法中提到的步驟獲取 N 的不同質因數。
現在，我們將檢查向量中第一個索引處的值是否等於 N。如果它等於 N，則返回 false，因為 N 是質數，而欺詐數始終是合數。
如果 N 是合數，那麼我們將透過迭代向量來計算不同質因數的數字和。我們將使用模運算子計算質因數的數字，然後將數字除以 10 以獲取下一個數字。我們將每個質因數的數字和儲存在一個變數中，以獲取所有不同質因數的數字和。
現在使用相同的邏輯計算數字 N 的數字和，並將其儲存在一個變數中。
如果 N 的不同質因數的數字和與 N 的數字和相等，則返回 true，因為數字 N 是欺詐數，否則返回 false。
示例
//C++ code to check if N is a hoax number or not
#include <bits/stdc++.h>
using namespace std;
//function to store the distinct prime factors of N in vector
void factors(vector<int>& v, int N){
if(N%2==0){ //check if N is divisible by 2
while(N%2==0){ //divide N by 2 until remainder is equal to 0 and update N everytime
N = N/2;
}
v.push_back(2); //store 2 in the vector
}
//N must be odd now so iterate for odd numbers from i=3 to sqrt(N)
for(int i=3;i<=sqrt(N);i += 2){
if(N%i==0){ //if N is divisible by i
while(N%i==0){ //divide N by i until remainder is 0 and update N
N = N/i;
}
v.push_back(i); //store value of i in the vector
}
}
//for the case when N is a prime number greater than 2
if(N>2){
v.push_back(N);
}
}
//function to check sum of digits of distinct prime factors of N and N
bool check(int N){
vector<int> p; //vector to store distinct prime factors of N
factors(p,N); //calling the function to store prime factors of N in vector
if(p[0]==N){ //for the case when N is a prime number
return false;
}
int sum_factors=0; //to store sum of digits of distinct prime factors
//to calculate sum of digits of prime factors
for(int i=0;i<p.size();i++){
while(p[i]>0){ //adding each digit in the variable using modulo operator
sum_factors += p[i]%10;
p[i]=p[i]/10;
}
}
int sum_number=0; //to store sum of digits of N
//to calculate sum of digits of N
while(N>0){
sum_number += N%10; //adding each digit using modulo 10
N /=10; //dividing N by 10 to get the next digit
}
if(sum_factors==sum_number){ //N is a hoax number if sum is equal
return true;
}
else{
return false;
}
}
int main()
{
int N;
N=234;
//calling the function
if(check(N)==true){
cout<<N<<" is a hoax number"<<endl;
}
else{
cout<<N<<" is not a hoax number"<<endl;
}
return 0;
}
輸出
234 is a hoax number
時間複雜度− $\mathrm{O(\sqrt{N}*\log N)}$
空間複雜度− O(1)
結論
本文討論了欺詐數的概念以及一個數成為欺詐數的具體條件。我們使用 C++ 設計了一種有效的演算法，透過計算數字的質因數，然後檢查數字和來檢查給定的數字是否為欺詐數。
希望您在閱讀本文後消除了對該主題的所有疑問並理解了該方法。
200 次檢視
