[Java]소인수분해

 

 안녕하세요 코북입니다. 오늘은 소인수분해에 대한 문제를 풀었는데 여러가지 풀이 방법이 있어 기록하려고 합니다. 먼저 소인수분해의 뜻을 알아야 문제를 풀 수 있습니다. 어렸을 때부터 들어봤지만 정확히 무슨 뜻인지는 저도 잘 몰랐던 것 같습니다. 

 

소인수분해란?

소인수분해는 어떤 수를 소수인 인수로 분해하는 것이다. 소수는 1과 자기 자신으로만 나누어 떨어지는 정수를 의미한다. 소인수분해가 중요한 이유는 현대 암호학의 가장 기본 토대가 되는 부분이기 때문이다. 두 수의 곱셈을 결과로 나타내기는 쉬워도 결과를 두 수의 곱셈으로 나타내기는 어렵다는 역발상에서 시작되는 것이 암호학의 기초이기 때문에 그렇다고 한다.

 

 저는 두 가지 방식으로 문제를 해결했습니다.

첫 번째는 while문과 if문을 사용한 풀이이고, 두 번째는 for문과 while문을 이용한 풀이입니다.

 

1. while문과 if문 사용

public class Java09 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		System.out.print("소인수분해 할 수를 입력하세요. : ");
		int num = sc.nextInt();
		int i=2;
		
		while(num>=i) 
		{
			if(num%i==0) 
			{
				System.out.print(i);
				num /= i;
			}
			else 
			{
				i++;
			}
		}
	}
}

 

입력하는 값이 i보다 클 때 while문이 동작하고 나누어 떨어진 값을 반복적으로 출력해줍니다. 그리고 더 이상 나누어 떨어지지 않으면 i를 더해주는 방식입니다. 입력값이 i보다 커지면 while문은 동작을 멈춥니다. 여기서 위의 풀이처럼 인수 중간에 '*'를 추가하려면 다음과 같은 조건을 생성해주면 됩니다.

 

public class Java09 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		System.out.print("소인수분해 할 수를 입력하세요. : ");
		int num = sc.nextInt();
		int i=2;
		
		while(num!=1) //입력값이 1이 아닌 경우에만 동작
		{
			if(num%i==0) 
			{
				System.out.print(i);
				num /= i;
				if (num>i) //나눠지는 값이 i보다 큰 경우에만 * 삽입
				{
					System.out.print("*");					
				} 
				else 
				{
					break;
				}
			} 
			else 
			{
				i++;
			}
		}
	}
}

 

2. for문과 while문 사용

public class Java09_2 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		System.out.print("소인수분해 할 수를 입력하세요. : ");
		int num = sc.nextInt();
		
		for(int i=2; i<=num; i++) 
		{
			while(num%i==0) 
			{
				System.out.print(i);
				num/=i;
			}
		}
	}
}

결국 나누는 수를 반복하고 더 이상 반복이 되지 않을 때 더하는 규칙은 같습니다. 여기서도 중간에 *식을 넣어주려면 위에서 추가했던 if문을 삽입해주면 됩니다. 코드는 아래와 같습니다.

 

public class Java09_2 {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		System.out.print("소인수분해 할 수를 입력하세요. : ");
		int num = sc.nextInt();

		for(int i=2; i<=num; i++) 
		{
			while(num%i==0) 
			{
				System.out.print(i);
				num/=i;
				
				if(num>i) 
				{
					System.out.print("*");
				} 
				else 
				{
					break;
				}
			}
		}
	}

}

 

배운 점

소인수분해에 대해 더 정확한 개념을 알 수 있었고, 왜 소인수분해가 중요한지도 배울 수 있는 기회였다. while문에서 언제 break를 걸어야 하는지 생각해 볼 수 있는 시간이었다.

 

 

 

본 글은 아래 링크의 내용을 참고하여 학습한 내용을 나름대로 정리한 글임을 밝힙니다.

https://terms.naver.com/entry.naver?docId=925907&cid=47324&categoryId=47324

https://st-lab.tistory.com/152

https://st-lab.tistory.com/100