[BaekJoon] 1124 언더프라임

오태호·2022년 3월 9일

baekjoon

1. 문제 링크

https://www.acmicpc.net/problem/1124

2. 문제

요약

소인수분해하여 얻은 수들의 개수가 소수인 수를 언더프라임이라고 합니다.
특정 수 A보다 크거나 같고 특정 수 B보다 작거나 같은 정수 중에서 언더프라임인 수의 개수를 구하는 문제입니다.
입력: 첫번째 줄에 정수 A와 B가 주어집니다.
출력: A보다 크거나 같고 B보다 작거나 같은 언더프라임의 수를 출력합니다.

3. 소스코드

초기 버전

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public boolean isPrime(int num) {
		for(int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	public int getUnderPrimeNum(int min, int max) {
		int count = 0;
		for(int i = min; i <= max; i++) {
			int num = i;
			ArrayList<Integer> primes = new ArrayList<Integer>();
			for(int j = 2; j < i; j++) {
				while(num % j == 0) {
					num /= j;
					primes.add(j);
				}
			}
			if(primes.size() != 0 && primes.size() != 1 && isPrime(primes.size())) {
				count++;
			}
		}
		return count;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		StringTokenizer st = new StringTokenizer(input);
		int min = Integer.parseInt(st.nextToken());
		int max = Integer.parseInt(st.nextToken());
		Main m = new Main();
		bw.write(m.getUnderPrimeNum(min, max) + "\n");
		bw.flush();
		bw.close();
	}
}

수정 버전

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public boolean isPrime(int num) {
		for(int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0) {
				return false;
			}
		}
		return true;
	}
	
	public int getUnderPrimeNum(int min, int max) {
		int count = 0;
		for(int i = min; i <= max; i++) {
			int num = i;
			ArrayList<Integer> primes = new ArrayList<Integer>();
			for(int j = 2; j <= Math.sqrt(i); j++) {
				while(num % j == 0) {
					num /= j;
					primes.add(j);
				}
			}
			if(num != 1) {
				primes.add(num);
			}
			if(primes.size() != 0 && primes.size() != 1 && isPrime(primes.size())) {
				count++;
			}
		}
		return count;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String input = br.readLine();
		br.close();
		StringTokenizer st = new StringTokenizer(input);
		int min = Integer.parseInt(st.nextToken());
		int max = Integer.parseInt(st.nextToken());
		Main m = new Main();
		bw.write(m.getUnderPrimeNum(min, max) + "\n");
		bw.flush();
		bw.close();
	}
}

4. 접근

A부터 B까지의 수들을 소인수분해하여 얻은 수들의 개수가 소수인지 판별하여 그 개수가 소수인 언더프라임의 수를 구하면 됩니다.

소인수분해를 하는 방법

소수인 2부터 시작하여 언더프라임인지 판별하고자 하는 수를 해당 수로 나누어보고 나누어떨어진다면 해당 수는 소인수가 되고 판별하고자 하는 수를 해당 수로 나누고 나눈 수를 이용하여 이 과정을 반복합니다.
더 이상 나누어떨어지지 않을 때는 해당 수로 더 이상 나누어지지 않으므로 다음 수로 넘어가여 이 과정을 반복합니다.

초기 버전에서는 소수인 2부터 시작하여 언더프라임인지 판별하고자 하는 수보다 1 작은 수까지 위의 소인수분해 하는 방법을 이용하여 소인수분해를 진행하였는데 시간 초과의 문제가 발생하였습니다.
수정 버전에서는 소수인 2부터 시작하여 언더프라임인지 판별하고자 하는 수의 제곱근까지 진행하였습니다. 그리고 진행한 후 남은 수가 1이 아니라면 그 수 또한 소인수가 됩니다.
20으로 예를 들면, 20의 제곱근은 4.4721...이므로 4까지 진행된다고 할 수 있는데, 2부터 4까지 위 방법으로 진행하면 {2, 2}가 결과로 나오게 됩니다. 이렇게 진행한 후 남은 수가 5인데 이 역시 소수이므로 소인수가 되게 됩니다.