항해 51일) (Python 3)백준 알고리즘 4948번

베르트랑 공준

 

 

자연수 n에 대해 n < x < 2n 을 만족하는 소수 x의 수를 구하는 문제.

파이썬으로 소수를 찾는 효율적인 방법. 

에라토스테네스의 체 

에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법. 1. 1은 제거 2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. 3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다. 4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. 지워지지 않은 수 중 제일 작은 7를 소수로 채택하고, 나머지 7의 배수를 모두 지운다. (반복)

에라토스테네스의 체를 파이썬 코드로 표현하면 다음과 같다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

참고
*위키백과
에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

[파이썬] 에라토스테네스의 체 (velog.io)
2. 소수 구하기 - 에라토스테네스의 체 - 코딩으로 수학 하기 (wikidocs.net)
에라토스테네스의 체 (소수구하기. 파이썬) (tistory.com)

---

 

 

풀이 1.

에라토스테네스의 체를 이용한 풀이

def prime_list(n):
	# 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n
    
    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 / sqrt = square root 제곱근약자
    m = int(n ** 0.5)                    #  **거듭제곱  / m = math.sqrt(n)
    for i in range(2, m + 1):
        if sieve[i] == True:             # i가 소수인 경우
            for j in range(i+i, n, i):   # i이후 i의 배수들을 False 판정
                sieve[j] = False
 
     # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]
 
 
 
while 1:
    n = int(input())        #범위를 주기 위한 입력
    if n == 0:              #0 입력하면 아웃되는 조건
          break         
    li = prime_list(2*n+1)
    print(len([i for i in li if i > n]))

 

정답화면

 

함수설명

for in range

range함수: 필요한 만큼의 숫자를 만들어냄

#인수 1개 - 시작 숫자를 지정해 주지 않으면 range 함수는 0부터 시작한다.

>>> list(range(5))
[0, 1, 2, 3, 4]

# 인수 2개 - 입력으로 주어지는 2개의 인수는 시작 숫자와 끝 숫자를 나타낸다.
# 단, 끝 숫자는 해당 범위에 포함되지 않는다는 것에 주의하자.
>>> list(range(5, 10))
[5, 6, 7, 8, 9]

# 인수 3개 - 세 번째 인수는 숫자 사이의 거리를 말한다.
>>> range(1, 10, 3)
[1, 4, 7]
>>> range(20, 10, -2)
[20, 18, 16, 14, 12]

for i in range(5):
  print(i)

• for in list : 순회할 리스트가 정해져 있을 때 사용
• for in range : 순회할 횟수가 정해져 있을 때 사용

 

len()

en(s)은 입력값 s의 길이(요소의 전체 개수)를 반환하는 내장 함수. 이 함수는 입력받은 숫자에 해당되는 범위의 값을 반복 가능한 객체로 만들어 리턴한다.

list comprehension + if

리스트 컴프리헨션은if 조건문을 써서 특정 값을 걸러내서, 즉 필터링(filtering)하여 생성되는 리스트의 원소로 넣거나 뺄 수 있다. 문법은 기본 리스트 컴프리헨션의 끝에 ‘if’ 문을 넣기만 하면 돼서 매우 간단하다.

list comprehension

‘리스트를 쉽게, 짧게 한 줄로 만들 수 있는 파이썬의 기본 문법’이다. 이게 핵심이다. 리스트는 Java 등 타 언어의 ‘배열’과 매칭 되는 선형 자료구조로서 프로그래밍에서 매우 자주 활용하는 중요한 요소다. 

[ ( 변수를 활용한 값 ) for ( 사용할 변수 이름 ) in ( 순회할 수 있는 값 )]

• 변수를 활용한 값
  • 이는 앞선 코드의 ‘i * 2’에 대응된다. 배열의 각 원소에 값을 할당하는데 이 예제처럼 인덱스에 2를 곱해 할당할 수도 있고, 경우에 따라서는 제곱을 해서 할당할 수도 있다. 이렇게 ‘for’ 앞에는 실제로 할당될 값을 적는다.
• 사용할 변수 이름
  • 앞선 코드의 ‘i’에 대응된다. 파이썬의 for 문에서 ‘for’와 ‘in’ 사이에 for 블락 안에서 사용될 인자의 이름을 쓰는 것과 같다. ‘i’ 대신에 ‘n’ 등 어떤 단어를 써도 된다.
• 순회할 수 있는 값
  • 여기서 ‘순회할 수 있는 값’은 range 처럼 값을 하나씩 살펴볼 수 있는 것을 총칭한다. range 뿐 아니라 다른 리스트, set, dict, tuple 등도 될 수 있다. 일반 for문에서 쓸 수 있는 모든 값이 들어갈 수 있는 것이다. 참고로 이런 것들에는 ‘Iterable’이라는 고귀한 이름이 붙어있다.

예를 들어 자바에서 크기가 10인 배열을 생성하고, 각 원소에 인덱스에 2를 곱한 값을 할당하는 코드를 짠다고 하자. 코드는 다음과 같을 것이다.

int size = 10
int[] arr = new int[size];
for (int i = 0; i < arr.length; i++) {
    a[i] = i * 2;
}

자바를 잘 모른다면 이 코드는 정확히 예로 제시한 일을 한다고만 이해하면 된다. 똑같은 작업을 파이썬에서 해보자.

size = 10
arr = [0] * size
for i in range(len(size)):
    arr[i] = i * 2

아하, 이제 이해가 된다. arr 에는 0, 2, 4, …, 18까지의 값이 담겨있을 테다.

이게 타 언어와 파이썬에서 배열(또는 리스트)을 만드는 일반적인 과정이다. 이 짧은 코드에서는 크게 두 가지 작업이 차례로 진행된다.

1. 배열을 선언한다
   • 선언한다는 것은 배열의 크기를 정하고 배열을 특정 이름의 변수에 할당하는 것을 포함한다. 자바 같은 언어에서는 추가로 원소들이 어떤 자료형(위에서는 정수)인지까지도 선언한다.
2. 배열의 각 원소에 값을 할당한다

이때 리스트 컴프리헨션은 이 작업을 매우 간편하게 해주는 역할을 한다.

 

 

참고
*list comprehension 개인깃주소
[Python] list comprehension에 대한 즐거운 이해 - Parkito's on the way (shoark7.github.io)
*for  in 반복문, range, enumerate
파이썬 파트7. for in 반복문, range, enumerate · 초보몽키의 개발공부로그 (wayhome25.github.io)
[백준] 4948번 : 베르트랑 공준 in 파이썬 쉽게 풀기 (tistory.com)

---

 

 

★ 참고 def 문: 함수 정의 ★

파이썬에서 함수를 정의할 때는 def 문을 사용한다. def는 ‘정의하다’라는 뜻의 영어 단어 define에서 앞 글자를 딴 것이다. def 문은 다음과 같은 양식으로 작성한다. (# 뒤의 주석은 설명을 위한 것이며 양식에 포함되지 않는다.)

def 함수이름():   # ❶ 첫 행
    본문          # ❷ 함수를 호출했을 때 실행할 코드 블록

❶ def 예약어로 시작하는 첫 행에는 함수의 이름을 쓴다. 함수의 이름은 (식별자 규칙(2.2.4)에 따라) 의미를 알 수 있게 짓는다. 함수 이름 뒤에는 괄호를 붙인다.

❷ 함수의 본문은 함수를 호출했을 때 실행할 파이썬 코드다. 원하는 만큼 여러 행의 코드를 작성할 수 있으며, 각 행의 앞에 띄어쓰기를 네 번씩 해야 한다. 이것을 ‘들여 쓰기’라고 한다. 들여 쓰기는 코드의 블록(구역)을 형성한다. 나란히 들여 쓰기 된 코드 블록은 하나의 def 문 안에 포함된 코드임을 나타낸다. 들여 쓰기가 끝나면, 그 함수의 정의가 끝난다.

 

하나 더!!

( : ) 콜론

파이썬에서 블록(block)은 콜론(:)으로 시작하여 동일한 들여 쓰기(indentation) 구간을 의미하므로, 키워드의 맨 끝에도 반드시 콜론(:)을 삽입해야 한다.

 

 

 

참고
*콜론
코딩의 시작, TCP School
*파이썬 함수 정의
3.3 함수 정의하기 | 연오의 파이썬 프로그래밍 입문서 (bakyeono.net)

---

 

 

풀이 2.

comprehension 표현식 풀이   펌!! 

 

Python3 코드 풀이

1. 코드 작성에 대한 전체적인 풀이 내용

이 문제는 n이 주어지면 n보다 크고 2n보다 작은 소수의 개수를 구하는 문제이다. 시간을 절약하기 위해서 소수의 집합을 먼저 구하고서 while 반복문으로 테스트 케이스를 입력받았다. 코드에서 리스트와 집합을 생성할 대는 comprehension 표현식으로 작성하였다. 혹시라도 comprehension 표현식의 설명이 필요한 분을 위해 이전 포스팅을 링크 걸어둔다. ▶comprehension 표현식 사용 예시

 

2. 코드 상단, 차집합 연산으로 소수 집합을 생성한다. 

nums = {x for x in range(2, 246_913) if x == 2 or x % 2 ==1}
# nums = 2와 홀수로 이루어진 집합
for odd_num in range(3, int(math.sqrt(246_912))+1, 2):  # 3부터 최대값의 제곱근까지 홀수만
    nums -= {i for i in range(2 * odd_num, 246_913, odd_num) if i in nums}
    # 홀수의 배수로 이루어진 집합을 생성해서 빼줌

입력받는 자연수 n은 123456보다 작거나 같은 수이다. 그래서 2부터 2n에 해당하는 246,913까지의 자연 수에서 소수를 먼저 구했다. 이렇게 입력될 수 있는 최대한도 범위 안에서 소수를 먼저 구해놓은 이유는 소수를 구하는 식은 시간이 오래 걸리기 때문이다. n을 입력받을 때마다 매번 2n까지 범위에서 소수를 구했더니 시간 초과가 되었다.

 

먼저 2와 홀수로 이루어진 집합을 생성했다. 소수에는 2 이외에는 짝수가 없기 때문이다. 이후에 3부터 최댓값의 제곱근까지 홀수를 반복하면서 해당 홀수의 배수로 이루어진 집합을 생성해서 빼주었다. 즉 처음 생성한 nums 집합의 차집합을 구하는 방법으로 소수의 집합을 구했다. set자료형인 집합의 차집합 연산에 대해서도 작성해둔 적이 있다. 혹시라도 필요하실 분을 위해 이전 포스팅 링크를 걸어둔다. ▶set자료형 합집합, 교집합, 차집합 사용 예시

 

3. 코드 하단부, 0이 입력될 때까지 while문으로 반복한다.

while True:
    n = int(input())
    if n == 0:
        break  # n == 0 이면 반복문을 끝냄
    sosu_list = [i for i in range(n+1, 2*n+1) if i in nums]
    # 소수 집합(nums)안에서 n보다 크고 2*n보다 작거나 같은 수의 리스트를 생성
    print(len(sosu_list))

테스트 케이스의 개수가 먼저 주어지지 않고 마지막에 0이 입력되면서 문제가 끝나기 때문에 while 반복문으로 작성하였다. if조건식으로 입력받는 수 n이 0인 경우 break로 반복문이 끝나도록 했다.

 

n보다 크고 2n 보다 작은 소수의 집합은 list comprehension 표현식으로 작성하였다. 먼저 range 함수로 n+1부터 2*n까지의 숫자 범위를 생성하고 in 연산자를 사용해서 위에서 생성한 소수 집합 nums 안에 포함이 된 수를 골라서 리스트를 생성하였다. 해당 리스트의 원소 개수는 len 함수로 구했다.

 

 

참고
백준 4948 [파이썬] 베르트랑 공준 : 차집합 연산 활용 (tistory.com)
[파이썬] comprehension / list, dict, set 간편 표현식 (Python) (tistory.com)

---

 

 

 

참고

*백준 알고리즘

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