[BOJ/Step9] 4948 : 베르트랑 공준 (Python)

www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

 

n까지의 수를 미리 소수 판별 후 확인
1. prime 리스트안에 False, False, True, … 를 저장한다

    -> prime의 인덱스 숫자가 소수면 True, 그렇지 않으면 False를 저장할 것이다

2. 에라토스테네스의 체를 이용한다.

  2-1. i는 2부터 2n의 제곱근까지의 순서대로 배수를 지워나갈것.

          -> i의 배수는 i로 나눠지기 때문에 소수가 아니므로 prime[i]를 False로 변경

  2-2. prime[i] 가 True일 때만 배수를 지운다 -> False는 이미 더 이전에 지워진 것이므로 배수 또한 이미 False

  2-3. i*i부터 i씩 더하면서 False로 변경. i의 2배, 3배, …, n배는 더 이전에 이미 지워졌을것이므로 i*i부터 지워나간다

3. 입력받은 n부터 2n까지 prime[n+1] ~prime[2n]의 값을 확인하여 True일 때만 count++

4. count 출력

# 4948-1.py

while True:
    n = int(input())
    if n == 0:
        break

    count = 0
    prime = [False, False] + [True] * (2*n - 1)
    for i in range(2, int(pow(2*n, 0.5) + 1)):
        if prime[i]:
            for j in range(i * i, 2*n + 1, i):
                prime[j] = False

    for i in range(n+1, 2*n+1):
        if prime[i]:
            count += 1
    print(count)

 

바로 이전의 1929 문제에서 푼 방식 그대로 문제를 풀었는데

속도가 느리던 방법은 시간초과가 되고, 속도가 빠르던 방법도 시간이 엄청 늘어났다

하지만 오히려 메모리는 줄어들었다는점.. 1929번 문제가 범위가 더 넓어서 그런것 같다

4948문제는 prime 리스트를 재사용 해서 줄어든 듯? 범위는 거의 10배 차이나니까

 

 

+ 최대 범위만큼 소수를 미리 판별해 prime에 저장하면 속도가 훨씬 빨라진다!

# 4948-2.py

N = 123456 * 2 + 1

prime = [False, False] + [True] * (N - 1)
for i in range(2, int(pow(N, 0.5) + 1)):
    if prime[i]:
        for j in range(i * i, N + 1, i):
            prime[j] = False

while True:
    n = int(input())
    if n == 0:
        break
    count = 0
    for i in range(n+1, 2*n+1):
        if prime[i]:
            count += 1
    print(count)