[수학] 소인수분해

소인수분해

• 정수 N을 소수의 곱으로 분해
• 소수를 구하지 않고 해결 가능
• N을 소인수분해 했을 때, 나타날 수 있는 인수 중에서 가장 큰 값은 루트 N
• 따라서 2부터 루트 N까지 나눌 수 없을 때까지 계속해서 나누면 됨

코드

        for(int i=2; i*i<=n; i++){
        	while(n%i==0){
        		System.out.println(i);
        		n = n/i;
        	}
        }
        if(n>1){
        	System.out.println(n);
        }