每日一题——求解质因子

关键词

唯一分解定理

题目

给定一个数字 N，请你求出它的所有的质因子。

输入描述

输入仅一行包含为一个整数 N。

1\leq N \leq 10^{12}。

输出描述

输出仅一行，包含若干个整数，表示 N 的质因子（相邻两数用空格隔开）。

示例

输入

60

输出

2 3 5

知识点

算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

如：6936=2^3\times3\times17^2, 1200=2^4\times3\times5^2

解决方案

void solve(long long num){
    for (int i=2; i<=num/i; i++){
        while (num % i == 0){
            cout << i << ' ';
            while (num % i == 0) num = num / i;
        }
    }
    if (num != 0) {
        cout << num ;
    }
}