알고리즘/백준

[python] 백준 4948번 베르트랑 공준

펄찌 2021. 9. 1. 22:00

 

해당 문제는 1929번의 소수 구하기 문제와 유사하므로 풀이 과정은 생략하겠다.

 

[python] 백준 1929번 소수 구하기

문제 요약 및 풀이 M이상 N이하의 소수를 모두 출력 이 문제 같은 경우 1부터 ~ 1,000,000까지 소수인지 아닌지 일일이 검사한다면 시간 초과가 걸리게 될 것이다. 그렇기에 에라토스테네스의 체라

begin-dev-awos.tistory.com

코드!!👌👌

n = 123456*2
# 0, 1 = False, 소수는 2부터 시작이므로 True 로 설정
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
    cnt = 0
    for i in primes:
        if N < i <= 2 * N:
            cnt += 1
    print(cnt)

 

반응형