[백준] 4948번 베르트랑 공준 - 파이썬(Python)

2021. 1. 31. 19:33· 알고리즘/문제풀이
목차
  1. 문제 (링크)
  2. 나의 풀이
728x90

문제 (링크)

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

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

나의 풀이

첫 번째 풀이

 

import sys
import math

data = []

while True:
    n = int(sys.stdin.readline())
# 입력값이 0이 아닐때까지 입력값을 data배열에 저장
    if n == 0:
        break
    else:
        data.append(n)
    
def is_prime_count(x, y): # x이상 y이하의 수 중 소수인 것의 개수 리턴해주는 함수
    arr = [True for _ in range(y+1)]
    arr[1] = False

    for i in range(2, int(math.sqrt(y)) + 1):
        if arr[i]:
            j = 2
            while i * j < y:
                arr[i*j] = False
                j += 1

count = 0
for i in range(x, y):
    if arr[i]:
        count += 1

return count

for x in data:
    print(is_prime_count(x+1, x*2+1)) # x보다 크고 2x보다 작거나 같은 값 사이의 소수의 개수

 

가장 기본적인 에라토스테네스의 체 알고리즘을 이용해 문제를 해결하였다.

 

문제가 n초과 2n이하의 숫자들 사이의 소수의 개수를 출력하는 것이었는데, n이상으로 착각을 해서 계속 실패판정이 났었다.

 

문제를 잘 읽자..

 

위 코드로도 성공을 했지만, 풀고나서 한 가지 생각이 들었다.

 

어차피 arr[i]는 숫자 i가 소수인지 아닌지를 저장해주는 배열인데, 이걸 굳이 매번 함수를 돌릴 때마다 초기화했다가 다시 채워줄게 아니라, 입력 범위 내의 모든 숫자들에 대한 arr[i] 값을 구해놓고 입력값에 대해 갯수만 세면 훨씬 더 효율적일거란 생각이 들었다.

 

따라서 그러한 방식으로도 코드를 작성해봤다.

 

두 번째 풀이

import sys
import math

data = []

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    else:
        data.append(n)

# 입력 n의 범위는 1 <= n <= 123456 이므로, 2n의 값까지 y를 설정
y = 123456 * 2
arr = [True for _ in range(y+1)]
arr[1] = False

for i in range(2, int(math.sqrt(y))+1):
    if arr[i]:
        j = 2
        while i * j <= y:
            arr[i*j] = False
            j += 1


for x in data:
    count = 0 # data의 각 값들에 대한 count 초기화

    for i in range(x+1, 2*x+1): # x초과 2x이하까지 i가 돈다
        if arr[i]: # arr[i]가 True면 (소수이면)
            count += 1 # 카운트에 1 추가

print(count)

 

입력값으로 들어오는 n 은 1 이상 123456 이하이므로, 최대 범위가 될 수 있는 값은 2n일 경우의 123456 * 2이다.

 

따라서, arr를 123456 * 2의 범위만큼 설정해주고 소수 여부를 처리해줬다.

 

이후, data의 값들을 돌면서 x 초과 2x 이하에 대한 count를 계산해주는 방식을 거쳤다.

 

 

 

 

위에 것의 두 번째 풀이, 밑에 것이 첫 번째 풀이

 

두 풀이 모두 통과판정을 받았지만, 걸린 시간 차이가 6배로, 엄청난 시간적 차이를 보였다.

 

 

저작자표시 (새창열림)

'알고리즘 > 문제풀이' 카테고리의 다른 글

[백준] 1806번 부분합 - 파이썬(Python)  (0) 2021.02.02
[백준] 2003번 수들의 합2 - 파이썬(Python)  (0) 2021.02.01
[백준] 1929번 소수 구하기 - 파이썬(Python)  (0) 2021.01.31
[백준] 1463번 1로 만들기 - 파이썬(Python)  (6) 2021.01.26
[백준] 1978번 소수 찾기 - 파이썬(Python)  (1) 2021.01.26
  1. 문제 (링크)
  2. 나의 풀이
'알고리즘/문제풀이' 카테고리의 다른 글
  • [백준] 1806번 부분합 - 파이썬(Python)
  • [백준] 2003번 수들의 합2 - 파이썬(Python)
  • [백준] 1929번 소수 구하기 - 파이썬(Python)
  • [백준] 1463번 1로 만들기 - 파이썬(Python)
SeongOnion
SeongOnion
서버는 꺼지지 않아요
SeongOnion
조무래기 코딩
SeongOnion
전체
오늘
어제
  • 분류 전체보기 (166)
    • 알고리즘 (81)
      • 이론 (8)
      • 문제풀이 (73)
    • 언어 (15)
      • Python (9)
      • JavaScript (1)
      • JAVA (5)
    • 데이터베이스 (5)
    • 프레임워크 (15)
      • Django (7)
      • Spring (8)
    • 그 외 공부 (37)
      • 운영체제 (1)
      • 자료구조 (14)
      • 네트워크 (5)
      • CS (2)
      • 기타 (6)
      • 트러블 슈팅 (9)
    • 프로젝트 (0)
    • 개발자취 (8)
    • 회고 (3)
    • 주저리주저리 (1)
    • 기타 (비개발) (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BFS/DFS
  • 큐
  • 브루트포스
  • 그리디알고리즘
  • 프로그래머스
  • 회고
  • 오픈소스
  • spring
  • 스택
  • Django
  • 개발자
  • 코딩테스트
  • 알고리즘
  • 소수
  • 웹
  • 컨트리뷰트
  • BFS
  • 파이썬
  • 장고
  • DRF
  • 데이터베이스
  • 에라토스테네스의 체
  • 자바
  • 정렬 알고리즘
  • DP
  • 트러블 슈팅
  • 코딩
  • 백준
  • 투 포인터 알고리즘
  • 이진탐색

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
SeongOnion
[백준] 4948번 베르트랑 공준 - 파이썬(Python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.