[4948] 베르트랑 공준 / 파이썬 (다시풀어보기)

 

 

 

저기요................ 다시 도전하겠소!!!!!!!!!!!!!!

진지 궁서체요!

 

 

 

문제 링크: https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

---

❌ 1차시도 실패

에라토스테네스의 체 & count 조합으로 구현해보려고 했는데.... 시간초과...........😕

#시간초과 (실패)---------------------------------------
 
#n과 2n사이의 소수
#False 카운트 방법
 
#소수 - 에라토스테네스의 체
import math
 
def prime(x):
    array=[True for i in range(x+1)]
    array[0]=False
    array[1]=False 
    if x==1: return 1
    for i in range(2,int(math.sqrt(x))+1):
        if array[i]==True:
            j=2
            while i*j<=x:
                array[i*j]=False
                j+=1
    return array.count(True) 
 
#기본 정보 입력받기
from sys import stdin
while True:
    n=int(stdin.readline())
    if n==0:
        break
    elif n==1:
        print(1)
        continue
    #정답 도출
    print(prime(2*n)-prime(n))

---

❓ 정답은 ??

#문제 포인트!!!!!
#n의 값이 1 ≤ n ≤ 123,456 제한 되어있으니
#미리 123456값까지 소수를 구해놓는것!!!
 
max = 123456 # n의 범위의 최댓값
 
#소수 판별을 위한 리스트array 설정(소수는 True, 아니면 False)
array = [True for _ in range(2*max+1)] 
 
#0과 1은 미리 False 설정
array[0], array[1] = False, False 
 
# 에라토스테네스의 체 공식
import math
#2부터 int(math.sqrt(2*123456) 인덱스까지 확인
for i in range(2, int(math.sqrt(2*max)+1)): 
    
    if array[i]==True:
        j=2 
        while i*j <= 2*max: #i*j 가 2*123456 보다 작거나 같다면
            array[i*j]=False #해당 i*j의 값은 소수가 아니므로 False로 설정
            j+=1 #j를 1씩 증가
 
# 기본정보 입력 및 답 출력
while True:
    n = int(input())
    if n == 0: #0이면 반복문 탈출
        break
    
    #array 슬라이싱하고 count!
    print( array[n+1 : 2*n+1].count(True) )

---

💯 풀이 과정

어제 풀었던 방법으로 풀기 싫어서 다른 분들의 답을 찾아보았는데, WOW!!!!!😮

엄청 다양했다..... 다른 사람들의 지식을 모아모아

쉽고 간단하고 시간 안잡아먹는 코드 식이 뭐가 있을까 봤다.

 

1) 보니까 다들 문제에서 주어지는 n의 최대값 123456까지의 소수를 미리 구해놓고 그 다음 카운트를 하는 것이었다!

(123456정도의 숫자는 미리 리스트를 구해놓아도 괜찮은 가 보다...)

2) 카운트함수로 소수(True) 개수세면 끝!

---

😎오늘의 한줄평: 역시나.... 다시 풀어도 다른 코드.... 시간초과가 나오기도하고... 결국 답을 찾았다.

 

..... 리스트를 미리 생성해놓는게 빠른거였다니! VS CODE에서 작성 후 제출하기 전 미리 복잡도 체크부터 해야겟다.