质数因子

HJ6 质数因子

思路：

一开始想先筛一下质数，然后用hash去存一下，后来发现不用这样，因为在去判断是不是约数的时候实际上大的合数就被去掉了。
看下面的代码

代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

int main(){
    long x;
    cin >> x;
    map<int,int> Hash;
    
    for(int i=2;i<=x/i;i++){
	//比如4 4 = 2 * 2 但是在筛2的时候 while循环就把4筛掉了
        while(x%i==0){
            x/=i;
            Hash[i]++;
        }
    }
    if(x>1) Hash[x]++;
    
    for(auto i : Hash){
        while(i.second--) cout<<i.first<<' ';
    }
    return 0;
}

后来又发现，实际上hash都不用开

#include<iostream>
using namespace std;

int main(){
    long x;
    cin >> x;
    
    for(int i=2;i<=x/i;i++){
        while(x%i==0){
            x/=i;
            cout<<i<<' ';
        }
    }
    if(x>1) cout<<x;
    
    return 0;
}