백준 - 4948 - 베르트랑 공준 - Python/소수 구하기

4948번: 베르트랑 공준 (acmicpc.net)

4948번: 베르트랑 공준

문제

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

제한

• 1 ≤ n ≤ 123,456

 

풀이

import math

def IsPrime(num): #소수인지 판별하는 함수
    a = int(math.sqrt(num)) # 루트2 루트3 루트4(2) 루트 5 루트 6
    if num == 1:
        return False
    else:
        for i in range(2, a+1):
            if num % i == 0: 
                return False
        return True

Num_list = list(range(2,246912)) #미리 뽑아 버린다 소수를
Sort_list = []
for i in Num_list: # 위에 함수에 들어갈 수를 반복문으로
    if IsPrime(i): #
         Sort_list.append(i) #소수인 것만 넣어라

while True:
    n = int(input())  #범위설정
    if n == 0:
        break
    cnt = 0
    for i in Sort_list: # 소수 뽑은 리스트를 반복문으로 하나씩 꺼낸다
        if n < i <= n*2: # 반복문으로 꺼낸수가 n과 2n 사이에 있으면
            cnt += 1 # 카운트를 1씩 올리자
    print(cnt)     

 

처음 오류 떴던게 범위 맞출 때 

 for i in range(n+1,2*n+1): 요거를

 for i in range(n+1,2*n):로 해서 1일 때 0이 출력되었다. 

*for i in range(첫값,끝값) : 첫값부터 끝값 -1 이기 때문에 +1을 해줘야한다

 

이 코드도 python으로 하면 시간초과 뜨고 pypy로 해야 맞게 나오는데 그 이유를 모르겠어서 질문해보니

'매번 소수를 구할 때마다 에라토스테네스의 체를 사용하는 것은 비효율적입니다.
한번만 사용해서 모든 소수를 구한 다음에, 해당 배열 값이 True인지 확인하면 시간 초과는 뜨지 않을 것입니다.'

라고 한다.

귀찮으니까 다음부턴 이렇게 해보는걸로 ㅎ

 

<내 풀이>

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

    array=[True for n in range(2*n+1)] #처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

#에라토스테네스의 체 알고리즘
    for i in range(2, int(math.sqrt(2*n))+1): #2부터 n의 제곱근까지의 모든 수를 확인하며
        if array[i]==True: #i가 소수인 경우(남은 수인 경우)
        #i를 제외한 i의 모든 배수를 지우기
            j=2
            while i*j<=2*n:
                array[i*j]=False
                j+=1 
#모든 소수 출력

    for i in range(n+1,2*n+1):
        if array[i]:
            cnt+=1

    print(cnt)   

 

 

사용된 개념

<이코테> APPENDIX B p.466 참고

저번주에 소수 문제 이해 안됬는데 책 읽고 다시 보니까 코드가 이해가 간다! 다시 풀어보는 것 좋은듯 저번주꺼 ㅎㅎ

 

 

-소수의 판별

#소수 판별 함수
import math

def is_Sosu(x):
    #2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2,int(math.sqrt(x)+1):
        #x가 해당 수로 나누어떨어진다면
        if x%i==0:
            return False #소수가 아님
    return True #소수임


print(is_Sosu(4))
print(is_Sosu(7))

 

위에껀 하나의 수에서만 대해서 소수인지 아닌지 판별해야 하는 경우였고 수의 범위가 주어졌을 때는 어떻게 할까?

 

-에라토스테네스의 체

p.468

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘임.

에라토스테네스의 체는 N보다 작거나같은 모든 소수를 찾을 떄 사용할 수 있음. 

 

1) 2부터 N까지의 모든 자연수를 나열한다.

2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.

3) 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다)

4) 더 이상 반복할 수 없을 때까지 2)번과 3)번의 과정을 반복한다.

 

이렇게 2부터 26까지의 모든 소수를 찾았다. 

2 3 5 7 11 13 17 19 23

import math
n=10 #2부터 100까지의 모든 수에 대하여 소수 판별
array=[True for i in range(n+1)] #처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

#에라토스테네스의 체 알고리즘
for i in range(2, int(math.sqrt(n))+1): #2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i]==True: #i가 소수인 경우(남은 수인 경우)
        #i를 제외한 i의 모든 배수를 지우기
       j=2
       while i*j<=n:
           array[i*j]=False
           j+=1 
#모든 소수 출력
for i in range(2,n+1):
    if array[i]:
        print(i,end=' ')       

 

-코드 효율화 예시

joychae.tistory.com/m/14

[항해99] 2주차 알고리즘 실전 (D+12) / 시간 복잡도, 코드 효율화