[백준 - 자바] [실버] 1124. 언더프라임

이번 주의 문제

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

자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.

어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.

두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자.

<제한>
2 ≤ A ≤ B ≤ 100,000

생각해본 풀이

1. 소수를 판별하는 메서드를 따로 만들기 = 소인수인지, 소수 개인지를 세어야 하므로
2. 에라토스테네스의 체 알고리즘을 사용해서 인수를 분해한다
3. 이때, 2 x 2 처럼 같은 인수가 여러번 나올 수 있음으로, 이 부분을 고려한다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		
		boolean[] prime = new boolean[B + 1];
		Arrays.fill(prime, true);
		
		prime[0] = prime[1] = false;
		
		for (int i = 2; i * i <= B; i++) {
		   if (prime[i]) {
		       for (int j = i * i; j <= B; j += i) {
			           prime[j] = false;
			   }
	       }
		}
		
		int[] primeCount = new int[B+1];
		
		for (int i = 2; i <= B; i++) {
		    int number = i;
		    
		    //같은 숫자가 여러번 나눠질 수도 있기 대문에 while로 돌림
		    for (int p = 2; p <= Math.sqrt(number); p++) {
		        while (number % p == 0) {
		            primeCount[i]++;
		            number /= p;
		        }
		    }
		    
            //남은 게 1이 아니라면 또 곱해지는 숫자가 있으므로, ++
		    if (number > 1) {
		        primeCount[i]++;
		    }
		}
		
		int count = 0;
		
		for(int i = A; i <= B; i++) {
			if(isPrime(primeCount[i])) count++;
		}
		
		System.out.println(count);
	}

	private static boolean isPrime(int b) {
		
		if (b <= 1) return false;
		
	    for (int i = 2; i <= Math.sqrt(b); i++) {
	        if (b % i == 0) return false;
	    }
	    
	    return true;
	}
}

함께 보는 알고리즘

에라토스테네스의 체

에라토스테네스의 체는, 하나의 숫자의 배수들을 지워나가면서 소수인지, 아닌지 (또는 해당 숫자를 약수로 가지는지 아닌지)를 판별할 수 있습니다. 소인수분해와 비슷한 과정이라고 보면 되는데, 따라서 소수를 판별하고, 그 소수의 배수들은 소거해나가는 방법입니다.

소수 판별

private static boolean isPrime(int b) {
		
		if (b <= 1) return false;
		
	    for (int i = 2; i <= Math.sqrt(b); i++) {
	        if (b % i == 0) return false;
	    }
	    
	    return true;
	}

소수는 1과 자기 자신만을 약수로 가지는 숫자로, 2부터 자기 자신 이전까지의 숫자를 다 나누어 떨어지는지, 안 떨어지는지 체크하는 것이 소수 판별의 기본 골격이고, 이를 제곱근까지만 반복해도 되기 때문에, 위와 같이 메서드를 작성합니다.

에라토스테네스의 체

		// 소수는 false
        // 1은 소수가 아니므로 제외
        prime[0] = prime[1] = true;
        
        for(int i=2; i*i<=N; i++){
        	// prime[i]가 소수라면
            if(!prime[i]){
            	// prime[j] 소수가 아닌 표시
            	for(int j=i*i; j<=N; j+=i) prime[j] = true;                
            }        
        }

소수인지 아닌지를 판별하는 boolean 배열을 만든 후, 0과 1은 소수가 아니라서 제외하고, 2부터 주어진 숫자까지 계산하면 됩니다. (헷갈리면 true, false를 바꾸어도 됩니다!) 소수라면, 해당 소수의 배수를 전부 체크해주면 됩니다.