python 백준 알고리즘 4948번: 베르트랑 공준

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

4948번: 베르트랑 공준

 

n부터 2n까지의 소수 구하기

 

이번엔 제곱근을 이용하여 소수를 구해도 시간초과에 걸린다;; 

문제에서 주어진 범위 내 소수를 먼저 구한 뒤 리스트를 대조하는 형식으로 문제 해결

덤으로 제곱근을 구하는데 파이썬 math 라이브러리를 import 하여 안에 정의된 sqrt 함수를 이용했다.

 

from math import sqrt

def prime(n):  # 소수 구하기
    if n == 1:
        return False
    for i in range(2,int(sqrt(n))+1):
        if n % i == 0:
            return False
    return True

numbers = list(range(2,246912))  # 제한 영역까지
prime_list = []								

for i in numbers:						
    if prime(i):							
        prime_list.append(i)  # 소수 리스트 만들어놓기					

n = int(input())

while True:
    cnt = 0					
    if n == 0 :
            break
    for i in prime_list:  # 소수 리스트와 대조			
        if n < i <=2*n:  # 소수 리스트 안의 숫자가 n~2n 사이에 있다면		
            cnt += 1  # 카운트 +1
    print(cnt)
    n = int(input())  # 0 입력받기 전까지 계속 입력