백준 4948번 베르트랑 공준 / 백준 단계별로 풀어보기 8단계 / 8. 기본 수학 2

백준 8단계 5번 문제 - 4948번 베르트랑 공준

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

4948번: 베르트랑 공준

 

 

 

---

8. 기본 수학 2 (5) 백준 4948번 베르트랑 공준

---

문제

---

 

 

 

 

---

과정 생각해보기

---

 

1978번에서 했듯이

n이 입력될 때마다 반복되는 while문 안에

n부터 2n까지 반복문 하나 만들고

또 그 안에서 2부터 2n의 제곱근까지 나눠봐서 소수인지 따지면 될 것 같다

 

 

 

---

오답

---

 

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int count = 0;
        boolean prime = true;
        
        while(true) {
            int n = sc.nextInt();
            
            for(int i = n + 1; n <= 2*n; i++) { //n보다 크고 2n보다 작거나 같은 소수의 개수
                for(int j = 2; j <= Math.sqrt(2*n); j++) {
                    if(i % j == 0) {
                        prime = false; //소수가 아니라면
                        break;
                    }
                }
                if(prime) {count++;}
            }            System.out.println(count); //n입력될 때마다 출력해야 하니까 for문 밖, while문 안
            
            if(n == 0) { //0 입력하면 끝
                break;
            }
            
        }
    }
}

 

지금까지 썼던 코드들 여러 개 응용해서 써봤으나 시간 초과가 떴다

BufferedReader로 바꿔봐도 마찬가지였다

 

역시 에라토스테네스의 체를 써야하는 것 같다

 

그래서 해봤는데

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        while(true) {
            int n = Integer.parseInt(br.readLine());
            
            if(n == 0) {
                break;
            }
            
            boolean prime[] = new boolean[2 * n + 1];
            
            prime[0] = true;
            prime[1] = true;
            
            for(int i = 2; i <= Math.sqrt(2 * n + 1); i++) {
                for(int j = i * i; j < 2 * n + 1; j += i) {
                    prime[j] = true;
                }
            }
            
            int count = 0;
            for(int i = n+1; n <= 2 * n; i++) {
                if(prime[i] == false) //false는 소수
                count++;
            }
            System.out.println(count);
        }
    }
}

 

왜 안 되는 건지 모르겠다

java.lang.ArrayIndexOutOfBoundsException: 이클립스에서 이 오류가 뜨는데,

prime[] 크기를 2n + 1로 줬으면 n+1부터 2n까지 문제없이 들어갈텐데 왜 자꾸 안 들어간다는 건지 모르겠다~~~!!!

 

알고보니 29번째 줄에서 i가 아니라 n <= 2 * n으로 썼다

이러니까 안 되지........ 멀쩡한 다른 곳만 엄청 고쳤다..

 

 

---

정답 인정 코드

---

 

 

30번째 줄에 있는 count를 반복문 밖에 설정했더니 틀려서 안쪽으로 넣었다

 

---

직후 백지 복습

---

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          
          boolean prime[];
          
          while(true) {
              int n = Integer.parseInt(br.readLine());
              
              if (n == 0) break;
              
              prime = new boolean[2 * n + 1];
              
              prime[0] = true;
              prime[1] = true;
            
              for(int i = 2; i <= Math.sqrt(prime.length); i++) {
                  for(int j = i * i; j < prime.length; j += i) {
                      prime[j] = true;
                  }
              }
              
              int count = 0;
              for(int i = n + 1; i <= 2*n; i++) {
                  if(prime[i] == false) count++;
              }
              System.out.println(count);
          }
    }
}

 

prime[0] = prime[1] = true; 를 또 빼먹어서 여러 번 다시했다

23번 줄에 j <= prime.length 로 한 것도 엄청 여러 번 에러...

확인을 정말 잘해야겠다..

 

 

 

 

---

에라토스테네스의 체는 앞으로 절대 안 까먹을 듯