[백준-파이썬] 4948: 베르트랑 공준

1년 전에 틀렸던 문제를 풀어봤다. 이번에는 과거의 나에게 알려주는 말투로 적어보려고 한다. ㅎㅎ 만우절이니까..ㅎㅎ 

문제 보러 가기

4948번: 베르트랑 공준

안녕! 베르트랑 공준 문제구나. 와 저런 수학적인 명제가 있다니 정말 놀랍네.
음 이 문제는 뭐가 포인트일까? 맞아 맞아~ 소수를 구하는 게 포인트겠지~

너는 어떻게 풀었는지 볼까?

while True:
    n=int(input())
    if n == 0: exit()
    for i in range(n+1,2*n+1):
        if n==1: print("1")
        elif i%2==1:
            S=[2,3]
            for j in range(len(S)):
                if i % S[j] == 0: break
                else:
                    if j == len(S) - 1: S.append(i) #리스트 S에 소수 넣음
        # 2*n미만인 소수를 리스트 A에 넣기
            A = []
            for o in S:
                 if 2*n > o:
                     A.append(o)
         # 리스트 S에서 리스트 A를 빼는 것처럼 하기 - n초과 2*n이하
            B = []
            for i in S:
                if i not in A: B.append(i)
            print(len(B))

음.. 열심히 풀었구나 ^^ 그런데 예제를 입력하니 0만 계속 찍히네??.. ^^

그럴 수 있지 괜찮아.

응 일단 0이 나올 때까지 ..니까 0이 나오면 exit을 해주는 구나. 오. 나는 요즘 exit 잘 안쓰는데 이런 게 있었네. 이게 뭐였지? 와 아예 파이썬 프로그램을 종료하는구나. 그리고 0이 아니라면 for문으로 들어가는 구나. 그 수를 n으로 두고, n초과 2*n 이하의 수를 i로 쭉 보는구나. 그리고 소수를 구해서 S에 넣고, 리스트 A에 2*n보다 작은 소수를 넣고, 리스트 S에 속하는데 A에 속하지 않는 소수를 리스트 B에다가 모우는 구나. 와 시간이 오래 걸리겠는걸..? 

음.. 의도는 대충 알겠지만.. 방향이 좀 잘못된 거 같은데..

일단 이럴 때는 소수를 먼저 구하는 게 좋아. 여러 개의 테스트 케이스가 오잖아. 테스트에서 n이 다 123456이면 매번 거기까지 소수를 구해야 하는데 오래 걸리잖아? 그러니까 123456*2+1까지 소수를 구해두자고~~ 왜냐면 n은 123456까지 오는데, 우리는 (n보다 크고) 2*n보다 작거나 같은 소수의 개수를 구하면 되니까! 2*n까지의 수만 보면 되잖아. 

이때 에라토스테네스의 체 방법을 사용할거야. 그게 뭐냐고? 체처럼! 소수를 구하면, 자기 자신을 제외하고, 그 소수의 배수들을 쭉 없애주는 거야~~ 일단 우리는 246913까지 소수인지 아닌지 봐주기로 했지? 그러니까 sosu리스트를 False로 해서 0~ 246913까지 만들어줬어. 그리고 가장 작은 소수인 2부터 봐줄게. 2가 소수 잖아? 그럼 2 빼고 2의 배수들을 다 True로 바꿔줘. 그 다음에 i를 1씩 증가해 봐. 만약 sosu[i]가 False라면 i는 소수일까? 아닐까? i는 소수지. 왜냐면, i는 그 이전 소수들의 배수가 아니니까 지금까지 sosu[i] = False로 남아있는 거잖아. 만약 i가 소수라면 그 수만 빼고, 그 수의 배수를 sosu 리스트에서 True로 바꿔줘. 예를 들어서 i가 3이면, 3은 소수이지. sosu[3]은 False로 남아있어. 그리고 3보다 큰 3의 배수들 즉  6, 9, 12, 15...... 3의 배수니까 소수가 아니게 되잖아. 그래서 sosu[j]=True로 바꿔줘.

아. 6, 12는 2의 배수라서 이미 True일텐데 왜 또 True로 바꾸냐고? 맞아~~ 물론 6, 12는 이미 2의 배수라서 sosu[6], sosu[12]는 True가 되긴 했겠지.. 그렇지만 if를 해서 체크하면, 또 그만큼 시간이 걸리니까 그냥 안해줬어. 그래도 한번 해보자고?? 그랭.

짠. 맨 위에 있는 것과 두번째 것은 if로 sosu[j]가 False인지 아닌지 체크하는 부분만 다른 코드야. 어.. 조금 차이나기는 하네.. 그래도 수가 커지면 더 차이가 날 수도 있을 걸..?!!

아무튼 이 작업을 i가 2일 때부터 246914일 때까지 쭉~ 하면 돼. 그러고 나면 이제 sosu[m]이 False이면 m은 소수이고, sosu[m]이 True이면 소수가 아닌 거지!!

이렇게 소수를 구한 후에는 각 테스트 케이스를 봐줘. 만약에 0이라면, 네가 해준 것처럼 exit()를 해서 프로그램을 끝내면 되겠지. 넘 잘했어 ~~ 굳굳~~

그게 아니라면 sosu의 인덱스를 n+1부터 2*n까지 봐주면서, 값이 False인 것의 개수를 세면 돼. 리스트 컴프리핸션으로 한 줄로 가능하지! 아 리스트 컴프리핸션이 뭐냐고? 어 조건문이나 반복문을 한 줄로 쓸 수 있는 거야.. 이렇게 하면 무슨 무슨 원리로 시간도 단축된대..! [(변수를 어떻게 쓸건지) for (변수) in (순회할 대상) if (조건문)] 형식으로 쓰면 돼. 그러면 조건문이 참일 때, 순회하는 대상의 변수를 하나씩 보면서 '변수를 어떻게 쓸건지' 형태를 모아서 리스트를 만들어줘. 예를 들어서 [ i*2 for i in range(10) if i%2==1]이면 어떻게 될까? i를 0부터 9까지 하나씩 보면서, i가 홀수일 때 i에 2를 곱해서 리스트를 만들겠지? 그러면 [2, 6, 10, 14, 18] 이렇게 되겠네.

짠 완성된 코드~~

# 먼저 소수 구하기
sosu = [False] * 246914
i = 2
while i < 246914:
    if sosu[i] == False:
        for j in range(i * 2, 246914, i):
            sosu[j] = True
    i += 1

while True:
    n = int(input())
    if n == 0: exit()

    ans = 0
    print(sum([1 for k in range(n + 1, n * 2 + 1) if sosu[k] == False]))

아 리스트 컴프리핸션 잘 모르겠다고? 그래 그러면 for문으로 풀어서도 써둘게 ^^ 리스트 컴프리핸션은 나중에 봐봐. 이 블로그에서 잘 설명해주셨더라! https://shoark7.github.io/programming/python/about-list-comprehension-python

코드는 아래와 같아~ 고생했어~ 

# 먼저 소수 구하기
sosu = [False] * 246914
i = 2
while i < 246914:
    if sosu[i] == False:
        for j in range(i * 2, 246914, i):
            sosu[j] = True
    i += 1

while True:
    n = int(input())
    if n == 0: exit()

    # 이 부분을
    ans = 0
    for k in range(n + 1, n * 2 + 1):
        if sosu[k] == False:
            ans += 1
    print(ans)

    # 아래 한 줄로 가능
    # print(sum([1 for k in range(n + 1, n * 2 + 1) if sosu[k] == False]))

(544ms는 리스트 컴프리핸션으로 한 버전, 720ms는 아닌 버전)