알고리즘 - 에라토스네스의 체

알고리즘 - 에라토스네스의 체

 1보다 큰 정수 p의 양의 약수가 1과 p뿐일 때 p를 소수라고 하며 1보다 큰 정수 n이 소수가 아닐 때 n을 합성수라고 한다.

 에라토스네스의 체란, 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 특정 숫자의 배수는 소수가 아니라는 법칙에 착안하여 2 ~ N까지의 숫자에서 숫자들의 배수를 모두 제거한 뒤 제거되지 않은 숫자를 소수로 판별하는 방식으로 프로그래밍에서는 상당히 효율적인 방법론이다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

 

jina-developer.tistory.com/10

프로그래머스 Level 1 - 소수 찾기