본문 바로가기
프로그래밍/백준 알고리즘 코드

백준 4948번 자바 베르트랑 공준 [기본수학2] 에라토스테네스의 체

by 졸린이 2021. 5. 4.
반응형

문제가 개떡같이 길게 쓰여 있지만 간단하게 풀면

n을 입력하면 n보다 크고 2n보다 작은 소수의 개수를 출력하는 문제이다.

0을 입력할 때 까지 계속 반복하면 끝~

 

저번 소수문제와 같이 이렇게 범위가 주어지고 소수를 구하는 문제는 에라토스테네스의 체 방법을 이용하면 된다.

 

마찬가지로 같은 방법을 이용해서 풀어보도록 하자.

hellodoor.tistory.com/114

 

백준 2581번 자바 소수 [기본 수학2] 에라토스테네스의 체

간단하다. m, n 두 수를 입력 후 m과 n 사이의 소수의 합을 출력하고 가장 작은 소수를 출력하면 된다. 여기서는 에라토스테네스 체 방법을 이용해서 문제를 풀어본다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1

hellodoor.tistory.com

에라토스테네 체의 관한 자세한 풀이는 요기에 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;
 
public class Main {
    //baekjoon 4948 베르트랑 공준 기본수학2
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        while(true) {
            int n = sc.nextInt();
            if(n==0) {
                break;
            }
            boolean arr[] = new boolean[2*n+1];
            arr[0= true;
            arr[1= true;
            
            for(int i=2; i<=Math.sqrt(2*n+1); i++) {
                for(int j=i*i; j<2*n+1; j+=i) {
                    arr[j] = true;
                }
            }
            int cnt = 0;
            for(int i=n+1; i<2*n+1; i++) {
                if(arr[i] == false) {
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}
 
cs


9행 : 0을 입력할 때 까지 반복해야 하므로 while(true)로 무한루프를 돌린다.

14행 : 소수 찾을 범위가 n보다 크고 2n보다 작으므로 2*n+1 크기로 bool 값 배열을 선언한다. (기본 false로 초기화됨)

 

15, 16행 : 2부터 검사할 것이므로 0과 1은 소수가 아닌 의미로 미리 true값을 준다.

18행 : 2 부터 (2*n+1)의 제곱근 까지 검사하고

19행 : j는 i의 제곱부터 범위까지 검사한다. 제곱한 수는 소수가 될 수 없다. j 에 i값씩 더해가며 반복

(처음에 2이므로 4, 6, 8 ...은 소수가 아님을 체크한다. 다음 수는 3이 들어와 9, 12, 15... 반복)

24행 : n보다 크고 2n보다 작거나 같으므로 i=n+1;  i<2*n+1 로 false값을 체크한다.

 

29행 cnt 출력~

반응형

댓글