[已解决]2018年北邮机试题

lilejin322

发财数
题目描述：一个数字如果是由8个及8个以上的质因数乘积而成的数为发财数
输入：数字n
输出：10000以内的第几个发财数
举例：输入：1　　输出：256

个人思考：这道题首先应该用到分解质因数的问题，感觉应该是遍历倒着推小于10000的所有数字的分解质因数？然后看够不够8个以上的质因子

最佳答案

月排行榜 / 总排行榜

人造人

2019-3-12 12:57:11

用C++写的，不过我觉得你是要C语言的，如果是这样，那就由你来把这个代码修改成C语言的
还有提问时说明要用什么语言

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

bool isprime(size_t num)
{
        // 0和1既不是质数也不是合数
        if(num == 0 || num == 1)
                return false;

        size_t max = (size_t)sqrt(num);
        for(size_t i = 2; i <= max; ++i)
        {
                if(num % i == 0)
                        return false;
        }
        return true;
}

std::vector<size_t> prime_factorization(size_t num)
{
        // 分解质因数只针对合数
        // 0和1既不是质数也不是合数
        if(num == 0 || num == 1)
                return std::vector<size_t>();

        std::vector<size_t> v;
        while(!isprime(num))
        {
                num /= 2;
                v.push_back(2);
        }
        v.push_back(num);
        return v;
}

int main()
{
        size_t max;
        std::cout << "请输入一个数字: ";
        std::cin >> max;

        size_t count = 0;
        for(size_t i = 2; i < 10000; ++i)
        {
                if(prime_factorization(i).size() >= 8)
                {
                        if(++count == max)
                        {
                                std::cout << i << std::endl;
                                break;
                        }
                }
        }
        return 0;
}

请输入一个数字: 1
256
请按任意键继续. . .

请输入一个数字: 2
258
请按任意键继续. . .

请输入一个数字: 3
259
请按任意键继续. . .

请输入一个数字: 99
961
请按任意键继续. . .

跳转到最佳答案楼层

人造人

用C++写的，不过我觉得你是要C语言的，如果是这样，那就由你来把这个代码修改成C语言的
还有提问时说明要用什么语言

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

bool isprime(size_t num)
{
        // 0和1既不是质数也不是合数
        if(num == 0 || num == 1)
                return false;

        size_t max = (size_t)sqrt(num);
        for(size_t i = 2; i <= max; ++i)
        {
                if(num % i == 0)
                        return false;
        }
        return true;
}

std::vector<size_t> prime_factorization(size_t num)
{
        // 分解质因数只针对合数
        // 0和1既不是质数也不是合数
        if(num == 0 || num == 1)
                return std::vector<size_t>();

        std::vector<size_t> v;
        while(!isprime(num))
        {
                num /= 2;
                v.push_back(2);
        }
        v.push_back(num);
        return v;
}

int main()
{
        size_t max;
        std::cout << "请输入一个数字: ";
        std::cin >> max;

        size_t count = 0;
        for(size_t i = 2; i < 10000; ++i)
        {
                if(prime_factorization(i).size() >= 8)
                {
                        if(++count == max)
                        {
                                std::cout << i << std::endl;
                                break;
                        }
                }
        }
        return 0;
}

请输入一个数字: 1
256
请按任意键继续. . .

请输入一个数字: 2
258
请按任意键继续. . .

请输入一个数字: 3
259
请按任意键继续. . .

请输入一个数字: 99
961
请按任意键继续. . .