[python]4948.베르트랑 공준

에라토스테네스 체에 대해 공부하기 싫어서 미루고 미루다 공부를 하고 코드를 짰는데 너무 안되서 대가리가 있는지 없는지도 헷갈릴정도라 힘들었던 문제다. 

leedakyeong.tistory.com/entry/%EB%B0%B1%EC%A4%80-4948%EB%B2%88-%EB%B2%A0%EB%A5%B4%ED%8A%B8%EB%9E%91-%EA%B3%B5%EC%A4%80-in-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%89%BD%EA%B2%8C-%ED%92%80%EA%B8%B0

[백준] 4948번 : 베르트랑 공준 in 파이썬 쉽게 풀기

여기 이 블로그의 코드를 보면서 이해하느라 뒤질뻔했다.

요즘 대가리가 너무 안돌아가서 스트레스였는데 간신히 이해했다.

여기 블로그의 코드를 바탕으로 설명해보겠다.

 

def primeop(end):
    list_p = [True]*end
    m = int(end**0.5)
    for i in range(2, m+1):
        if list_p[i]==True:
            for j in range(i+i, end ,i):
               list_p[j]=False
                
    return [i for i in range(2, end) if list_p[i] == True]
 
 
while True:
    n = int(input())
    if n==0: break
    li=primeop(2*n+1)
    print(len([i for i in li if i > n]))
 
 

 

12번째 줄부터 설명해 보자면,while True로 해놓아 입력값이 0 이기 이전까지 무한 반복 시켰다. 입력값이 0이면 break를 하여 실행 종료 시키고, 입력값이 0이 아니라면 primeop함수를 실행시켰다.

primeop함수를 보면 입력값보다 크고 입력값*2보다 같거나 작은 수 중 소수가 몇개인지 골라내야 하기 때문에 primeop함수의 매개변수인 end에 2n+1을 (이때의 n은 입력값) 넘겨주었다. 그럼 함수 primeop에서는 입력값의 2배개수의 원소를 가진 리스트가 필요한데, 리스트 같은 경우 인덱스가 0부터 시작되기 때문에 1을 더 더해준 개수대로 원소를 가진 리스트를 만들어주었다. 초기값으로는 True로 일단 다 소수라고 임시로 정해놓았다. 그런 다음 3번째 줄 을 보면

m = int(end**0.5)

이것을 했다. end에 0.5제곱 즉 루트 end을 값을 넣어주었다.  

어떤수가 소수인지 아닌지를 판별하기 조금 간단한 방법으로는 해당 수 x가 2부터 x의 제곱근(루트 x)가지 의 수들을 나눠봐서 나누어 떨어지는 수가 있으면 소수가 아니고 나누어떨어지는 수가 존재하지 않으면 그 수 x는 소수이다. 이 로직을 사용하여 만든 코드이다. 이로직으로 소수인지 아닌지  입력값보다 크고 입력값*2보다 같거나 작은 수 들을 각각 판별해서 소수가 아닌 수인 인덱스의 값을 False값으로 변경을 해준다.  그리고 다 판별 했으면 list_p의 인덱스가 2부터 끝까지 value가 True인 인덱스만 새로운 리스트에 모아서 그 리스트를 리턴 해준다.

그리고 다시 이 함수를 호출했던 15번째 줄에서 리턴된 리스트를 li에 넣어준다. 그러면 li에는 2부터 입력값*2사이의 수중 소수라고 판명된 인덱스 값만 들어있다. 이 들중 입력값보다는 커야 하기 때문에 이들을 다시 분리하여 출력해준다.

 

이해를 돕기위해 입력값을 10으로 하고 li리스트를 출력해보면,

이 상태인데 10보다는 크고 20보다 같거나 작은 소수의 개수를 구해야하니까 11, 13,17,19이렇게 4를출력하면 된다.

 

 

www.acmicpc.net/problem/4948

출처:leedakyeong.tistory.com/entry/%EB%B0%B1%EC%A4%80-4948%EB%B2%88-%EB%B2%A0%EB%A5%B4%ED%8A%B8%EB%9E%91-%EA%B3%B5%EC%A4%80-in-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%89%BD%EA%B2%8C-%ED%92%80%EA%B8%B0