(Week4)[소수찾기] 에라토스테네스의 체

 

주간 코딩스터디 때 푼 문제들을 정리하고 있습니다. 구체적인 문제에 대한 정보는 게시글 내 링크를 살펴봐주세요

소요시간: 30분

1. 문제 설명

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

2960번: 에라토스테네스의 체

에라토스테네스의 방식으로 소수를 구하지만, K번째로 지워지는 수를 출력한다. 

2. 접근 방식

• 에라토스테네스 방식을 그대로 구현하되, 중간에 값을 확인할 수 있는 변수를 넣어주고, 해당 변수가 K번째일 때의 값을 리턴시켜준다.
• 해당 문제의 경우 소수도 지우는 것도 카운팅해야 한다. 기존 에라토스테네스의 알고리즘은 소수는 살려뒀었음.

코드를 구현하고, 생각보다 코드가 깔끔하지 않아서, 코드를 리팩토링 했다.

3. 코드

1) 초기 코드

n, k = list(map(int, input().split()))
dp = [0]*(n+1)

import math
def eratos(n, k):
    count = 0
    for p in range(2, n+1):
        if dp[p] == 0:
            i = 1
            while i*p <= n:
                if dp[i*p] == 1:
                    pass
                else:a
                    dp[i*p] = 1
                    count += 1
                    if count == k:
                        print(i*p)
                        break
                i+=1
        else:
            continue
eratos(n, k)

2) 리팩토링'

n, k = list(map(int, input().split()))

import math
def eratos(n, k):
    dp = [0]*(n+1)
    for p in range(2, n+1): # 루트를 씌워서 하는 방법?
        if dp[p] == 0:
            for i in range(p, n+1, p):
                if dp[i] == 0:
                    dp[i] = 1
                    if sum(dp) == k:
                        print(i)
                        break

 

4. 코멘트

• 처음 코드보다는 깔끔해진 것 같다. while문 대신 for문에 jump를 줬고, 별도의 변수를 통해 count하지 않아서 오히려 효율성이 더 증가했다.
• 백준 기준으로 보면, 시간 복잡도와 공간복잡도가 확실히 줄었음을 확인할 수 있다.