[BOJ 4948]베르트랑 공준

4948번: 베르트랑 공준

문제 분석 

• 제한시간 1초 : Big-O 기준 최대 1억 연산
• 1 ≤ n ≤ 123,456
• n 부터 2n 까지 소수인걸 센다.

계획

• bool형 배열을 만들어 2n까지의 수들 중 소수가 아닌 index의 값을 false로
• 이때, 에라토스테네스의 체를 이용한다.
  (에라토스테네스란 2부터 어떤수 까지 자기자신을 제외한 배수를 거름으로써 소수를 구하는 것을 말한다.)
• i의 배수를 지울때 "i*i" 부터 지우면 된다."i*j" (j<i) 는 i-j의 배수를 지울때 이미 지움
  ➣ 이로 인하여 √(2n) 의 배수까지만 지우면 된다.

#include <iostream>
#include <cmath>

#define MAX 250000

int n,last, cnt;
bool arr[MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    do{ // n이 0으로 초기화 되어있으므로 한번은 해준다.
        cin>>n;
        last = 2*n; //2n까지 시행
        cnt = 0;
        if(n==0) return 0;
        for (int i = n; i <= last; i++) {
            arr[i] = true;
        }// 모든 값을 true로 초기화
        for(int i=2;i<=sqrt(last);i++){ //2부터 root(last)까지의 배수
            for(int j=i;i*j<=last;j++){ // 곱해서 last넘어가면 안해도 됨
                arr[i*j] = false; //i의 제곱부터 i의 배수 false로
            }
        }
        for (int i = n+1; i <= last; i++) {
            if (arr[i]) {
                cnt++;
            }
        }
        cout<<cnt<<"\n";
    }while(n!=0);
}

느낀 점

• 처음엔 <map>을 이용한 재귀함수를 사용했다. 그랬더니 시간초과가 떴다. (<map>에서 index접근은 상수시간을 보장하지 않기 때문이다.)
• 그래서 배열을 만들었고, 재귀함수를 이중반복문 형태로 바꿔서 구현했다. 재귀함수에서는 반복문에서 한번, 반복문을 벗어나서 한번 함수를 호출해주기 때문에 시간이 더 걸리는 것 같다.

시간 복잡도(테스트 케이스 하나당)

• 이중 반복문 -> O(n²)