[Baekjoon] 1124_언더프라임

Silver I

문제(출처: https://www.acmicpc.net/problem/1124)

---

< 언더프라임 >

 

문제 풀이 

 

먼저 에라토스테네스의 체를 사용하여 소수인지 아닌지 판단한다.

 

그 후에 A이상 B이하의 값을 각각 소인수분해하여 소수의 개수를 구한다. 소수의 개수가 소수인지 판단한다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _1124_ { // 언더프라임

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());

		boolean arr[] = new boolean[100001];
		arr[0]=true;
		arr[1]=true;
		for (int i = 2; i < 50001; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 100001; j += i) {
					arr[j] = true;
				}
			}
		}

		int result = 0;
		for (int i = a; i <= b; i++) {
			int num = i;
			int cnt = 0;
			int idx = 2;
			while (idx <= num) {
				if (num % idx == 0) {
					num /= idx;
					cnt += 1;
				} else {
					idx++;
				}
			}
			if (!arr[cnt]) {
				result += 1;
			}
		}
		System.out.println(result);
	}
}

변수)
a, b : 두 정수
arr : 소수
result : 언더프라임 개수
num : 자연수 X
cnt : 자연수 X 소인수분해해서 구한 소수의 목록의 길이

 

두 정수 A와 B를 입력받는다. 

먼저 에라토스테네스의 체를 사용해서 소수를 판별할 수 있게 구해둔다. 

그다음 A이상 B이하의 값을 각각 소인수분해하여 소수의 개수를 구한다. 그 소수의 개수가 소수인지 판단한다.

---

---