[백준 2024/01/15] 4948번

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

4948번: 베르트랑 공준

 

1) 접근 방법

간단히 말하면, n과 2n 사이에서 소수의 개수를 구하라는 것이다.

 

처음에는, 2중 for문을 이용해서, 만약 나누어 떨어진다면, break; 하는 식으로 생각하였다.

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;
import java.util.Collections;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //String N = scanner.nextLine();

        List<Integer> list = new ArrayList<>();
        int flag;

        while (true) {
            int number = scanner.nextInt();
            if (number == 0) {
                break;
            }

            for (int i = number + 1; i <= 2 * number; i++) {
                flag = 0;
                for (int k = 1; k < i; k++) {
                    if (i % k == 0 && k != 1) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0) {
                    list.add(i);
                }
            }
            //System.out.println(list);
            System.out.println(list.size());
            list.clear();
        }
    }
}

따라서 위와 같이 작성하였지만, 시간초과를 하였고

고민해보아도 잘 모르겠어서 chatGPT에게

"효율적으로 소수 구하는 법" 에 대해서 물어보았다.

 

소수(prime number)를 효율적으로 확인하는 방법 중 하나는 "에라토스테네스의 체"를 사용하는 것입니다. 하지만, 단일 숫자에 대해 소수 여부를 판별할 때는 이 방법이 적합하지 않을 수 있습니다. 단일 숫자에 대한 소수 판별을 위해서는 주어진 숫자의 제곱근까지만 나눗셈을 시도해보는 방법이 일반적입니다.

이 방법의 핵심은 어떤 수 n이 소수가 아니라면, n은 반드시 제곱근 이하의 수들 중 하나로 나누어 떨어진다는 것입니다.

 

에라토스테네스의 체를 이용하는 방법이 효율적이라는 것을 알게 되었다. 

이를 통해서 코드를 재구성하니, 시간초과를 하지 않고 제출할 수 있었다.

 

2) 코드

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class b4948 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        //String N = scanner.nextLine();

        List<Integer> list = new ArrayList<>();
        int flag;

        while (true) {
            int number = scanner.nextInt();
            if (number == 0) {
                break;
            }
            int answer = 0;

            for (int i = number + 1; i <= 2 * number; i++) {
                if(isPrime(i)){
                    answer += 1;
                    //System.out.println(i);
                }
            }
            System.out.println(answer);
            //System.out.println(list.size());
            //list.clear();
        }
    }
    public static boolean isPrime(int number){
        if(number <= 1){
            return false;
        }
        for(int i = 2; i<= Math.sqrt(number); i++){
            if(number%i ==0){
                return false;
            }
        }
        return true;
    }
}