华为机试每日一练--第七题： 进制转换

练习题入口

问题描述

功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

数据范围： 1 \le n \le 2 \times 10^{9} + 14 \1≤n≤2×109+14

输入描述：

输入一个整数

输出描述：

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。

解题分析

       首先科普一下什么是质数的因子

质因子（或质因数）在数论里是指能整除给定正整数的质数。根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。只有一个质因子的正整数为质数。

将一个正整数表示成质因数乘积的过程和得到的表示结果叫做质因数分解。显示质因数分解结果时，如果其中某个质因数出现了不止一次，可以用幂次的形式表示。例如360的质因数分解是：

其中的质因数2、3、5在360的质因数分解中的幂次分别是3，2，1。

简而言之就是求一个数的因数，而这个因数必须是质数。

下面该分析解题思路了，我们知道n是由它的所有质因数相乘所得，那如何判断n的质因数呢？

质因数都是n的因子，所以当n取模等于0时，这个数就是n的质因数！

那如何找到所有的质因数呢？循环！假如质因数为a，当每次循环找到a后，我们就把n/a赋值为n（为了避免重复查找a），一直循环到找不到质因数为止。

       这样大致流程就确定了，但是我们也要减少循环次数，我们不能真的循环a-b次，那样耗费的时间就太长了。

当b>sqrt(a)+1时，就说明a中已经没有质因数了，这时循环就能结束了！

for (b=2; b < a; b++)
  {
  if (b > sqrt(a) + 1)
  {
    b = a;
  }
  if (a % b == 0)
  {
    printf("%d ", b);
    a = a / b;
  }
  }

上述伪代码其实存在漏洞，大家能发现吗？

我们看下图就能看到，第第三次循环找到了“4”，而4确不是120的质因数，所以上述代码存在问题

4为2*2，就说明a中的质因数不唯一，有重复的，那我们可不可以在一次for循环中在添加一个while循环，一直挑选出所有与b相同的质因数。

for (b=2; b < a; b++)
  {
  if (b > sqrt(a) + 1)
  {
    b = a;
  }
  while (a % b == 0)
  {
    printf("%d ", b);
    a = a / b;
  }
  }

这样我们就能顺利找出重复的质因数了

代码实现

#include<stdio.h>
#include<math.h>
int main()
{
    int a, b, i = 0;
    scanf("%d", &a);
    for (b = 2; b <= a; b++)
    {
        if (b > sqrt(a) + 1) //最小质数因子必小于输入数字的平方根
        {
            b = a;
        }
        while (a % b == 0)
        {
            printf("%d ", b);
            a = a / b;
        }
    }
    return 0;
}