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

lilejin322

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

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

最佳答案

月排行榜 / 总排行榜

人造人

2019-3-12 12:57:11

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. 
   
5. bool isprime(size_t num)
   
6. {
   
7.         // 0和1既不是质数也不是合数
   
8.         if(num == 0 || num == 1)
   
9.                 return false;
   
10. 
    
11.         size_t max = (size_t)sqrt(num);
    
12.         for(size_t i = 2; i <= max; ++i)
    
13.         {
    
14.                 if(num % i == 0)
    
15.                         return false;
    
16.         }
    
17.         return true;
    
18. }
    
19. 
    
20. std::vector<size_t> prime_factorization(size_t num)
    
21. {
    
22.         // 分解质因数只针对合数
    
23.         // 0和1既不是质数也不是合数
    
24.         if(num == 0 || num == 1)
    
25.                 return std::vector<size_t>();
    
26. 
    
27.         std::vector<size_t> v;
    
28.         while(!isprime(num))
    
29.         {
    
30.                 num /= 2;
    
31.                 v.push_back(2);
    
32.         }
    
33.         v.push_back(num);
    
34.         return v;
    
35. }
    
36. 
    
37. int main()
    
38. {
    
39.         size_t max;
    
40.         std::cout << "请输入一个数字: ";
    
41.         std::cin >> max;
    
42. 
    
43.         size_t count = 0;
    
44.         for(size_t i = 2; i < 10000; ++i)
    
45.         {
    
46.                 if(prime_factorization(i).size() >= 8)
    
47.                 {
    
48.                         if(++count == max)
    
49.                         {
    
50.                                 std::cout << i << std::endl;
    
51.                                 break;
    
52.                         }
    
53.                 }
    
54.         }
    
55.         return 0;
    
56. }

复制代码

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

复制代码

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

复制代码

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

复制代码

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

复制代码

跳转到最佳答案楼层

人造人

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

1. #include <iostream>
   
2. #include <vector>
   
3. #include <cmath>
   
4. 
   
5. bool isprime(size_t num)
   
6. {
   
7.         // 0和1既不是质数也不是合数
   
8.         if(num == 0 || num == 1)
   
9.                 return false;
   
10. 
    
11.         size_t max = (size_t)sqrt(num);
    
12.         for(size_t i = 2; i <= max; ++i)
    
13.         {
    
14.                 if(num % i == 0)
    
15.                         return false;
    
16.         }
    
17.         return true;
    
18. }
    
19. 
    
20. std::vector<size_t> prime_factorization(size_t num)
    
21. {
    
22.         // 分解质因数只针对合数
    
23.         // 0和1既不是质数也不是合数
    
24.         if(num == 0 || num == 1)
    
25.                 return std::vector<size_t>();
    
26. 
    
27.         std::vector<size_t> v;
    
28.         while(!isprime(num))
    
29.         {
    
30.                 num /= 2;
    
31.                 v.push_back(2);
    
32.         }
    
33.         v.push_back(num);
    
34.         return v;
    
35. }
    
36. 
    
37. int main()
    
38. {
    
39.         size_t max;
    
40.         std::cout << "请输入一个数字: ";
    
41.         std::cin >> max;
    
42. 
    
43.         size_t count = 0;
    
44.         for(size_t i = 2; i < 10000; ++i)
    
45.         {
    
46.                 if(prime_factorization(i).size() >= 8)
    
47.                 {
    
48.                         if(++count == max)
    
49.                         {
    
50.                                 std::cout << i << std::endl;
    
51.                                 break;
    
52.                         }
    
53.                 }
    
54.         }
    
55.         return 0;
    
56. }

复制代码

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

复制代码

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

复制代码

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

复制代码

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

复制代码