백준 4948, 소수 구하기 (에라토스테네스의 체)

문제

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

4948번: 베르트랑 공준

첫 번째 풀이

def isPrime(n):
    if n==1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True


while True:
    n=int(input())
    primelist=[]
    if n==0:
        break
    else:
        for i in range(n,2*n+1):
            if isPrime(i):
                primelist.append(i)
    print(len(primelist))

첫 번째 풀이이다 예전에 풀었던 소수 판별을 이용하여 소수인지 판별하는 isPrime 함수를 이용하여 n부터 2*n+1까지의 수를 각각 isPrime함수를 적용시켜 소수라면 primelist에 넣는 방식을 사용했지만 그렇게 하게 되면 시간초과가 발생하는 문제가 생겼다.

isPrime을 사용하는 방식은 한 개의 소수를 구할 때는 괜찮은 방식이지만 범위의 모든 소수를 구할 때는 효율적인 방식이 아니기 때문에 에라토스테네스가 제안한 소수를 구하는 방식을 사용하면 좀 더 효율적으로 소수를 판별 할 수 있다.

따라서 두 번째는 에라토스테네스의 체를 이용하여 풀이하였다.

 

두 번째 풀이

max=123456*2
primes = [False,False] + [True]*(max-1)

for i in range(2,max+1):
    if primes[i]:
        for j in range(2*i,max+1,i):
            primes[j]=False

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

여기서 에라토스테네스의 체란

범위에서 합성수를 지우는 방식으로 소수를 찾는 방식이다.

1. 1은 제거 2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. 3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다. 4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. (반복)

따라서 이를 파이썬 코드로 표현하면면

max=123456*2
primes = [False,False] + [True]*(max-1)

for i in range(2,max+1):
    if primes[i]:
        for j in range(2*i,max+1,i):
            primes[j]=False

처럼 되게 된다. 이렇게 코드로 표현하게 되면 primes에는 0부터 246912까지의 값이 소수인지 아닌지를 판별할 수 있는 도구로 사용할 수 있다.