12_백준 _4948 번 파이썬 베르트랑 공준

네,, 시간초과에요 왜요!
아무래도 입력값이 100000 까지 있다보니 일반적인 이중 for문으로 모든 수를 탐색하는 것이 불가한 문제이다.
구글의 힘을 빌렸다,, 에라토스테네스의 체 라는 함수를 이용해서 많이들 해결 했길래
보니까 수학적 규칙으로 소수 자신을 제외한 자신의 배수가 되는 숫자를 (22,222,,33,333,,55,555,,,) 전부 제거하면
남는 숫자는 소수뿐이다.. 라는 것을 이용해 코드를 짰다
처음의 시간 초과 코드는 맨 아래 있다

 

• 참고한 에라토스테네스의 체 함수

def prime_list(n):   ## 에라토스테네스의 체 함수 * sieve 가 '체 이다
  # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
  all_prime = [True] * n

  # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
  m = int(n ** 0.5)
  for i in range(2, m + 1):
      if all_prime[i] == True:           # i가 소수인 경우 (처음에 전부 소수라 가정했다)
          for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
              all_prime[j] = False
  # 소수 목록 산출
  return [i for i in range(2, n) if all_prime[i] == True]

 

• 풀이

while True:
    n = int(input())
    if n == 0:
        break

    count = 0
    prime_list = [True] * (2 * n + 1)  # 모든 수가 소수 라고 가정
    for i in range(2, int((n * 2) ** 0.5) + 1):
        if prime_list[i]:
            for j in range(i + i, n * 2 + 1, i):
                prime_list[j] = False

    for x in range(n + 1, 2 * n + 1):
        if prime_list[x] == True:
            count += 1

    print(count)