[프로그래머스][Lv.0][Java] 소인수분해

코딩테스트 연습 - 소인수분해 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

문제 설명

소인수분해란 어떤 수를 소수들의 곱으로 표현하는 것입니다. 예를 들어 12를 소인수 분해하면 2 * 2 * 3 으로 나타낼 수 있습니다. 따라서 12의 소인수는 2와 3입니다. 자연수 n이 매개변수로 주어질 때 n의 소인수를 오름차순으로 담은 배열을 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ n ≤ 10,000

---

풀이

• solution() : 2 부터 n 까지 반복하면서 i가 n의 약수인지 확인하고 isPrime 함수를 사용하여 i가 소수인지 확인하며, 둘 다 참일 때 answer 리스트에 추가한다. 마지막으로 'answer' 리스트를 'stream' 으로 변환하여 'mapToInt' 함수를 사용하여 'int[]' 배열로 반환한다.
  
  
• isPrime() :
  • 'n'이 '2'일 경우에는 소수이므로 'true'를 반환한다.
  • 'n'이 '2'보다 작거나 '2'로 나누어지는 경우에는 소수가 아니므로 'false'를 반환한다.
  • '3'부터 'sqrt(n)'까지의 수중에서 홀수인 수들을 i로 하여 'n'을 나누어 보며 소수인지 아닌지 판별한다.
  • 'n'이 'i'로 나누어지면 소수가 아니므로 'false'를 반환하고, 'sqrt(n)'까지 반복해도 소수가 아닐 경우 'false'를 반환한다.

import java.util.*;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> answer = new ArrayList<>();
        
        for (int i = 2; i <= n; i++) {
            if (n % i == 0 && isPrime(i)) {
                answer.add(i);
            }
        }
        
        return answer.stream().mapToInt(Integer::intValue).toArray();
    }
    
    public boolean isPrime(int n) {
        if (n == 2) {
            return true;
        }

        if (n < 2 || n % 2 == 0) {
            return false;
        }

        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }

        return true;
    }
}