1일 N알고리즘 - #23

문제

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

4948번: 베르트랑 공준

문제는 위 사이트를 참고해주세요.

 

---

풀이

while True:
    n = int(input())
    if n == 0:
        break
    count = (2 * n) - n
    for i in range(n+1, 2*n+1):
        x = int(i ** 0.5)
        for j in range(2, x+1):
            if i % j == 0:
                count -= 1
                break
    print(count)

 

처음에는 위와 같이 풀었지만 계속 시간 초과가 발생하여 방법을 바꿨습니다.

 

primeList = [True] * 246913
for i in range(2, 246913):
    x = int(i ** 0.5)
    for j in range(i+i, 246913, i):
        if primeList[j] == True:
            primeList[j] = False
while True:
    n = int(input())
    if n == 0:
        break
    count = 0
    for k in range(n+1, 2*n+1):
        if primeList[k] == True:
            count += 1
    print(count)

 

바꾼 방법은 처음부터 입력값의 최대 수인 123456의 2배만큼인 246912까지의 소수를 미리 구해놓고

 

while문을 돌려서 n값이 주어졌을 때 소수인것만 카운트해서 출력하게 했습니다.

 

가장 위 for문은

https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/

소수 구하기 (에라토스테네스의 체)

이 원리를 사용해 소수를 판별한 것이기 때문에

제가 설명하는 것보다는 위 글을 읽고 직접 문제를 풀어보는 것이 더 좋을 것 같습니다.

 

---

결과

결과 화면