欺诈数


问题陈述包括检查给定的数字 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++ 设计了一种有效的算法,通过计算数字的质因数,然后检查数字和来检查给定的数字是否为欺诈数。

希望您在阅读本文后消除了对该主题的所有疑问并理解了该方法。

更新于:2023年8月28日

200 次查看

开启您的 职业生涯

通过完成课程获得认证

开始
广告