에라토스테네스의 체를 이용한 소수 찾기

트라이캐치의 소수 찾기 문제

- 해당하는 모든 소수를 출력하라.

소수란 1과 자기 자신만을 약수로 가지는 수이다. 100이하의 자연수 중 모든 소수를 출력하시오.

소수를 오름차순으로 출력한다. 각 출력값 사이는 공백으로 구분하고 출력값 5개 마다 줄바꿈을 한다.

아래와 같은 결과 값이 출력되어야 한다.

2 3 5 7 11 
13 17 19 23 29 
31 37 41 43 47 
53 59 61 67 71 
73 79 83 89 97

위 내용까지 트라이캐치의 소수 찾기 문제이며, 아래코드는 오름차순과 출력값 사이를 공백으로 구분하고, 5개마다 줄바꿈을 적용하지 않은 소스이다.

해당 코드는 범용성을 위해 자바스크립트를 이용하여 만들었으며, 에라토스테네스의 체를 이용한 방법이다.

아래는 재귀 함수를 이용하여 좀더 간략하게 구성

var arrNum = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100], check = [2,3,5,7], res = null; function myFunc(_arr, _exp) { for (var i=0; i<_arr.length; i++) { if (_arr[i]%_exp[0]==false && _arr[i]!=_exp[0]) { _arr.splice(i,1) } } _exp.splice(0,1); if (_exp.length===0) { _arr.splice(0,1); } return _exp.length===0 ? _arr : myFunc(_arr, _exp); } res = myFunc(arrNum, check); console.log(res);

에라토스테네스의 체에 대한 부연설명

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.

아래 움직이는 이미지를 통해 쉽게 알고리즘을 눈으로 확인하자.