에라토스테네스의 체

Algorithm

프로그래머스 소수 찾기

https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 시간 초과 때문에 정말 힘들었다. 여러 시도를 해보며 시간을 뚫어보려 했지만 결국 이건 소수의 정의에 대한 수학적 개념이 필요하다 판단하고, 위키피디아를 참고했다. 참고하기 전까지 나의 전략이 에라토스테네스의 체와 동일하다는 것을 알 수 있었다. 3부터 주어진 숫자까지의 홀수 배열을 생성하고, 그 배열을 순회하며 소수를 만날 때마다 카운..

리차드
'에라토스테네스의 체' 태그의 글 목록