[BaeKJoon] 11653번: 소인수분해 (Python)

1일 최소 1문제 풀기 프로젝트 3일차!

오늘은 소인수 분해 문제를 풀어보려합니다.

11653번: 소인수분해

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하는 문제입니다.

 

소인수분해 문제이니 2일차에 풀었던 에라토스테네스의 체 문제를 활용하여 소수를 구하고 그 소수를 활용하여 풀어보기로 했습니다.

 

[BaeKJoon] 2960번: 에라토스테네스의 체 문제 풀이 (Python)

def getPrimaryNum_Eratos(N): 
    nums = [True] * (N + 1) 
    for i in range(2, len(nums) // 2 + 1): 
        if nums[i] == True: 
            for j in range(i+i, N, i): 
                nums[j] = False 
    return [i for i in range(2, N) if nums[i] == True]

에라토스테네스의 체 방법으로 소수를 구하고

N = int(input())

prime_nums = getPrimaryNum_Eratos((N // 2) + 1)

prime_nums_reverse = reversed(prime_nums)
# print(prime_nums)

answers = []

for prime_num in prime_nums_reverse:
    if N % prime_num == 0:
        while(N % prime_num == 0):
            answers.append(prime_num)
            N = N // prime_num
        
for num in answers:
    print(num)

그 소수의 list를 거꾸로 반전시킨 뒤 큰 소수부터 나누어지는 지 비교하여 나누어지면

그 수로 N % 소수의 나머지의 값이 0이 될때까지 계속 나누면서 나눌때마다 해당 소수의 값을 append 해주어 정답 list를 만들고

마지막에 출력을 해주는 방법으로 구현해보았습니다.

 

결과는!

앗..... 출력을 반대로 해주어

조금 수정하여 제출하여 보았지만!

def getPrimaryNum_Eratos(N): 
    nums = [True] * (N + 1)
    for i in range(2, len(nums) // 2 + 1): 
        if nums[i] == True: 
            for j in range(i+i, N, i): 
                nums[j] = False 
    return [i for i in range(2, N) if nums[i] == True]

N = int(input())

prime_nums = getPrimaryNum_Eratos((N // 2) + 1)

# prime_nums_reverse = reversed(prime_nums)
# print(prime_nums)

answers = []

for prime_num in prime_nums:
    if N % prime_num == 0:
        while(N % prime_num == 0):
            answers.append(prime_num)
            N = N // prime_num
        
for num in answers:
    print(num)

무엇이 문제일까 생각해보니 입력받는 값이 소수일 경우에 대해서는 생각을 하지 않았다는 것을 깨달을 수 있었습니다.

def getPrimaryNum_Eratos(N): 
    nums = [True] * (N + 1)
    for i in range(2, len(nums) // 2 + 1): 
        if nums[i] == True: 
            for j in range(i+i, N, i): 
                nums[j] = False 
    return [i for i in range(2, N) if nums[i] == True]

N = int(input())

prime_nums = getPrimaryNum_Eratos(N + 1)

# prime_nums_reverse = reversed(prime_nums)
# print(prime_nums)

if N in prime_nums:
    print(N)
else:
    answers = []

    for prime_num in prime_nums:
        if N % prime_num == 0:
            while(N % prime_num == 0):
                answers.append(prime_num)
                N = N // prime_num

    for num in answers:
        print(num)

정답! 시간이 조금 오래걸리긴했지만 맞았습니다!

 

이제 조금 더 효율적인 방법으로 짤 수 있을지 고민해보려합니다.

 

그럼 오늘은 여기까지!

 

SOMJANG/CODINGTEST_PRACTICE