/ BOJ

BOJ_1124_언더프라임_JAVA

문제 : 언더프라임

링크 : BOJ_1124_언더프라임

접근 방식

A부터 B까지의 각각의 수를 소인수분해하고, 그 길이가 소수인 경우 언더프라임이라고 한다. 언더프라임의 개수를 출력하면 되는 문제이다.

나는 이 문제를 먼저 1~100000까지 소수를 list를 만들어 저장해두고,

A부터 B까지 소수의 리스트에서 가장 작은 수 부터 나누어 떨어지는 경우 나누어주면서 소인수분해를 진행했다.

그 후 언더프라임인 경우를 체크하여 카운팅하여 그 결과를 출력하였다.

소스 코드

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

public class BOJ_1124_언더프라임 {

	static int arr[] = new int[100001];
	static ArrayList<Integer> list = new ArrayList<>();
	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st= new StringTokenizer(in.readLine());
		int idx = 0;
		for(int i=2;i<=100000;i++) {
			int P = i;
			if(arr[i] == 0) {
				for(int j = P+P; j <= 100000;j+=P) {
					arr[j] = 1;
				}
			}
		}


		for(int i=2;i<=100000;i++) {
			if(arr[i] == 0) {
				list.add(i);
			}
		}
//		System.out.println(list);


		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int cnt = 0;
		int ans = 0;
		for(int i=A;i<=B;i++) {
			int num = i;
			idx = 0;
			cnt = 0;
			while(true) {

				if(num % list.get(idx) == 0) {
					num = num / list.get(idx);
					cnt++;
				}else {
					idx++;
				}
//				System.out.println(num);
				if(num == 1) {
					break;
				}

			}
//			System.out.println("====");
			for(int j=0,n=list.size();j<n;j++) {
				if(list.get(j) == cnt) {
					ans++;
				}
			}

		}

		System.out.println(ans);
	}

}