Java 백준 11653번 문제 - 소인수분해

소인수분해 성공

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초

256 MB

35847

19351

15203

53.072%

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

예제 입력 1 

72

예제 출력 1 

2

2

2

3

3

 

---

소인수 분해란 ? 어떠한 수를 소수인 인자로 분해한 것

 

for(int i = 2; i <= N; i++) {
      while(N % i == 0) {
         println(i);
           N /= i;
      }
}

이것도 몰론 정답이지만 조금 더 효율적으로 코드를 짜기 위해선

어떤 N이 두 개 이상 곱셈(인수)으로 나타낼 수 있을 때 인수 중 한 개 이상은 반드시 √N보다 작거나 같다는 것이다.

즉, 반복문의 범위를 √N까지 반복하는 것이다.

 

하지만 제곱근까지만 반복문을 돌렸을 때

34가 들어왔을 때 2로 나눈 17은 제곱근 범위에 포함되어 있지 않다

그렇기에 남은 N이 1이 아닐 때 즉 제곱근보다 큰 수라면 N도 

StringBuilder에 추가시켜서 출력해준다