(Python3) - 프로그래머스(코딩테스트 입문) : 소인수분해

https://school.programmers.co.kr/learn/courses/30/lessons/120852

프로그래머스

에라토스테네스의 체를 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

1. 정답 변수 answer선언 후 빈 배열로 초기화합니다.

 

📔 풀이과정

1. 소수를 구하는 prime() 를 구현합니다. 시간복잡도 $sqrt(n)$로 소수를 구할 수 있습니다. check배열을 선언해 주어진 값의 sqrt값만큼 for loop를 수행하면서 check되지 않은 경우 현재 값의 배수에 해당하는 index를 check해주는 방식입니다. 모두 check했을때 False인 index들만 primes 배열에 담아주면 소수가 담긴 배열이 됩니다.

 

2. primes의 원소를 순회하며 n에 나눴을 때 나누어 떨어진다면 answer에 추가해줍니다.

📔 정답 출력 | 반환

answer를 반환합니다.

---

📕 Code

📔 Python3

import math
def prime(limit):
    check = [False] * (limit + 1)
    primes = []
    for i in range(2, int(math.sqrt(limit)) + 1):
        if check[i] == True:
            continue
        for j in range(i+i, limit + 1, i):
            check[j] = True
    for i in range(2, limit + 1):
         if not check[i]:
            primes.append(i)
    return primes

def solution(n):
    answer = []
    primes = prime(n)
    for p in primes:
        if n % p == 0:
            answer.append(p)
    return answer

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.