밍의 기록들😉

[수학] 소인수분해 본문

자료구조, 알고리즘/기본다지기

[수학] 소인수분해

민쓰 2018. 8. 16. 22:15

소인수분해

  • 정수 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);
        }


0 Comments
댓글쓰기 폼