[백준-자바] 4948번 베르트랑 공준 / 2022.02.07

 

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

4948번: 베르트랑 공준

 

 

https://cow-kite24.tistory.com/175

[백준-자바] 1929번 소수 구하기 (에라토스테네스의 체) / 2022.02.07

 

위의 문제(1929번 소수 구하기) 와 거의 동일한 문제입니다. 에라토스테네스의 체를 이해한다면 풀 수 있는 문제입니다.

 

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while(true) {
	        int n = sc.nextInt();
	        if(n==0) // 0이 입력되면 종료
	        	return;
	        int count = 0;
	        // 소수이면 false 소수가 아니라면 true
	        boolean sosu[] = new boolean[2*n+1]; // boolean 형 배열 생성
	        sosu[1] = true;                    // 1이면 소수가 아님 -> true
	        for(int i=2; i*i<=2*n; i++)          // i가 2부터 2n의 절반까지만 (에라토스테네스의 체)
	            if(!sosu[i])                     // 배열에 저장된수가 false일 경우
	                for(int j=i*i; j<=2*n; j+=i) // i가 2라면 j는 4, 6, 8, 10  i가 3이라면 j는 6, 9, 12, 15
	                    sosu[j] = true; 
	        // 배수는 소수가 아님 -> true 
	        for(int i=n+1; i<=2*n; i++){        // 우리가 궁금한 범위는 n 초과 2n미만
	            if(!sosu[i])                   // 범위 중에 false만 출력 (false가 소수)
	                count++;
	        }
	        
	        System.out.println(count);
        }
    }
}