[백준] 1456번 - 거의 소수

1456번 - 거의 소수

 

<문제>

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

1456번: 거의 소수

 

<문제 풀이>

먼저 정해진 범위 내에서 소수만 저장된 List를 구한다. 

public static void makePrimeArr(long end) { // 소수로만 이루어진 List 생성
	arr = new long[(int) (end + 1)];

	for (int i = 2; i <= end; i++) {
		arr[i] = i;
	}

	for (int i = 2; i * i <= end; i++) {
		if (arr[i] == 0)
			continue;
		for (int j = i * i; j <= end; j += i) {
			arr[j] = 0;
		}
	}

	for (int i = 2; i <= end; i++) {
		if (arr[i] != 0) { // 소수이면 추가
			prime.add(arr[i]);
		}
	}
}

 

1차 시도

N은 2 이상이기 때문에 B의 제곱근을 사용할 소수의 범위로 지정한다. 만약 B가 1000이면, 2~31까지의 범위에 포함되는 소수를 사용하여 거의 소수를 구한다. 

소수만 저장된 List에 요소를 N 제곱해서 A ~ B 범위에 부합하는지 확인한다. 범위에 부합하면 거의 소수의 개수를 확인하는 변수를 1씩 증가시킨다. 

for문을 통해 List를 순회하고 나면 N을 1씩 증가시켜 List의 요소가 N 제곱하여도 A ~ B 범위에 부합하는지 확인한다.

만약 이 범위에 부합하지 않는다면 List에서 해당 요소를 제거한다. 

List의 크기가 0이 되면 이 과정을 종료하고 거의 소수를 저장한 변수를 출력한다. 

while (true) {
	if (prime.size() == 0) break; // prime의 길이가 0이되면 반복문 종료

	for (int i = 0; i < prime.size(); i++) {
		long tmp = (long) Math.pow(prime.get(i), N);
		if (tmp <= B) {
			if (tmp >= A) cnt++; //거의 소수 개수 증가
		} 
        else if (tmp > B) {
			prime.remove(i); // prime.get() ^ N의 수가B를 넘어가면 prime에서 해당 소수를 삭제
		}
	}
    
	N++; // N을 1씩 증가
}

하지만 이 방법은 시간초과로 실패...

 

2차 시도

makePrimeArr 메소드를 거쳐 만들어진 prime 리스트를 가지고 B의 범위만 고려하여 새로운 List를 생성한다. 

이 과정을 마치고 나면 이진 탐색을 사용하여 A의 범위도 고려하여 거의 소수의 개수를 구한다. 

1차 시도에서 걸렸던 시간 초과 문제를 이진 탐색으로 해결! 

 

<코드>

import java.io.*;
import java.util.*;

public class Main {
	static long A, B;
	static ArrayList<Long> prime = new ArrayList<>();
	static long[] arr;
	static long cnt = 0, N = 2;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Long.parseLong(st.nextToken());
		B = Long.parseLong(st.nextToken());

		// B의 제곱근을 사용하여 N제곱하긴 전의 소수의 범위를 지정
		// B=1000 -> 제곱근B = 31.xxx
		// 소수의 범위는 2 ~ 31 : 2,3,5,7,11,13,17,19,23,29,31
		// 각각의 소수에 몇 제곱을하여 B를 넘어가지 않는 거의 소수의 개수를 찾으면 됨

		long b = (long) Math.sqrt(B);
		makePrimeArr(b); // 소수List 생성

		ArrayList<Long> list = new ArrayList<>();
		//B의 범위만 고려하여 거의 소수를 구함.
		for (int i = 0; i < prime.size(); i++) {
			if (prime.get(i) >= B) //범위를 넘어감.
				break;

			for (int j = 2; true; j++) {
				if ((long) Math.pow(prime.get(i), j) > B)
					break;
				list.add((long) Math.pow(prime.get(i), j));
			}
		}

		//A의 범위도 고려하여 거의 소수를 구함. -> Binary Search
		Collections.sort(list);
		int s = 0;
		int e = list.size() - 1;
		while (s <= e) {
			int mid = (s + e) / 2;
			if (list.get(mid) >= A)
				e = mid - 1;
			else
				s = mid + 1;
		}

		System.out.println(list.size() - s);
		// 두 번째 오류 -> 시간초과: 이진탐색으로 해결!
	}

	public static void makePrimeArr(long end) { // 소수로만 이루어진 List 생성
		arr = new long[(int) (end + 1)];

		for (int i = 2; i <= end; i++) {
			arr[i] = i;
		}

		for (int i = 2; i * i <= end; i++) {
			if (arr[i] == 0)
				continue;
			for (int j = i * i; j <= end; j += i) {
				arr[j] = 0;
			}
		}

		for (int i = 2; i <= end; i++) {
			if (arr[i] != 0) { // 소수이면 추가
				prime.add(arr[i]);
			}
		}
	}
}

 

<결과>

 

 

2022.02.04