백준 BaekJoon Online Judge // 4948

백준 알고리즘 BaekJoon Online Judge 4948번 "베르트랑 공준" 문제입니다.

n=250000

a = [False,False] + [True]*(n-1) 
primes=[] 
for i in range(2,n+1): 
  if a[i]: 
    primes.append(i) 
    for j in range(2*i, n+1, i): 
      a[j] = False

while True:
  N = int(input())
  if N == 0:
    break
  lst = [x for x in primes if N < x <= 2*N]
  print(len(lst))

마찬가지로 소수 문제다. 지금 소수 파트를 다루고 있어서 그런지 소수 문제를 많이 올리게 된다.

 

이 문제도 마찬가지로 에라스토테네스의 체를 사용해서 푼다.

 

그리고 필터링으로 N초과 2*N이하의 수들을 새로운 리스트에 담은 후에 그 길이를 출력해준다.