백준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하나씩 삭제하여서 풀었다.
- 2부터 n까지의 수를 저장할 arr배열을 선언하였다.
- 이 메인배열인 arr을 시작으로 첫번째 원소 즉, 소수를 찾고 해당 배수를 지울건데 while문을 이용해서 arr 배열의 길이가 0이되면 원소 삭제를 그만두게끔 한다.
- while 반복문 내에선 arr[0]은 소수이므로 해당 소수의 배수를 저장할 newArr배열을 선언한다.
- newArr배열을 하나씩 돌면서 arr배열에서 newArr배열의 원소들을 삭제한다.
- arr원소에서 하나씩 삭제할때 마다 result값을 1씩 증가한다.
- 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:
문자체가 성능이 좋지 않다고한다. 이 부분도 아쉽다생각한다.
Author And Source
이 문제에 관하여(백준2960-에라토스테네스의 체), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yjs3819/백준2960-에라토스테네스의-체저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)