牛客网华为机试——质数因子

牛客网华为机试——质数因子

题目描述

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

最后一个数后面也要有空格

输入描述:

输入一个long型整数

输出描述:

按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

示例1

输入

180

输出

2 2 3 3 5

思路：

这个题一开始我过于纠结质因子了，分解出来的因子我还去判断是不是质数，其实并不需要判断因子是不是质数！如果判断的话，就一直超时。

分解质因数，从最小的开始不停除法，除到为1，或者，除到最后除不了，就输出自己。

例如180：180%2=0 那么2为质因数输出2 （num=num/2=90)

90%2=0 那么2为质因数输出2 （num=num/2=45)

45%2!=0

45%3=0 那么3为质因子输出3 （num=num/3=15)

15%3=0 那么3为质因子输出3 （num=num/3=5)

5%3!=0

5%4!=0

5%5=0 那么5为质因子输出5 （num=num/5=1)

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
int main(){
    long num;
    cin>>num;
    int maxi=sqrt(num);
    for(int i = 2;i<=maxi&&num!=1;i++){
    while((num%i)==0){
           num/=i;
           cout<<i<<" ";
       }
 }
    if(num!=1)cout<<num<<" ";
    return 0;
    
}