반응형
소수 목록 구하기
소수는 약수가 1과 자기 자신뿐인 수를 말한다.
그래서 소수는 2, 3, 5, 7 등이다.
4는 약수가 1, 2, 4라 소수가 아니다.
10까지 소수를 구하라는 문제가 있을 때, 가장 쉽게 떠오르는 방식은 소수의 정의대로 2부터 시작해서 자기 자신보다 작은 수까지 쭉 나눠보는 거다.
2는 소수
3은 2까지 나눠서 안 떨어지니 소수!
4는 2부터 나눠서, 2로 바로 나눠떨어지니 중지.
5는 2부터 4까지 나눠서 안 떨어지니 소수!
이렇게 구현하면? 코딩 테스트에서 시간초과로 떨어진다.
너무 오래 걸리니까.
이럴 때 검색이 필요하다. 소수 구하기를 검색하다보면 에라토스테네스의 체가 나온다.
에라토스테네스의 체란?
고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다. (출처: 위키백과 에라토스테네세의 체)
120까지 소수를 구한다면, 모든 수가 소수라고 가정한 뒤에, 먼저 2가 소수니까, 2의 배수는 모두 제외, 그 다음 3으로 넘어가서 3도 소수, 3의 배수는 모두 제외하는 방식이다.
설명을 들으면 와! 하게 된다. 저렇게 간단하게 찾을 수 있다니! 그러니 이름이 남아 있게 된 것!
파이썬 구현 예
반응형