백준 11653번 소인수분해 JAVA 구현해보기

---

```

백준 11653번 소인수분해 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 11653번 소인수분해 풀이

---

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

11653번: 소인수분해

 

 

 

백준 11653번 소인수분해는 난이도 브론즈 문제로서

 

정수가 주어지면 소인수 분해해서 출력하면 되는 프로그램입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

 

풀이 1

정수를 입력받고

입력받은 정수를

2부터 정수를 계속 나눈 값까지 반복해서

확인하고 나눠줘서

인자 리스트를 구해줍니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        findPrimeFactorList(Long.parseLong(br.readLine())).forEach(System.out::println);
    }

    public static List<Long> findPrimeFactorList(Long num) {
        Long currentNumSize = num;
        List<Long> factorList = new ArrayList<>();
        for (Long i = 2L; i <= currentNumSize; i++) {
            while (currentNumSize % i == 0) {
                factorList.add(i);
                currentNumSize /= i;
            }
        }
        return factorList;
    }
}

 

 

풀이 2

풀이 1에서 알고리즘의 효율성 증가를 위해서

중간마다 비교해주는 값의 제곱근을 구해줍니다.

마지막에 현재 비교하는 숫자가 1보다 크면 리스트에 넣어줍니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        findPrimeFactorList(Long.parseLong(br.readLine())).forEach(System.out::println);
    }

    public static List<Long> findPrimeFactorList(Long num) {
        Long currentNumSize = num;
        List<Long> factorList = new ArrayList<>();
        for (Long i = 2L; i <= Math.sqrt(currentNumSize); i++) {
            while (currentNumSize % i == 0) {
                factorList.add(i);
                currentNumSize /= i;
            }
        }
        if(currentNumSize != 1){
            factorList.add(currentNumSize);
        }
        return factorList;
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

 

---