[백준] 4948번 베르트랑 공준 - 파이썬

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

각 입력 n ~ 2n 까지의 소수의 갯수를 세면됨

 

def prime_num(n):
    if n == 1 :
        return False
    else:
        for i in range(2,int(n**0.5)+1):
            if n % i == 0:
                return False
        return True
Num_list = list(range(2,246912))
Sort_list = []
for i in Num_list:
    if prime_num(i):
         Sort_list.append(i)


while True:
    a = int(input())
    cnt=0
    if a == 0:
        break
    for i in Sort_list:
        if a < i <= a * 2:
            cnt += 1
    print(cnt)

소수가 아닌 값들을 제외한 리스트를 만들었다

• 에라토스테네스의 체

문제 - 1 페이지

꼭 알아두자

그리고 시간초과 소수하면 시간 초과 꼭 생각하자