[백준] 8단계 - 4948번 (파이썬) check!

 

4948번

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

 

 

 

 

애증의 소수....😫

이번에도 '시간초과' 문제가 계속 발생했다.

어떤 분이 '에라토스테네스의 체'를 살펴보라고 하셔서

에라토스테네스의 체를 이용해서 문제를 풀었더니 다행히 문제가 풀렸다.

 

위키백과에 있는 에라토스테네스의 체 코드를 그대로 이용하는 방식(버전1)과

해당 코드를 응용해서 문제에 맞게 변형하여 푼 방식(버전2),

총 2가지 방법으로 문제를 풀어봤다.

(참고로 버전1이 더 깔끔한 것 같긴 하다...)

 

 

# 버전1
# n 미만의 소수 찾기(에라토스테네스의 체).
def prime_list(n):
    # 초기화: n개 요소에 True 설정(소수로 간주)
    ans = [True] * n
    
    
    for i in range(2, int(n ** 0.5) + 1):
        if ans[i] == True:             # i가 소수인 경우
            for j in range(2*i, n, i): # i이후 i의 배수들을 False 판정
                ans[j] = False


    # 소수 목록 추출
    return [i for i in range(2, n) if ans[i] == True]


x = int(input())
while x!=0:
    print(len([i for i in prime_list(2*x+1) if i>x]))
    x = int(input())

 

 

# 버전2
def prime_list(n):
    m = 2*n + 1        # 2n 이하의 소수 구하기 위해 2n+1로 설정.
    ans = [True] * m   # 초기화
    ans[0] = False
    ans[1] = False


    for i in range(2, int(m ** 0.5) + 1):        
        if ans[i] == True:             # i가 소수인 경우
            for j in range(2*i, m, i): # i이후 i의 배수들을 False 판정
                ans[j] = False


    # 문제에서 원하는 범위의 소수 목록 산출
    return [i for i in range(2, m) if (i>n) & (ans[i] == True)]


x = int(input())
while x!=0:
    print(len(prime_list(x)))
    x = int(input())