w22116972
3/23/2014 - 2:57 AM

質因數分解

質因數分解

map<int,int> primeFactor(int n){
  map<int,int>res;      // res[i]=j     i:= 有哪些質因數 j:= 多少個相同的此質因數
  for(int i=2;i*i<=n;i++){
    while(n%i==0){
      ++res[i];	        // 如果有這個質因數就增加count值
      n/=i;
    }
  }
  if(n!=1) res[n]=1;
  return res;
}