백준 11653번 풀이

문제

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

주어진 수를 소인수분해하시오. (1이면 아무것도 출력 안 되게)

 

풀이

소인수분해는 합성수를 소수들의 곱으로 나타내는 것이다. 예를 들어 60을 소인수분해하면 2^2*3*5가 된다. 뭐 그런건데… 이 문제에서는 저렇게 제곱으로 나타낼 필요는 없고, 2 2 3 5 이런 순으로 출력하면 된다.

import sys
N = int(sys.stdin.readline().strip())
def isprime(a):
    if a < 2: 
        return False
    for i in range(2,a):
        if a % i == 0:
            return False
    else:
        return True
# 이거 근데 언제까지 써야됨...? 
for i in range(2,N+1):
    if N % i == 0 and isprime(i):
        while N % i == 0:
            print(i)
            N = N // i
    else: 
        pass

전체 코드. 여기서 중점적으로 볼 부분은 주석 밑에 부분이다.

for i in range(2,N+1):
    if N % i == 0 and isprime(i):
        while N % i == 0:
            print(i)
            N = N // i
    else: 
        pass

그러니까 여기.

 

for문과 그 아래에 있는 if는 N의 약수 중에서도 소수인 약수만을 골라내는 코드이고, 그 밑의 While문은 N을 i(위에서 찾은 소수인 약수)로 나누어서 나머지가 없을 동안, 그러니까 정확히 나눠 떨어질 동안 i를 계속 출력하면 된다.

 

참고로 else문에 있는 게 pass이기 때문에 별도의 처리가 없어도 1을 넣으면 아무것도 안 나온다.