백준 4948번: 베르트랑 공준

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

공준 이란 : 한 영역의 기본적인 전제가 되는 명제
문제만든 사람 이름인줄

n보다 크고 2n보다 크지않은 범위내에서 소수의 개수 출력하는 문제이다.

에라토스테네스의 체 를 활용해야 할 것 같다.

에라토스테네스의 체

m,n = map(int,input().split())

for i in range(m,n+1):
	if i == 1:
    	continue
    for j in range(2, int(i**0.5)+1):
    	if i % j == 0:
        break
    else:
    	print(i)

위 코드는 에라토스테네스의 체를 이용하여 m과 n사이에 소수들을 소거법으로 출력하는 알고리즘 이었다.

n을 받고, n,2n 사이에 소수들이 있으면 count를 올려주고 count를 출력해주면 될 것 같다.

import sys

def number_prime(n):
    count = 0
    for i in range(n + 1, 2 * n + 1):
        if i == 1:
            continue
        for j in range(2,int(i**0.5)+1):
             if i % j == 0:
                break
             else:
                 count += 1
                 
    print(count)

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    number_prime(n)

시간 초과가 난다.

에라토스테네스의 체 방법을 쓰되, 시간을 줄일 방법이 필요하다.

n의 범위가 123456 인것을 발견.
미리 범위를 지정해놓고 함수를 돌리는 방법이 있었다.

import sys

MAX = 123456 * 2 

# 0,1은 소수가 아니므로 0, 나머지는 소수의 의미 1로 초기화
#[0,0,1,1,1,.... ] 이런식으로 만들어 짐
check = [0] * 2 + [1] * (MAX - 1)

# 에라토스테네스의 체를 이용해 소수 판별
for i in range(2, int(MAX ** 0.5) + 1):
    if check[i]==1:
        for j in range(i * i, MAX + 1, i):
            check[j] = 0

def number_prime(n):
    count = 0
    for i in range(n + 1, 2 * n + 1):
         if check[i]:
            count += 1
    print(count)

while True:
    line = sys.stdin.readline()
    if not line:
       break
    n = int(line)
    if n == 0:
        break
    number_prime(n)

여기서
for j in range(i i, MAX + 1, i):
코드는
ii 부터 MAX까지, i 만큼 증가하며 반복하겠다는 의미.
왜 ii 부터 시작하냐면 i부터 시작한다면
만약 i=3 일때, i부터 시작하면 소수인 3도 0처리를 해주어 소수인데도 소수가 아닌 것으로 만들어버림.
i+i 부터 시작해도 오류는 없지만 2i라는 점에서 2의 배수에서 이미 처리됨

따라서 에라토스테네스의 체에서는 효율성과 정확성을 위해 ixi 부터 시작하는 것이 좋다.