백준 1456번 자바 ☆

문제

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

1456번: 거의 소수

 

1. 접근 방식

에라토스테네스의 체를 이용해 소수를 구하고 해당 문제 조건에 맞는 값을 구하면 된다. 

구현 자체는 어렵지 않았지만 A,B의 범위 값이 너무 크기때문에 long 타입으로도 못담는 숫자가 생긴다.

 

쉽게 예를 들자면 long의 최대 값이 100이고, B의 값이 81이라고 가정했을 때

소수 7의 3제곱은 343이므로 long의 범위를 넘기에 오버플로우가 발생한다. 엉뚱한 값이 생성되면서 조건을 통과하게 되면서 오답이 도출된다.

 

*실제 long의 범위는 2의 64제곱으로 -9223372036854775808 ~ 9223372036854775807 이며 굉장히 크다.

 

위와 같은 문제가 발생할 수 있기 때문에 조건식에서 곱하기 대신 이항정리를 통해 나누기로 작성해야 한다.

 

2. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
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());
		long A = Long.parseLong(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		long[] arr = new long[(int) Math.sqrt(B)+1];
		List<Long> list = new ArrayList<Long>();
		for (int i=1; i<arr.length; i++) {
			arr[i] = i;
		}
		for (int i=2; i<=Math.sqrt(B); i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j=i+i; j<arr.length; j+=i) {
				arr[j] = 0;
			}
		}
		
		for (int i=2; i<arr.length; i++) {
			long temp = 0;
			if (arr[i] != 0) {
				temp = arr[i];
				while (arr[i] <= B/temp) {
					temp *= arr[i];						
					if (temp >= A) {
						list.add(temp);					
					} 
					if (temp > B) {
						break;
					}
				}
			}
		}
		System.out.println(list.size());
	}
}

 

정리 : 해당 문제를 처음에 잘못 이해해 해당 조건의 값들을 모두 출력해야 하는 줄 알아 List를 사용했다. 하지만 몇개인지만 파악하면 되기에 변수 증감식을 통해 해결하는 쪽이 더 나았을 것이다.

또 int형의 오버플로우와 관련된 문제는 경험해봐서 걱정을 안했는데 long까지 건드니 전혀 생각을 못했었다. 이런식으로 출제되는 경우는 거의 없겠지만 그래도 항상 염두에 두자.