백준) 4948번 베르트랑 공준 .python

문제

베르트랑 공준은 임의의 자연수 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 ≤ n ≤ 123,456

2. n보다 크고, 2n보다 작거나 같은 소수

import sys

primeNumArray = [ False for i in range(123456 * 2 + 1)] 
primeNumArray[0] = True
primeNumArray[1] = True

for i in range(2, int(len(primeNumArray)**(1/2))+1): # 에라토스테네스의 체
    if primeNumArray[i] == True:
        continue
    for j in range(i*i, len(primeNumArray), i):
        primeNumArray[j] = True

while 1:
    cnt=0
    n = int(sys.stdin.readline())
    if n==0:
        break
    for i in range(n+1, n*2+1):
        if primeNumArray[i] == False:
            cnt+=1
    print(cnt)

1. 문제에 나온 범위만큼 boolean 타입으로 False를 만든다. (2n까지니까 123456*2+1)을 한다. (+1을 하는 이유는 0부터 시작하는 인덱스를 소수를 판별할 숫자로 사용하기때문)

2. 에라스토테네스의 체를 이용하여 소수가 아닌 숫자를 모두 True로 만든다. 0, 1은 소수가 아니라서 먼저 True로 만들어줌

3. i*i 부터 primeNumArray 끝까지 i씩 증가하며 True로 만들어준다. i의 배수들은 모두 소수가 아니기 때문이다.

4. 이미 True인 숫자는 가볍게 continue로 넘겨준다.

5. 입력받은 숫자 n부터 n*2까지 미리 소수 판별을 해놓은 array에서 False 인덱스일때만 cnt를 1 증가시켜준다

6. 출력!

 

처음엔 어려웠는데 알고나면 쉽다 !! 실무에서 사용할지는 모르겠지만 코딩테스트에서 소수문제가 나오면 절대 안틀릴거같다!!!

출처

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