백준 1929번 자바

문제

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

1929번: 소수 구하기

 

1. 소수 구하기

특정 범위의 소수를 구하기 위해선 여러방법이 있겠지만 특히 자주 사용되는 방법이 '에라토스테네스의 체' 이다.

 

원리는 간단하다 첫번째 소수인 2부터 2의 배수를 삭제한다. 그 다음 삭제 되지 않은 수인 3의 배수를 삭제하고 그 다음부터는 마찬가지다.

상세한 설명 및 예시는 아래에 있다.

https://terms.naver.com/entry.naver?docId=1179083&cid=40942&categoryId=32204 

에라토스테네스의 체

 

2. 접근 방식

이제 소수를 구하는 방법을 알았으니 구현을 하면 된다.

하지만 생각없이 구현하다간 시간초과가 날 확률이 높다.

2중 for문으로 소수를 구해야 하는데 조건식을 N으로 할 경우 1,000,000 x 1,000,000이 되어 시간 초과가 발생한다.

그렇기 때문에 조건식의 범위를 최소한으로 낮춰줘야 해당 문제를 해결 할 수 있다.

 

N이라는 숫자가 a*b로 이루어져 있을 때, a,b의 각각의 값은 N의 제곱근을 넘지 않는다. 

예를 들어 100의 제곱근 10인데, a = 10, b = 10인 경우를 제외하면 a = 20, b = 5처럼 한쪽은 항상 제곱근 이하의 값이다.

이 말을 해당 문제에 적용해보자.

 

어떤 수 N을 이루는 a,b라는 숫자가 각각 N의 제곱근을 넘지 않기 때문에

N미만의 수들을 이루는 x,y의 값은 a,b보다 작거나 같다. 즉, N미만의 수의 약수는 N의 제곱근을 넘지 않는다.

 

결국 1~100의 범위에서 소수를 구할 때 최대값인 100의 제곱근의 배수까지만 탐색을 완료하면 해당 범위의 소수는 모두 찾게 된다.

 

3. 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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 M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int[] arr = new int[N+1];
		
		for (int i=2; i<N+1; i++) {
			arr[i] = i;
		}
	
		for (int i=2; i<=Math.sqrt(N); i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j=i+1; j<N+1; j++) {
				if (arr[j]%arr[i] == 0) {
					arr[j] = 0;
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i=M; i<arr.length; i++) {
			if (arr[i] != 0) {
				sb.append(arr[i] + "\n");
			}
		}
		
		System.out.println(sb);
	}
}

 

정리 : 단순 구현 자체는 어렵지 않은데 시간초과라는 제한 때문에 힘들었다. 항상 원리에 주목하자.