首页 > 试题广场 >

分解质因数

[编程题]分解质因数
  • 热度指数：251 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个正整数 n ，请将 n 按从小到大的顺序分解为若干个质因数并输出。输出的质因数乘积必须恰好等于 n 。

\hspace{15pt}【名词解释】
\hspace{23pt}\bullet\, 质因数：若正整数 p 仅能被 1 与自身整除，则称 p 为质数；若质数 p 能整除 n ，则称 p 为 n 的质因数。

输入描述:
\hspace{15pt}在一行上输入一个整数 n\left(2 \leqq n \leqq 10^{12}\right) ，代表需要进行分解的数。


输出描述:
\hspace{15pt}在一行上输出若干个整数，表示按照从小到大顺序排列的 n 的所有质因数。若某个质因数在分解中出现多次，则需重复输出对应的次数。相邻两个整数之间以单个空格分隔，行尾不得有多余空格。
示例1

输入

18

输出

2 3 3

说明

18=2\times3\times3。
示例2

输入

60

输出

2 2 3 5

说明

60=2\times2\times3\times5。
算法知识视频讲解
添加回答
C++
牛客207135092号头像 牛客207135092号
#include <iostream>
#include <vector>
using namespace std;

int main() {
    long long n;
    cin>>n;
    vector<long long> num;
    for(long long i=2;i*i<=n;i++){
        while(n%i==0){
            num.push_back(i);
            n/=i;
        }
        if(i!=2) i++;
    }
    if(n>1) num.push_back(n);
        for(auto it:num){
            cout<<it<<" ";
        }
    return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2025-07-06 10:07:17 回复(0)
提交观点

问题信息

难度：
1条回答 36浏览

热门推荐

相关试题

分解质因数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号