1124
언더프라임
- 소인수분해의 업그레이드
- 소인수분해 결과 소인수의 개수가 소수인 경우 언더프라임이라고 한다.
- A와 B가 주어지면, [A,B] 범위에서 언더프라임의 개수를 출력하는 문제.
import java.util.Scanner;
public class bj1124_0123 {
public static void main(String[] args) {
// 입력
Scanner sc = new Scanner(System.in);
int A = sc.nextInt();
int B = sc.nextInt();
sc.close();
// underprime 개수 카운팅
int cnt = 0;
for (int i = A; i <= B; i++) {
if (underprimeTest(i) == true)
cnt++;
}
// 결과 출력
System.out.println(cnt);
}
// 소수인지 아닌지 확인 (맞으면=true)
static boolean primeTest(int num) {
// 디폴트는 flag = true(소수가 맞다). 즉, 아래 테스트에서 걸리지 않으면 소수가 맞다는 논리.
boolean flag = true;
if (num < 2) { // 1은 소수 아님.
flag = false;
} else if (num != 2 && num % 2 == 0) { // 2가 아니면서 짝수면 소수아님.
flag = false;
} else if (num % 2 != 0) { // 2보다 큰 홀수에 관해
for (int i = 3; i <= (int) Math.sqrt(num); i += 2) { // 3부터 루트num까지 차례로 모든 홀수를 나눠 나머지를 구함.
if (num % i == 0) { // 나눠 떨어지는 순간 소수아님, 반복문 종료.
flag = false;
break;
}
}
}
// - 이 수는,
// - (1) 2이거나,
// - (2) (1이 아니면서 && 짝수도 아니면서 && 2보다 큰 홀수인데) && (자기 자신의 루트보다 작거나 같은 1아닌 모든 홀수에
// 대해 나눠 떨어지지 않는다면)
// - 그러면 flag = false를 거치지 않을 것이고, 따라서 디폴트인 true일 것이며 소수라고 할 수 있다.
return flag;
}
static boolean underprimeTest(int N) {
// 디폴트는 flag = false(언더프라임이 아니다). 즉, 아래 테스트를 통과하면 언더프라임이라고 인정해준다.
boolean flag = false;
// 소인수분해를 해서 소인수의 개수를 cnt로 카운팅함.
int cnt = 0;
// 본격 소인수분해
for (int i = 2; i <= (int) Math.sqrt(N); i++) { // 소인수는 2부터 루트N사이에만 존재할 수 있음.
if (primeTest(i) == false) // 만약 이번 회차 i가 소수가 아니면 다음 홀수 i로 건너뛰기.
continue;
if (N % i != 0) // 이번 회차 i는 소수가 맞긴 한데, 나눠 떨어지지 않는다면 다음으로 건너뛰기.
continue;
cnt++; // 두 건너뛰기에 해당안했으니 소수이면서 나눠 떨어진다는 뜻이므로 하나 추가.
N = N / i; // + 소인수로 나눠주고,
i = 1; // i는 처음부터 다시해야하니 초기화 해주고 다시 반복문 돌아감.
// (i=1을 해줘야 반복문 돌아가면서 i++에 의해 i가 다시 2로 시작할 수 있음.)
}
cnt++; // 마지막 남은 N은 소수일 수 밖에 없으므로, 하나 더 세줌.
// 본격 언더프라임 검사.
// cnt가 소수여야만 언더프라임.
if (primeTest(cnt) == true)
flag = true;
// 소인수 분해 결과 소인수 개수가 소수인 경우만 true를 반환.
return flag;
}
}
- 앞으로는 주석을 열심히 쓰기로 했다. 너무 열심히 쓴것 같긴 한데...
- 소인수분해 풀었던 코드를 복사해서 활용했다.
'PS - BOJ' 카테고리의 다른 글
1034 - 램프 (0) | 2022.01.24 |
---|---|
1138 - 한 줄로 서기, 1032 - 명령 프롬프트 (0) | 2022.01.23 |
10872 - 팩토리얼, 1065 - 한수 (0) | 2022.01.22 |
11729 - 하노이 탑 이동 순서 (빠른 입출력!!) (0) | 2022.01.22 |
11653 - 소인수분해 (0) | 2022.01.22 |