[백준] 11653번 : 소인수분해 - 파이썬[Python]

 

 

 

 

문제

11653번: 소인수분해

 

코드

A=int(input())
i=2
B=A
while i!=(A+1):
  if (B%i)==0:
    B=B/i
    print(i)
    i==2
  else:
    i+=1

 

풀이

소인수란 주어진 자연수를 나누어 떨어뜨리는 약수 중에서 소수(2, 3, 5, 7)인 약수를 말한다.

즉, 2 이상의 소수로 나누어 떨어지는 반복문을 활용하여 문제 풀이가 가능하다

일단 원본 변수 A와 계산할 변수 B를 설정한다.

그리고 i를 2로 지정한 후 (A+1)의 범위까지 1씩증가하는 반복문을 만든다.

(A+1까지 범위를 설정한 이유는 소수일 경우 소인수가 자기 자신이기 때문에 범위가 원본보다 커야 탐색이 가능하다)

 

if문을 활용하여 나누어 떨어지는(나머지가 0) 경우 B를 소인수로 나눈 후 다시 i값을 2부터 시작하는 조건문을 만들고,

나누어 떨어지지 않을 경우 i가 증가하는 조건을 추가한다.

 

위 방식을 활용하면 2부터 탐색을 시작해서 나누어 떨어지면 입력값을 나눈 뒤, 다시 2부터 하나씩 값을 올리며 탐색을 하여 소인수를 찾을 수 있다.