BOJ 4948 베르트랑 공준

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

4948번: 베르트랑 공준

1번 풀이

#include <cstdio>
#include <math.h>
int main() {
    int n,cnt;
    while(scanf("%d",&n), (n)) {
        cnt = 0;
        for(int i=n+1;i<=2*n;++i) {
            int j=2, max = (int)sqrt(i);
            for(;j<=max;++j) {
                if(i%j == 0)
                    break;
            }
            if(j == max+1) cnt++; // 중간에 나누어 떨어지지 않으면 소수
        }
        printf("%d\n",cnt);
    }
}

 

 

x가 소수인지 알아보기 위해 2 ~ //(\sqrt{n}//)까지 나눠보는 고전적인 방법으로 문제를 해결했다. 답은 맞았지만, 너무 오래걸렸다.

 

처음 제출한 코드에서는 for loop 조건에 max 대신 (int)sqrt(i)가 들어있었는데, 632ms가 걸렸다. 매 번 조건을 확인할 때마다 제곱근 연산이 이루어져서 오버헤드가 발생한 것으로 생각된다. 이후 max로 대치한 후에는 수행 시간이 조금 줄어든것을 볼 수 있다.

 

그럼에도 다른 분들에 비해 너무 오래 걸려 코드를 공개하신 몇 분의 코드를 살펴봤다.

 

 

배열 prime[i]를 다음과 같이 정의하자.

      prime[i]: 정수 i가 소수이면 true / 아니면 false

set prime[] to true

prime [1] = false
for i in 2 ~ max {
	if prime[i] is true // i 가 소수이면
    	for j in 2*i to max by j += i // 소수의 배수들에 대해
            prime[j] = false
            // 소수의 배수들은 소수가 아님
}

즉 범위 내 모든 정수들에 대해 소수만 남기고 모두 제거한다. 이후에는 단순히 n ~ 2n 범위 내 prime[k]가 몇개인가 세면 문제를 해결 할 수 있다.

 

 

2번 풀이

#include <cstdio>
#include <cstring>
#define maxN 246912
bool prime[maxN];
//false가 소수의 갯수
int main() {
    int in;
    memset(prime,true,sizeof(prime));
    prime[1] = true;
    for(int i=2;i<=maxN;i++) {
        if(prime[i]) // i가 소수이면
            for(int j=i*2;j<=maxN;j+=i) // 소수의 배수들에 대해
                prime[j] = false; // 소수가 아님을 표시
    }

    while(scanf("%d",&in),(in)) {
        int ret = 0;
        for(int i=in+1;i<=2*in;++i)
            if(prime[i])
                ret += 1;
        printf("%d\n", ret);
    }
}