ING

안녕하세요 Jin's 입니다.

백준 알고리즘의 수학2 중 베르트랑 공준 ( 문제 번호 : 4948 )의 소스입니다.

Java와 Python 두가지 버전 소스입니다.

예시 ) 4  : 1 2 4

        12 : 1 2 3 4 6 12

* 제곱근의 루트보다 작은 수일때 약수가 존재하지 않는다면 소수이므로 찾는 범위를 반으로 줄여 시간을 줄일 수 있다. 

1) JAVA

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while(true){
			int n = scan.nextInt();
			int cnt = 0;
			if(n==0) break;
			
			for(int i=n+1; i<=2*n; i++){
				int result = 0;
				int half = (int)Math.sqrt(i);
				if(i==1) result++;

				for(int j=2; j<=half; j++){
					if(i%j==0){
						result++;
						break;
					}
				}
				
				if(result==0){
					cnt++;
				}
			}
			System.out.println(cnt);
		}
		scan.close();
	}

}

2) PYTHON

   * 파이썬은 자바처럼 해결하게 될 경우 시간 초과가 뜨게 된다.

     따라서 2n의 범위까지 나오는 소수들을 미리 구한 뒤 소수의 개수를 더해주는게 시간을 줄일 수 있다.

     반복해서 사용하게 될 경우 그때 그때 다시 계산해줄 필요가 없으므로 자바 또한 이러한 방식으로 바꿔서 풀면

     좋을 것 같다

import math
k = 123456*2+1
num_list = [1]*k
for i in range(1, k):
    if i == 1:
        continue
    for k in range(2, int(math.sqrt(i))+1):
        if i % k == 0:
            num_list[i] = 0
            break

while True:
    n = int(input())
    sum = 0
    if n == 0:
        break
    for i in range(n+1, 2*n+1):
        sum += num_list[i]
    print(sum)

여러분도 한번 풀어보세요!