백준 4948번 : 베르트랑 공준

 문제

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

4948 베르트랑 공준

 

 구현 방법

 저는 에라토스테네스의 체를 사용해서 풀어주었습니다.

한번에 쫙~~ 구하고 바로 값만 가져오면 되므로 문제 푸는 시간이 굉장히 짧아집니다.

위키백과에 나와있는 에라토스테네스의 체 알고리즘 설명입니다.

 

 

 

 

 

 

 

 

 

간단하게 보자면.. 소수는 2, 3, 5, 7, 11 ... 입니다. 소수의 배수들은 소수가 될 수 없으므로 설정한 범위내에서 소수의 배수들을 미리 소수가 아니다~~ 라고 표현해줍니다.

1은 소수가 아니므로 제외하고 2부터 해당 범위까지 반복문을 설정해줍니다.

2일 때 : 2의 배수들인 4, 6, 8, 10,,,,,  => 소수 아님

3일 때 : 의 배수들인 6(계산할 필요 없음), 9, 12, 15,,,,, => 소수 아님

4일 때 : 계산할 필요 없음

이미 소수가 아니라고 판정된 수는 계산할 필요가 없으므로 내부 반복문은 i*i부터 해당 범위까지 i만큼 키워줍니다.

 

 구현 코드

package BOJ.Silver;

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

public class B4948_베르트랑공준 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while(true) {
			int N = Integer.parseInt(br.readLine());
			if (N==0) break;
			
			boolean[] cnt = new boolean[250000]; // 2n을 구해야하므로 제한되어있는 123,456보다 2배값을 크기로 설정
			
			for (int i=2;i*i<cnt.length;i++) {
				for (int j=i*i;j<cnt.length;j+=i) {
					cnt[j] = true;
				}
			}
			int ans = 0;
			for (int i=N+1;i<=2*N;i++) {
				if (!cnt[i]) ans++;
			}
			
			sb.append(ans+"\n");
		}
		System.out.println(sb);
	}
}

 

정답!