문제 링크 : https://www.acmicpc.net/problem/4948
이번 문제에는 저번에 풀어본 소수 구하기(1929번) 문제를 참고하면 된다.
범위 안에서 소수들의 개수를 구하면 되는데,
1. 소수를 구하는 함수를 만든다.
2. n < i <=2n 의 범위 안에서 소수를 찾으면 count += 1 을 해준다.
3. count를 출력한다.
처음에 문제에서 주어진 제한 범위 (1 ≤ n ≤ 123,456)를 무시하고 for문을 돌렸더니 시간초과가 되었다.
그래서 다른 분들의 블로그를 참고하여 (2 ≤ n ≤ 246,912) 만큼의 범위를 제한해주었다.
import math
import sys
def num(num): #소수 구하는 함수 (3 5 7 11 ...)
if num == 1: #1은 소수가 아니다.
return False
else :
for i in range(2,int(math.sqrt(num))+1) :
if num%i == 0:
return False
return True
all_list = list(range(2,246912)) # 문제에서 주어진 범위
save_list=[]
for i in all_list : # 주어진 범위 안의 소수들을 찾아서 저장해놓는다.
if num(i):
save_list.append(i)
num = int(sys.stdin.readline())
while num != 0:
count = 0
for i in save_list: # 저장된 소수들 중,
if num < i <= num*2:
count += 1
print(count)
num = int(sys.stdin.readline())