C++ 恶数

2025年3月25日 | 阅读 4 分钟

如果一个整数的唯一质因数的数字之和等于它本身的数字之和，则称该整数为“欺骗数”（hoax number）。值得注意的是，在计算质因数数字之和时，我们不包括 1，因为 1 不是质数。当一个合数被同一个质因数多次整除时，请注意只计算该质因数一次。

此问题的主要目标是确定给定的正整数（大于 1）是否应被视为欺骗数。一旦确定一个数字满足所有条件，可以称之为欺骗数，我们就可以确认它确实属于这一类别。

Input: 58
Output: yes.

输入包含数字 58，其质因数分解为 2*29。给定数字的数字总和为 5+8=13，其不同质因数的数字之和为 2+2+9=13。所提供的数字是欺骗数，因为数字之和相等，并且它满足一个数字成为欺骗数所需的所有要求。

Input: 54
Output: No

数字 54 分解为质因数是 2*3*3*3。2 和 3 是唯一的质因数，它们的数字之和是 2+3=5。

给定数字的数字之和为 5 + 4 = 9。给定数字不是欺骗数，因为其数字之和不等于其不同质数数字之和。

算法

如果一个数字的数字总和等于其唯一质因数的数字总和，则该数字被认为是欺骗数。不同质因数数字之和可以通过简单地计算该数字的所有不同质因数来获得。

我们将数字除以 2，直到它变为奇数，并将所有的 2 存储在另一个列表中。
使用 for 循环，我们将从 i=3 迭代到 i<=sqrt(N)，每次将 i 增加 2，因为此时 N 必须是奇数。
如果 N 可以被 i 整除，则重复除以它并计算除以的次数。之后，将 i 的值保存在另一个列表中。
每当 N 再次被同一个数字 (i) 整除时，继续更新 N 的值。
由于如果 N 是大于 2 的质数，使用上述步骤 N 不可能变为 1，因此请使用 if 语句检查其值，如果大于 2 则将其存储到另一个列表中。

示例

让我们举一个例子来说明 C++ 中的欺骗数。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// Function to find distinct prime factors of N and store them in a vector
void findDistinctPrimeFactors(vector<int>& factorsVector, int number) {
    
    if (number % 2 == 0) { // Check if number is divisible by 2
        while (number % 2 == 0) { // Divide number by 2 until remainder is 0
            number = number / 2;
        }
        factorsVector.push_back(2); // Store 2 in the vector
    }
    
    // Iterate for odd numbers from 3 to square root of number
    for (int i = 3; i <= sqrt(number); i += 2) {
        
        if (number % i == 0) { // If number is divisible by i
            while (number % i == 0) { // Divide number by i until remainder is 0
                number = number / i;
            }
            factorsVector.push_back(i); // Store value of i in the vector
        }
    }
    
    // For the case when number is a prime number greater than 2
    if (number > 2) {
        factorsVector.push_back(number);
    }
}

// Function to check if number is a hoax number
bool isHoaxNumber(int number) {
    vector<int> primeFactors; // Vector to store distinct prime factors of number
    
    findDistinctPrimeFactors(primeFactors, number); // Find prime factors of number and store them in vector
    
    if (primeFactors[0] == number) { // For the case when number is a prime number
        return false;
    }
    
    int sumOfPrimeFactors = 0; // Sum of digits of distinct prime factors
    
    // Calculate sum of digits of prime factors
    for (int i = 0; i < primeFactors.size(); i++) {
        int temp = primeFactors[i];
        while (temp > 0) {
            sumOfPrimeFactors += temp % 10; // Add each digit to sumOfPrimeFactors
            temp = temp / 10; // Move to the next digit
        }
    }
    
    int sumOfDigits = 0; // Sum of digits of number
    
    // Calculate sum of digits of number
    int tempNumber = number;
    while (tempNumber > 0) {
        sumOfDigits += tempNumber % 10; // Add each digit to sumOfDigits
        tempNumber /= 10; // Move to the next digit
    }
    
    if (sumOfPrimeFactors == sumOfDigits) { // If sum of digits of prime factors is equal to sum of digits of number
        return true; // Number is a hoax number
    } else {
        return false; // Number is not a hoax number
    }
}

int main() {
    int number;
    cout << "Enter a number to check if it's a hoax number: ";
    cin >> number;
    
    // Call the function to check if number is a hoax number
    if (isHoaxNumber(number)) {
        cout << number << " is a hoax number" << endl;
    } else {
        cout << number << " is not a hoax number" << endl;
    }

    return 0;
}

输出

Enter a number to check if it's a hoax number: 58
58 is a hoax number
Enter a number to check if it's a hoax number: 345
345 is not a hoax number

下一主题C++ 中的珠宝和石头

C++ 恶数

算法

示例

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 恶数

算法

示例

相关帖子

C++ 中的平面性测试算法

C++ STL 算法与自定义算法的区别

C++ std::tuple_cat() 函数

C++ 石头游戏

C++ 中的莱昂纳多数

C++ 中的卡塔德罗姆数

C++ 中的皮尔庞特素数

C++ Jarvis March 算法

C++ std::packaged_task 类

在 C++ 中使用旋转卡尺方法查找坐标平面上两点之间的最大距离

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器