[Java] 자바 소인수 분해 / java 소인수 분해 구현하기

2020-09-18

---

소인수분해(영어: prime factorization, integer factorization)는 

합성수를 소수의 곱으로 나타내는 방법을 말한다.

소인수분해를 일의적으로 결정하는 공식은 아직 발견되지 않았다.

현대 암호 처리에서 소인수분해의 어려움은 중요한 기준이 된다.

 

산술의 기본 정리(fundamental theorem of arithmetic)에 의해

모든 양의 정수는 소수들의 곱으로 표현하는 방법이

(곱의 순서를 바꾸는 것을 제외하면) 유일하게 존재한다.

그러나 산술의 기본정리는 그 소인수분해를 하는 방법을 알려주지는 않는다.

단지 존재성을 확인해 줄 뿐이다.

출처 : 위키피디아

---

소스코드

 

※ 기본 알고리즘 원리는 우선 입력받은 값의 제곱근을 구해 

[ EX)  10 제곱근 3.xxxxx  ]정수 3이 될때까지 2부터 차근차근 나누어 주는 것이다.

// 3.XXX이니까 2~3까지 나누어질 것이다.

//다만 2로 나누어 졌을때 나머지가 0 이 됨으로

// 반복문은 탈출하게 된다. 3까지 갈 필요 없다.

그후 나머지가 0이 되는 값이 소인수가 된다. 

 

다음 소인수를 구하기 위해

//몫이 되는 값은 5이다.

나머지 외 몫이 되는 수를 다시 제곱근 후

위와 같은 방식으로 진행하며,

자기 자신이 나누어지는 수와 같아질때까지 반복한다.

 

		Scanner scan = new Scanner(System.in);
		
		int number, d, SqrtE;
		int [] arr = new int [100];
		int mok = 0, nmg = 0;
		
		int count = -1;
		//배열 위치 지정 함수
		number = scan.nextInt();
		
		while(true) {
			 
			d = 2;
			//제곱근 까지 하나씩 더해줄 수
			//1은 곱해도 1이기 때문에
			//제외 시키고 시작점은 2부터 시작
			
			SqrtE = (int) Math.sqrt(number);
			//정수 까지만 체크하면 되기 때문에
			//int 형은로 변환을 해줌
			
			while(true) {
				if(d > SqrtE) {
					d = number;
					break;
					//더 이상 d로 나누어 지는 값이 없어
					//d가 SqrtE 보다 커진 경우
					//number 자체가 소인수 이기 때문에
					//d 값에 number 대입
				}
				
				mok = number / d;
				nmg = number - mok * d;
				
				if(nmg == 0) {
					break;
					//나머지가 0이 되는 수도 
					//소인수 이기 때문에 배열 탈출
				}else {
					d++;
				}
				
			}
			count++;
			arr[count] = d;
			
			if(number == d) {
				break;
			}
			//number 와 d 값이 같은 경우
			//더 이상의 소인수는 없음
			//때문에 반복문 중단
				number = mok;
			//넘버를 몫값으로 초기화 해주고
			//다음 소인수 체크
		}
		
		for(int i = 0; i <=count; i++) {
			System.out.println(arr[i]);
		}