백준2960-에라토스테네스의 체

백준 2960 에라토스테네스의 체

소수를 쉽게 구하는 방법을 알게되었다.

• 코드

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

arr = [i for i in range(2, n + 1) ]

result = 0;
answer = ''

while len(arr) > 0:
    pm = arr[0] # 이게 소수임.
    # arr[0]의 배수들을 저장할 새 배열 newArr
    # round(n / pm) + 1은 배수의 개수이다. 예를들면 1부터 10까지의 2의배수의 개수는 10 / 2 로 5개
    newArr = [pm * i for i in range(1, round(n / pm) + 1)]
    for i in range(len(newArr)):
        print(arr)
        if newArr[i] in arr:
            print('삭제되는 값: ', newArr[i])
            result += 1
            arr.remove(newArr[i])
            if result == k:
                answer = newArr[i]
                break

print(answer)

# 나는 배열 총 두개를 이용해서 풀었따.
# 메인 배열 arr하나
# 그리고 삭제된 소수의 배수 배열 newArr
# 메인배열에서 newArr하나씩 삭제하여서 풀었다.

1. 2부터 n까지의 수를 저장할 arr배열을 선언하였다.
2. 이 메인배열인 arr을 시작으로 첫번째 원소 즉, 소수를 찾고 해당 배수를 지울건데 while문을 이용해서 arr 배열의 길이가 0이되면 원소 삭제를 그만두게끔 한다.
3. while 반복문 내에선 arr[0]은 소수이므로 해당 소수의 배수를 저장할 newArr배열을 선언한다.
4. newArr배열을 하나씩 돌면서 arr배열에서 newArr배열의 원소들을 삭제한다.
5. arr원소에서 하나씩 삭제할때 마다 result값을 1씩 증가한다.
6. result가 k(입력값)과 같으면 answer에 저장하고 break을 걸어서 while문을 빠져나온다.

느낀점

• 파이썬으로 알고리즘을 처음하여서 입출력하는데 생각보다 힘들었다.
• 파이썬이 익숙치않아서 더 좋은 계산법이 있다고 생각한다.
• 아쉬운 부분은 while문이 돌때마다 newArr배열이 새로만들어지는데 이전의 newArr과 새로만들어진 newArr의 원소가 겹치는 부분이 많다. ex) 첫번째 newArr = [2, 4, 6, ...], 두번 째 newArr= [3, 6, 9, 12 ...] 벌써 6과 12가 겹친다. 이렇게 되면 더 시간이 오래걸릴수밖에 없다 생각한다.

아쉬운부분 수정

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

arr = [i for i in range(2, n + 1) ]

result = 0;
answer = ''

while len(arr) > 0:
    pm = arr[0] # 이게 소수임.
    i = 1
    while pm * i < n + 1:
        if pm * i in arr:
            result += 1
            arr.remove(pm * i)
            if result == k:
                answer = pm * i
                break            
        i += 1

print(answer)

newArr배열을 새로만들지 않고 그냥 바로바로 삭제하면서 나아갔다. 이렇게하면 일단 불필요한 배수의 배열을 만들지 않고 겹치는 배수의 수도 if pm * i in arr: 조건문에서 걸리기 때문에 더 좋다생각한다.

그런데 pm * i in arr: 문자체가 성능이 좋지 않다고한다. 이 부분도 아쉽다생각한다.