백준 - 4948번 / 에라토스테네스의 체

베르트랑 공준

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

4948번: 베르트랑 공준

입력받은 n보다 크고, 2n보다 작거나 같은 수들 중 존재하는 소수의 개수를 출력해야 한다.

 

작성한 코드(시간: 1168ms)

max = 123456
def isPrime(num):
    if num == 1 or num == 0:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num % i == 0:
                return False
        return True
 
numbers = [ isPrime(i) for i in range(2*max +1)]
N = int(input())
while N:
    cnt = 0
    for i in range(N+1, 2*N +1):
        if numbers[i]:
            cnt += 1
    print(cnt)
    N = int(input())

최대 입력값인 123456(=max)이 입력됐을 때 확인해야 하는 수인 ( 2*max +1 ) 까지 소수를 찾는다.

입력한 값을 확인해 0이 아니면 while문을 반복한다.

N+1부터 2N까지의 수들 중 소수인 것들의 개수를 새서 화면에 출력한다.

 

여러 값들을 입력받아서 확인할 땐 소수인지 확인해야 하는 최대의 수까지 확인하고, 입력받은 값에 대한 값을 찾는 것이 더 빠른 방법인 것 같다. 예시에는 1, 10, 13... 작은 수의 케이스도 많이 나오는데 최대값에 가까운 값들을 여러번 입력받을 수 있기 때문이다.

 

속도를 향상하려고 다른 방법을 알아보다가 '에라토스테네스의 체'라는 방법을 사용해봤다.

일정 범위의 수들 중 소수인 것을 가려내는 방법이다.

1. 2부터 소수를 구하고자 하는 구간의 수들을 나열한다.

2. 2부터 자신은 빼고 2의 배수인 수들을 소수에서 제외한다.

3. 소수가 아닌 다음 수(3)를 제외하고, 3의 배수인 수들을 소수에서 제외한다.

이런 식으로 남아있는 수들 중 가장 작은 값은 소수로 남겨두고, 그 수의 배수들을 제외하면 된다.

구간의 최대값의 제곱근까지만 배수를 제외하고, 그 이후 남는 수들은 모두 소수로 배정하면 된다.

 

'에라토스테네스의 체'는 소수들의 배수만 확인하는데, 위의 코드는 range(2, int(num**0.5)+1) 의 값, 2부터 1씩 증가하며 확인하는 것이 다르다.

(시간 : 644ms, 반으로 줄어듬)

max = 123456 * 2 + 1
numbers = [ True for _ in range(max)]
 
for i in range(2, int(max**0.5)):
    if numbers[i]:
        for j in range(2*i, max, i):
            numbers[j] = False
            
while True:
    N = int(input())
    if N == 0:
        break
    cnt = 0
    for i in range(N+1, 2*N +1):
        if numbers[i]:
            cnt += 1
    print(cnt)

4) max까지 소수를 찾기 위해 √max까지 나눠서 확인한다. 그 이상은 확인할 필요가 없다.

5) 소수가 아닌 것들을 제외할 때, if numbers[i]로 소수인지 확인한 후 소수가 아니면 패스한다.

6) 2*i부터 i씩 증가하게 해서 i의 배수들을 False로 만든다.

9) while True:로 while에서 확인하지 않고 일단 while문을 실행한 뒤, 값을 입력받아 확인하도록 했다.

 

범위 내의 소수를 구할 땐 에라토스테네스의 체 방법을 사용하는게 제일 빠르다