[BOJ] 4948번

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

4948번: 베르트랑 공준

 

Python3

code1 - Fail

def sosu(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


if __name__ == '__main__':
    while True:
        N = int(input())
        if N == 0:
            break
        cnt = 0
        for number in range(N, 2*N+1):
            if sosu(number):
                cnt += 1
        print(cnt)

첫 풀이는 위와 같은 방식으로 구현했다. N부터 2N까지의 수를 sosu함수를 통해 소수인지 판별하고 소수라면 카운팅을 해주었다.  sosu함수는 수가 1인경우 소수가 아니기 때문에 false, 2부터 제곱근까지 돌면서 나누어지는 수가 있다면 false, 이 경우가 아니라면 소수인 것으로 판별했다.

하지만 이 방법은 시간초과가 났다.

 

 code2 - correct

if __name__ == '__main__':
    s = 123456*2+1
    prime = [True]*s
    for i in range(2, int(s**0.5)+1):
        if prime[i]:
            for j in range(i*2, s, i):
                prime[j] = False
    while True:
        N = int(input())
        if N == 0:
            break
        cnt = 0
        for number in range(N+1, 2*N+1):
            if prime[number]:
                cnt += 1
        print(cnt)

2가지 방식을 바꿨다. 주어진 범위 내의 소수 여부를 구해두고 나중에 개수만 세는 방식과 에라토스테네스의 체를 이용하여 소수의 개수를 구하는 방식을 사용했다. 테스트케이스가 많고 숫자가 클수록 code1의 방식은 같은 소수 판별을 여러번 해야해서 시간이 더 오래 걸렸다. 따라서 n의 최대값이 123456이고 2n의 범위까지 센다고 했으니 123456*2의 범위에 해당하는 수들의 소수 판별을 미리 해주었다.

에라토스테네스의 체 방식은 임의의 자연수 n에 대해서 이 수가 소수라면 정해진 범위까지 n의 배수인 수들을 모두 소수에서 제거하는 방식이다. 즉 정해진 범위내의 모든 수를 True, 소수라고 초기화해놓고 소수 2부터 시작하여 2의 배수는 모두 false로, 다음의 소수 3의 배수도 모두 false로, 이와같은 방식을 반복하여 소수를 남긴다.

이를 통해 정해진 범위까지 소수를 구했고 주어진 n보다 크고 2n보다 작거나 같은 소수들을 미리 구해둔 소수 배열 prime에서 소수여부를 판별하여 개수를 셌다.