【华为机试题分析】 6 质数因子

描述

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

输入描述：

输入一个整数

输出描述：

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

示例1

输入：180

输出：2 2 3 3 5

---

首先收下概念，质因数（或质因子）在数论里是指能整除给定正整数的质数，每个合数都可以写成几个质数相乘的形式，那么这几个质数就都叫做这个合数的质因数，比如10=2×5，那么2和5就是10的质数因子。

思路1：最大质因数必小于输入数字的平方根

#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;
}

思路2：如果一个数在它的根号左边或右边没有质数，那么这个数的质数只有1和它本身

#include <stdio.h>
#include <math.h>
 
int main() {
    long int n;
    scanf("%ld", &n);
    int i = 2;
    int j = 0;
    for (; i <= sqrt(n);) {
        if (n % i == 0) {
            printf("%d ", i);
            n /= i;
            continue;
        } else {
            i++;
        }
        j++;
    }
    printf("%d ", n);
 
    return 0;
}