(알고리즘)소인수 분해

//이 방법은 일일히 다 계산해야 하기 때문에 num이 커지게되는 경우는 구하기 힘들어진다. 즉 여기선 num을 구하기 위해서 N!의 N값이 주어졌다. 여기선 그 과정이 생략되었다.

private static void factorization_prime(int num,HashMap<Integer,Integer> hm)
{
int div=2;
int temp=1;
int temp2=num;

while(num!=1)
{
if(num%div==0){
temp=temp*div;
if(temp==temp2){
//div추가하기
if(hm.containsKey(div))
{
int value=hm.get(div);
hm.put(div, value+1);
}else{
hm.put(div,1);
}
break;
}
//소인수 div 추가하기
if(hm.containsKey(div))
{
int value=hm.get(div);
hm.put(div, value+1);
}else{
hm.put(div,1);
}
num=num/div;
div=2;
continue;
}
else{
div++;
}
}
}

//팩토리얼을 다 계산하면 num값이 너무 커지므로 작은 수 부터 소인수분해를 저장시켜 놓은 후 그걸 재이용하는 방법을 쓰겟다 예를들어) 5!의 소인수분해를 구하기 위해서는
2의 소인수분해 3의소인수분해 4의소인수분해를 미리 구해놓고 각 소인수를 합치는 방법이다.


public class SpecialNFac2 {


public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(reader.readLine());

HashMap<Integer,HashMap<Integer,Integer>> hm=new HashMap();
//2와 3인 경우는 각각 2 한개, 3 한개이다.
for(int i=2;i<=3;i++){
HashMap<Integer,Integer> temp=new HashMap();
temp.put(i,1);
//2와 3에 해당하는 소인 수들을 추가 시킴.
hm.put(i,temp);
}
for(int i=4;i<=N;i++){
   HashMap<Integer,Integer> temp=Factorization(i);
   ArrayList<Integer> li=new ArrayList<Integer>();
   li.addAll(temp.keySet());
   Iterator it=li.iterator();
   while(it.hasNext()){
    int key=(int)it.next();
    hm.put(i,temp);
   }
}
   ArrayList<Integer> li=new ArrayList<Integer>();
   li.addAll(hm.keySet());
   Iterator it=li.iterator();
   while(it.hasNext())
   {
    int key=(int)it.next();
    System.out.print(key+","+hm.get(key));
    System.out.println();
   }

}

private static HashMap<Integer,Integer> Factorization(int num) {
// TODO Auto-generated method stub
int div=2;
int temp=1;
int last=num;
HashMap<Integer,Integer> hm2=new HashMap<Integer,Integer>();
while(num!=1)
{
if(num%div==0)
{
temp=temp*div;
 
if(temp==last)
{
if(hm2.containsKey(div))
{
int val=hm2.get(div);
hm2.put(div,val+1);
}
else
hm2.put(div,1);

break;
}
if(hm2.containsKey(div))
{
int val=hm2.get(div);
hm2.put(div,val+1);
}
else
hm2.put(div,1);
num=num/div;
div=2;
continue;
}else
{
div++;
}

}
return hm2;

}

}