백준 4948번 <베르트랑 공준> [파이썬]

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

4948번: 베르트랑 공준

베르트랑 공준

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

제한

• 1 ≤ n ≤ 123,456

예제 입력 1 복사

1
10
13
100
1000
10000
100000
0

예제 출력 1 복사

1
4
3
21
135
1033
8392

 

 

우선 이 문제를 풀려면, 에라토스테네스의 체를 알아야 한다!

나도 이 것에 대해선 몰랐는데, 에라토스테네스의 체를 간단하게 설명하면, 

1. n까지의 소수를 알고 싶을 경우 사용하는 것이다.

2. 가장 작은 수의 배수부터 시작해서 각 수의 배수를 없애는 것이다.

3. 즉, n이 10까지면, 2의 배수인 4,6,8,10을 없애고 그 다음 작은 수인 3의 배수인 6,9를 없애는 식으로 가는 것이다.

4. 이렇게 가다보면, 어느 순간 소수들만 남아있고, 테이블은 변하지 않는다.

 

즉 이런 생각을 가지고 알고리즘을 만들면!

def isPrime(n2,n):
    a = [True] * (n2 + 1)
    m = int(n2**0.5)
    for i in range(2, m + 1):
        if a[i] == True:
            for j in range(i + i, n2 + 1, i):
                a[j] = False
    print(len([i for i in range(n+1, n2) if a[i] == True]))

while True:
    n = int(input())
    if n == 0:
        break
    elif n == 1:
        print(1)
    else:
        n2 = n * 2
        isPrime(n2,n) 

이런식으로 만들어진다!

def isPrime(n2,n):
    a = [True] * (n2 + 1)
    m = int(n2**0.5)
    for i in range(2, m + 1):
        if a[i] == True:
            for j in range(i + i, n2 + 1, i):
                a[j] = False
    print(len([i for i in range(n+1, n2) if a[i] == True]))

 함수부분부터 설명해보면, 

n2와 n이 인자로 들어오고, 

n2+1개 만큼 True를 갖는 a리스트를 만들어주고

int(n2**0.5)는 제곱근을 뜻하는데, 즉 예를 들면 

n2가 2라면 제곱근은 1이고, 4면 2이고, 8이여도 2이고, 9면 3이고 15면 3이고 16이면 4이다.

즉 m이 될 수 있는 값들은 1-> 1,  4->2,  9 -> 3 ... 이렇게 제곱이 되는 수가 될 때 값이 바뀐다.

그리고 그 제곱근 만큼 반복문을 돌리는 이유는, 최대한 반복문을 돌리는 시간을 줄이기 위해서이다!

리스트 a에 있는 True값들을 아까 말했듯, 각 수의 배수의 크기가 되는 것들을 모두 False로 바꿔주고 나서

바뀐 리스트의 True값의 수를 세는 것이다!

설명이 좀 두서없긴 하지만, 최대한 자세히 써본 것이다. [내 공부도 할겸ㅎ]

 

쨋든 이렇게 되고

그 다음은 어렵지 않은데, 한번 지켜볼 부분은 메인 함수에

else:
    n2 = n * 2
    isPrime(n2,n) 

이 부분인데, n과 n2를 인자로 넣는 이유는 알다시피 범위제한이고, 함수 마지막 프린트 부분쪽을 보면, 이 두 인자가 들어가 있는 것을 확인할 수 있다. 더불어서 문제에서 n보다는 큰 값부터 소수를 세라고 했기 때문에 n+1을 한것이다!

 

 

에라토스테네스의 체를 알지 못한다면, 일반 알고리즘으로는 어려울 것이다.

그렇게 잘하는 것이 아니기에 이 방법을 제외하고 일반적인 알고리즘을 자체적으로 만들어서 시간제한을 맞추는 것은 쉽지 않을 것이다.

코테를 준비하는 만큼, 알아야 될 것들이 이렇게 수학공식으로도 있다는 것에서 좀 놀랐지만, 그래도 하나 알아가서 좋다!

 

 

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2011 Japan Domestic Contest A번

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체