4948번 베르트랑 공준

 

 

1) 사이트

4948번: 베르트랑 공준

 

 

 

2) 문제

간단히 예로 들어 설명하자면 2를 입력받으면,

2~2*2 안의 소수가 몇 개 존재하는지 찾으라는 문제입니다.

문제 푸는데 계속 <시간초과>가 걸려서 정답 코드 찾아가며 이해하고 결과보는데 3시간 걸렸던 문제입니다 ㅠㅠ

 

시간초과의 문제는 한 번에 너무 많은 것을 하는 나의 코드 탓이었는데요...

저는  하나의 숫자를 입력받을 때마다 그 숫자마다 소수인지 판별하고, 결과값에 하나 추가하는 식으로 짰었습니다.

하지만 이번 문제는 범위가 1~123,456으로 정해져 있는 만큼 이 범위 내 소수 값을 미리 구하고, 숫자를 입력받을 때마다 n~2n 범위의 수가 몇 개인지만 찾아주면 쉽게 풀 수 있는 문제입니다.

 

제가 참고했던 사이트를 알려드릴게요!

백준 4948번 베르트랑 공준 - Python

 

 

 

3) 파이썬 코드

import math
#1. 소수를 구하는 함수
def isPrime(number):
    for i in range(2,int(math.sqrt(number))+1):
        #1은 소수가 아니다.
        if int(number)==1:
            return 0
        #합성수면 제거
        elif(number%i==0):
            return 0
    return number

#2.주어진 범위안 소수 찾기
matrix=list(range(2,123456*2))

#remove로 지우면 매트릭스 지운자리를 매우려고 뒤에 수들이 붙는 시간이 추가되기 때문에 그냥 새로운 리스트에 추가하는 것이 빠를 것 같다
prime_num=[]

isZero=0
for i in matrix:
    isZero=isPrime(i)
    if isZero!=0:
        prime_num.append(isZero)
        
number=1        
result=0
#3. 완성된 소수 매트릭스를 가지고 범위에 소수의 수를 세준다.
while(number!=0):
    number=int(input())
    for i in prime_num:
        #사이수를 넘어가면 멈춰라
        if 2*number<i:
            break
        # i==7 number==5 / 5<7<=10
        elif number<i and 2*number>=i:
            result=result+1
    if(number!=0):
        print(result)
    result=0

3-1) 선수 지식

파이썬 코드를 이해하기 위해 알아야 할 선수 지식이 있습니다.

 

1. sqrt, 제곱근 쓰는 방법

>import math

>math.sqrt(숫자)

 

2. for문 없이 리스트에 1~n까지 숫자 넣는 방법

>리스트변수=list(range(1,n+1))

 

3. 리스트에 값을 추가하는 방법

>list변수.append

추가로 list에 값을 추가하고, 삭제하고, 삽입하는 방법을 잘 정리해둔 블로그 링크를 공유드립니다!

[파이썬]리스트 목록 추가,삭제(append,insert,extend,pop,del,remove,clear)

 

 

 

3-2) 설명

 

1. 소수를 구하는 함수를 만듭니다.

import math
#1. 소수를 구하는 함수
def isPrime(number):
    for i in range(2,int(math.sqrt(number))+1):
        #1은 소수가 아니다.
        if int(number)==1:
            return 0
        #합성수면 제거
        elif(number%i==0):
            return 0
    return number

이 문제를 풀면서 소수를 구하는 법 정확하게 이해했는데요.

그동안 풀었던 문제들에서 소수구하는 방식은 반만 알았던 지식이라는 것을 깨달았습니다 ㅎㅎ...

 

소수인지를 판별하는 방법은 <에라토스테네스의 체>를 이용하는 방법이죠.

2~루트(숫자)까지의 숫자로 나눠지지 않으면 소수입니다.

 

그동안은 2가 들어가면 소수 아니라고 나오는 것 아닌가 걱정해서 1~16 아래의 수는 따로 일일히 로직을 짰는데요.

다시 천천히 들여다보니 2, 3, 5, 7은 루트를 거치면 1.xx~2.xx가 되므로 for문을 돌지 않고 빠져나와 number를 리턴한다는 것을 위의 함수에서 짜면서 깨달았네요 ㅠㅠ

 

2. 문제에서 주어진 범위 내 소수를 전부 찾아 리스트에 넣어줍니다.

#2.주어진 범위안 소수 찾기
matrix=list(range(2,123456*2))

#remove로 지우면 매트릭스 지운자리를 매우려고 뒤에 수들이 붙는 시간이 추가되기 때문에 그냥 새로운 리스트에 추가하는 것이 빠를 것 같다
prime_num=[]

isZero=0
for i in matrix:
    isZero=isPrime(i)
    if isZero!=0:
        prime_num.append(isZero)

문제의 범위는 1~123,456이지만, 사실상 1은 소수가 아니므로 넣지않고, n~2n까지 검사해야하기 때문에

2~123,456*2까지 검사해주면 됩니다.

 

그리고 이 수들을 전부 isPrime 함수에 넣고 소수만 골라내어 새로운 리스트(prime_list)에 넣습니다.

사실 remove로 할까했지만, [1 2 3 4 5]리스트가 있다고 쳤을 때 3을 없애면 그 자리를 매우기 위해 4, 5가 앞으로 움직이는 시간도 추가될 것 같기에 (c언어 배울 때 배운 것이지만...ㅎ) 차라리 새로운 리스트에 값을 추가하는 게 시간이 덜걸릴 것이라 생각했습니다.

 

공간을 소비하고 시간을 아낀다...!

 

3. 입력받은 숫자가 n일 경우 n~2n까지 소수가 몇개있는지 출력한다.

#3. 완성된 소수 매트릭스를 가지고 범위에 소수의 수를 세준다.
number=1        
result=0
while(number!=0):
    number=int(input())
    for i in prime_num:
        #사이수를 넘어가면 멈춰라
        if 2*number<i:
            break
        # i==7 number==5 / 5<7<=10
        elif number<i and 2*number>=i:
            result=result+1
    if(number!=0):
        print(result)
    result=0

위에서 이미 완성한 prime_list만 있으면, 어떤 숫자가 들어오든 추가 시간 들이지 않고, 결과를 출력할 수 있습니다.

for문을 돌다가 2n을 넘어가면 멈추는 것도 시간을 단축하는 방법입니다 : )

 

 

 

4) c언어

없음

 

 

---

궁금한 점이나 공유할 정보가 있다면 댓글로 남겨주세요 *^^*

끝!