소수 찾기(프로그래머스 level1, 에라토스테네스의 체, 파이썬)

프로그래머스 소수 찾기(프로그래머스 level1, 에라토스테네스의 체, 파이썬) KQNG 2018. 9. 20. 14:13 이웃추가 본문 기타 기능 이번에 포스팅할 문제는 프로그래머스 코딩테스트 연습의 1단계인 소수 찾기 라는 문제입니다. level1에 있는 문제라서 그냥 가볍게 문제를 풀려고 했지만 제출 시 효율성 테스트가 있는 걸로 보아선 에라토스테네스의 체를 적용해야될 것으로 생각됩니다. 문제는 다음과 같습니다. n까지의 숫자를 받으면 1부터 n 까지 몇개의 소수가 있는지를 확인해주는 문제입니다.

이 문제를 풀기 위해선 에라토스테네스의 체 진행 과정을 알아야합니다. (1) 2를 선택하여 2의 배수들을 모두 제거해줍니다. (2) 그 다음 제거되지 않은 숫자를 기준으로 그 숫자의 배수들을 모두 제거해줍니다. 이러한 과정을 수행하였을 때 제거되지 않고 남아있는 숫자가 소수가 되게 됩니다.

GIF가 더 자세히 들어간 친절한 설명은 제 블로그에 이전의 올렸던 아래 링크를 확인하시면 됩니...

요청 처리 중입니다...

소수 찾기(프로그래머스 level1, 에라토스테네스의 체, 파이썬)

등록된 다른 글