[백준 4948 JAVA 자바] 베르트랑 공준

제가 정수론 수업을

대학교 2학년때 들었으니

거진 5년만에 들어보는 단어네요

"베르트랑 공준"

 

자연수 n이 주어졌을때

n보다 크고 2n보다 작거나 같은 소수의 개수를 찾읍시다

 

1. while문으로 반복을 하고

2. n~2n까지 for문을 돌리고

3. 각 수에대해서 소수판정을해서 count합시다

 

코드입니다

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));
		StringBuilder sb = new StringBuilder();
		
		int k = Integer.parseInt(br.readLine());
		sb.append(bertlang(k));

		while(true) {
			k = Integer.parseInt(br.readLine());
			if(k==0)break;
			sb.append('\n').append(bertlang(k));
		}
		System.out.print(sb);
	}  
	static int bertlang(int n) {
		int count = 0;
		
		for(int i=n+1;i<=2*n;i++) {
			if(isprime(i)==1) {
				count++;
			}
		}
		
		return count;
	}

	static int isprime(int m) {
		if (m==0 || m==1) 
		{
			return 0;
		}
		for (int i=2;i<=(int)(Math.sqrt(m));i++) {
			if (m%i==0) {
				return 0;
			}
		}
		return 1;
	}
}

실버2 문제지만

천천히 계산 순서를 생각하며 만들면

브론즈2와 비슷한 정도입니다