[JAVA] 언더프라임_1124

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

1124번: 언더프라임

 

언더프라임 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

4099

1520

1157

39.869%

문제

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

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

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

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

첫째 줄에 A보다 크거나 같고, B보다 작거나 같은 언더프라임 개수를 출력한다.

제한

• 2 ≤ A ≤ B ≤ 100,000

예제 입력 1 복사

2 10

예제 출력 1 복사

5

예제 입력 2 복사

100 105

예제 출력 2 복사

2

예제 입력 3 복사

17 17

예제 출력 3 복사

0

예제 입력 4 복사

123 456

예제 출력 4 복사

217

출처

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main
{
    private static Scanner s = new Scanner(System.in);
    
    public static void main(String[] args) {
    	long answer = 0;
    	
    	int A = s.nextInt();
    	int B = s.nextInt();
    	
    	// 소수 저장
    	int max = B+1; // 최대수까지 소수 목록 체크
    	List<Integer> primeList = new ArrayList<>();
    	Boolean[] primeBl = new Boolean[max];
    	primeBl[0] = false;
    	primeBl[1] = false;
    	
    	for(int i=2; i<max; i++) {
    		if(primeBl[i]!=null && !primeBl[i]) continue;
    		
    		primeBl[i] = true;
    		primeList.add(i);
    		
    		for(int j=i*2; j<max; j+=i) {
    			primeBl[j] = false;
    		}
    	}

    	// 소인수분해 실행
    	for(int i=A; i<=B; i++) {
    		int tmpCnt = 0;
    		int saveI = i;
    		
    		// 애초에 소수면 (1이라 정답이 될 수 없음.)
    		if(primeBl[i]) {
    			continue;
    		}
    		
    		// 연산 수행 : 하나씩 빼서 소인수분해
    		for(int prime : primeList) {
    			while(saveI > 1 && saveI%prime == 0) {
    				tmpCnt++;
    				saveI /= prime;
    			}
    			
    			if(saveI == 1) break;
    		}
    		
    		
    		// 소인수분해 결과 갯수가 소수이면 정답 추가
    		if(primeBl[tmpCnt]) {
    			answer++;
    		}
    	}
    	
        System.out.println(answer);
    }
    
}