[백준]_4948번 : 베르트랑 공준(파이썬 and C언어)

4948번: 베르트랑 공준

에라토스테네스의 체를 이용해서 시간 초과를 내지 않고 풀 수 있냐 없냐를 판정하는 문제이다. 사실상 전략이랄 것도 없어서 바로 코드로 들어가겠다.

---

시도 1(Python)

import sys

input = sys.stdin.readline


def eratosthenes(limit):
    primes = []
    is_prime = [1] * (limit + 1)
    is_prime[0] = is_prime[1] = 0

    for number in range(2, int(limit ** 0.5) + 1):
        if is_prime[number]:
            primes.append(number)
            for multiple in range(number * number, limit + 1, number):
                is_prime[multiple] = 0
    return is_prime


limit = 246912
prime_list = eratosthenes(limit)
while 1:
    n = int(input())
    if not n: break
    print(sum(prime_list[n + 1:2 * n + 1]))

시도 2(C언어)

#include <stdio.h>

#define LIMIT 246912

int is_prime[LIMIT + 1];

void eratosthenes() {
    for (int i = 0; i <= LIMIT; ++i) {
        is_prime[i] = 1;
    }
    is_prime[0] = is_prime[1] = 0;

    for (int number = 2; number * number <= LIMIT; ++number) {
        if (is_prime[number]) {
            for (int multiple = number * number; multiple <= LIMIT; multiple += number) {
                is_prime[multiple] = 0;
            }
        }
    }
}

int main() {
    eratosthenes();

    while (1) {
        int n;
        scanf("%d", &n);

        if (n == 0) {
            break;
        }

        int sum = 0;
        for (int i = n + 1; i <= 2 * n; ++i) {
            sum += is_prime[i];
        }

        printf("%d\n", sum);
    }

    return 0;
}