[알고리즘] 백준 11653번 소인수분해 :: 우유

[알고리즘] 백준 11653번 소인수분해 :: 우유

소수 구하는 방법처럼 제곱근까지만 for문을 돌렸다.

소인수분해로 나누어지는 정수는 2부터 시작이고 2가 제일 작은 숫자기때문에

주어진 숫자는 제곱근 숫자 이하의 인수 개수만 가지기 때문

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); for (int i = 2; i <= Math.sqrt(N); i++) { while (N % i == 0) { System.out.println(i); N /= i; } } if (N != 1) System.out.println(N); } }

from http://studywithus.tistory.com/74 by ccl(A) rewrite - 2021-10-21 00:01:25