소인수분해
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 73515 | 39405 | 30680 | 52.237% |
문제
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.
출력
N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.
예제 입력 1
72
예제 출력 1
2
2
2
3
3
예제 입력 2
3
예제 출력 2
3
예제 입력 3
6
예제 출력 3
2
3
예제 입력 4
2
예제 출력 4
2
예제 입력 5
9991
예제 출력 5
97
103
방법1.
package Day1106;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B11653 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int i = 2;
//n이 1이 될 때까지 반복
while (N != 1) {
if (N % i == 0) {
N /= i;
sb.append(i + "\\n");
} else {
i++;
}
}
System.out.println(sb);
}
}
방법2. - 제곱근으로 소수찾아서 나누기(추천!!)
N이 72면 72까지 i를 다 돌리는게 아니라 72에 제곱근까지만 찾아주면 시간이 훨씬 줄어들것이다.
package Day1106;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B11653_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
for (int i = 2; i <= Math.sqrt(N); i++) { // 또는 i * i <= N
while (N % i == 0) {
sb.append(i + "\\n");
N /= i;
}
}
//N이 소수일 경우 그대로출력
if (N != 1) {
sb.append(N);
}
System.out.println(sb);
}
}
소수찾기
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0)
return false;
}
처음 틀린코드
package Day1106;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B11653 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int i = 2;
while (true) {
if (N <= 0)
break;
if (N % i == 0) {
N /= i;
sb.append(i+"\\n");
i = 2;
} else {
i++;
}
}
System.out.println(sb);
}
}
시간초과로 나온다….
while을 트루로해서그런가..?