파이썬(Python) 가장 큰 소인수 구하기

 

안녕하세요, 츄르 사려고 코딩하는 집사!      코집사입니다.

안녕하세요, 츄르 사려고 코딩하는 집사! 코집사입니다.

이번 글은 숫자가 주어졌을 때 그 숫자의 소인수를 구하는 문제입니다.

 

소인수 분해는 소수의 곱으로만 나타내는 것을 말합니다.

예를 들어, 16의 소인수 분해는 2X2X2X2 입니다.

다른 예로는 45의 소인수 분해는 3X3X5 입니다.

여기서 16의 소인수 분해에서 나온 2와 45의 소인수 분해에서 나온 3과 5는 소인수라고 합니다.

이처럼, 위의 예에서 13195의 소인수 분해는 5X7X13X29 이면서 5와 7, 13, 29는 소인수라고 합니다.

 

우리가 소인수 분해를 할 때 많이 사용하는 방법은 작은 수부터 나누면서 소인수 분해를 합니다.

1. 풀이

그래서 1을 제외한 소수 2부터 시작하여 입력받는 값의 number+1까지 반복문을 통해 소인수를 구별합니다.

입력받은 number가 0으로 나눠질 때까지 while문을 돌리면서

number을 i로 나눴을 때 몫을 계속적으로 나눌 것이기에 아래와 같이 코드를 구성하고, i값을 출력하여 가장 큰 소인수를 출력하는 문제입니다.

2. 코드

number = int(input())

for i in range(2, number+1):

    while(number%i==0):

        number /= i

        print(i)

        i+=1