4948 - 베르트랑 공준

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

4948번: 베르트랑 공준

문제요약

•  n 이라는 숫자가 주어졌을 때,  n <     <= 2n 범위 내의 소수의 갯수 구하기.
• n의 제한 : 1 ≤  n  ≤ 123,456
• 입력은 여러 개의 테스트 케이스로 이루어져 있음. 입력이 0이 주어지면 종료.

이번 문제의 핵심은, 입력 제한 수에 해당하는 소수 판별 배열을 미리 만들어놓고, n <     <= 2n 범위 내의 소수의 갯수를 구하는 것이다.

소수 배열을 만드는 과정 설명
1. 총 123456 * 2 + 1 크기의 boolean 타입의 배열 만들기(false로 초기화 되어 있음)
2. 배열의 1번째 ( 숫자 1에 대응 )는 사전에 true(소수가 아님)으로 변경
3. 이후 배열의 2번째 (숫자 2에 대응)부터 돌면서 자기 사진을 제외한 배수의 인덱스에 true(소수가 아님)로 변경

※ 해당 문제의 핵심 알고리즘은 '에라토스테네스의 체'를 바탕으로 만들어진 java 코드다.

 

 

import java.util.*;

public class Main {

    public static Scanner sc = new Scanner(System.in);
	
    // 소수 구하는 메소드
    public static boolean[] getPrime() {
        int num = 123456;

        boolean[] arr = new boolean[num * 2 + 1];
        arr[1] = true;

        // 소수인 것들만 false;
        for (int i = 2; i < arr.length; i++) {
        
        	// false를 만나면 자기 자신을 제외한 배수 인덱스를 모두 true(소수아님)으로 만들기
            if (!arr[i]) {
                for (int j = i * 2; j < arr.length; j += i) {
                    arr[j] = true;
                }
            }
        }
        return arr;
    }


    public static void main(String[] args) {
    
        boolean[] arr = getSosu();
        while (true) {
            int num = sc.nextInt();
            int count = 0;
			
            // while문 탈출 조건 
            if (num == 0) break;
			
            // 범위 내의 갯수 세기
            for (int i = num + 1; i <= 2 * num; i++) {
                if (arr[i] == false) count++;
            }
            System.out.println(count);
        }

        sc.close();
    }
}

---

느낀점

나름대로 적당한 알고리즘을 짜서 제출을 해봤지만, '시간초과'가 발생했다.

시간복잡도에 대한 내용을 알고 있으면 좋겠지만, 현재로선 시간복잡도를 계산하는 방법은 알수 없기에,

프로그램이 시작되면, 내가 소수의 갯수를 구하고자하는 범위의 소수를 알 수 있는 배열을 미리 만들어 두었다.

이후에는 특정범위 내의 소수의 갯수를 세기만 하면 되기에 간편했다.

다른 여러 방법이 있겠지만, 소수를 구하는 가장 심플하면서도 빠른 방법이 에라토스테네스의 체를 사용하는 것이라 생각했고, 적용해본 결과 성공

이미 공식화되어있는 방법 외의 방법을 생각해내기란 쉽지 않았다...

그래도 에라토스테네스의 체라는 공식을 알고 난 뒤, 나만의 코드로 구현하는 데에는 오래걸리지 않았다.

이미 완성된 코드를 찾기 보단, 그 코드가 생성된 공식을 알고 나만의 코드로 짜보는 것도 의미있는 것이라는 생각이 든다.알고리즘은 재밌으면서도 어렵다..ㅋㅋ