[Baekjoon] 1456_거의 소수

Gold V

문제(출처: https://www.acmicpc.net/problem/1456)

---

< 거의 소수 >

 

문제 풀이 

 

먼저 에라토스테네스의 체 알고리즘을 사용하여 소수를 구한다. 이때 범위는 B값의 제곱근을 사용한다. 

소수를 판별하는 배열을 탐색하며 N제곱을 구한다. A보다 크거나 같고 B보다 작거나 같은 거의 소수 개수를 구한다.

 

 

 my solution (Java)

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

public class _1456_ { // 거의 소수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		long A = Long.parseLong(st.nextToken());
		long B = Long.parseLong(st.nextToken());

		boolean arr[] = new boolean[(int) Math.sqrt(B) + 1];
		arr[0] = true;
		arr[1] = true;
		for (int i = 2; i < ((int) Math.sqrt(B) + 1) / 2 + 1; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < (int) Math.sqrt(B) + 1; j += i) {
					arr[j] = true;
				}
			}
		}

		int result = 0;
		for (int i = 1; i <= (int) Math.sqrt(B); i++) {
			if (!arr[i]) {
				long num = Long.valueOf(i);
				while ((num*=Long.valueOf(i)) <= B) {
					if(num >=A) {
						result += 1;
					}
					if(num > B/Long.valueOf(i)) {
						break;
					}
				}
			}
		}
		System.out.println(result);
	}
}

변수)
A, B : 왼쪽, 오른쪽 범위
arr : 소수 판별
result : 거의 소수 개수

 

두 정수 A와 B를 입력받는다. 이때, A와 B의 범위가 1 이상 10의 14승 이하이므로 long 타입으로 입력받는다.

에라토스테네스의 체 알고리즘을 사용하여 0부터 B의 제곱근까지 소수를 판별한다.

 

소수를 판별하는 배열을 전체 탐색하여 소수라면 다음 과정을 반복한다.

1) N제곱을 구해 B이하이고 A이상이면 result+1을 한다.

2) 다음 N+1 제곱을 구하기 위해 오버플로우가 발생하는지 확인한다. num*Long.valueof(i) > B로 확인하면 오버플로우가 발생해 정확한 비교가 불가능하므로 num > B/Long.valueOf(i)로 판단한다.

 

거의 소수 개수를 출력한다.

---

* 오버플로우로 인하여 제대로 된 비교를 하지 못해 정확한 답을 구할 수 없었다.

---