백준 알고리즘 4948 문제 풀이 (java) - 베르트랑 공준

다음은 4948번 문제입니다.

만약, 10이 주어지면 10(n)보다 크고 20(2n)보다는 작거나 같은 소수의 개수를 출력하는 문제입니다.

 

1. 0을 입력받을 때까지 계속하여 입력을 받아야 하기 때문에 while문을 만들어 줍니다.
2. 소수인지 아닌지 판단하기 위한 boolean타입의 배열을 n+1크기 만큼 만들어 주고, true로 초기화 해줍니다.
   (0과 1은 소수가 아니므로 false로 값 세팅)
3. 2부터 N까지의 도는 for문을 만들어 줍니다.
4. for문안에 j=2부터 j*i는 N과 같거나 작을때 까지 도는 포문을 만들어 줍니다. 
   (약수가 있다는 것은 소수가 아니기 때문에 2부터 N까지의 배수들을 모두 false로 만들어 줌)
5. data배열의 ture값 만큼 카운트를 증가해 줍니다.

이렇게 만들어 주면 문제를 풀 수 있습니다.

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int m=1;
		
		while(true) {
			m=s.nextInt();
			if (m==0) break;
			int n=m*2;
			int cnt=0;
			boolean[] data= new boolean[n+1];
			
			data[0]=false;data[1]=false;
			for(int i=2;i<=n;i++) data[i]=true;
			for(int i=2;i<=n;i++) 
				for(int j=2;j*i<=n;j++) 
					data[i*j]=false;
			for(int i=m+1;i<data.length;i++) 
				if (data[i]) cnt++;
			System.out.println(cnt);
		}
	}
}