[Programmers] 소인수분해 (PYTHON, JAVA)

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

Algorithm

Idea

2부터 숫자를 늘려가며 나누어본다. 나누어지면 해당 숫자를 소인수분해 숫자 목록에 추가하고, 나누어지지않으면 1을 늘려 다음숫자로 나누어본다.

 

+) Java에는 LinkedHashSet이라는 것이 있어 중복을 허용하지않고 순서까지 보장해 준다!

---

Python

def solution(n):
    answer = []
    d = 2
    while d <= n:
        if n % d == 0:
            n /= d
            if d not in answer:
                answer.append(d)
        else:
            d += 1
    return answer

Java

import java.util.LinkedHashSet;

class Solution {
    public int[] solution(int n) {
        LinkedHashSet<Integer> primeNumbers = new LinkedHashSet<>();

        int i = 2;
        while (n != 0 && i <= n) {
            if (n % i == 0) {
                primeNumbers.add(i);
                n /= i;
            } else {
                i++;
            }
        }

//        System.out.println(primeNumbers);

        return primeNumbers.stream().mapToInt(Integer::intValue).toArray();
    }
}