반응형
그리스의 수학자.천문학자.지리학자. 소수를 발견하는 방법으로서 에라스토테네스의 체(코스키콘)를
고안하고, 해시계로 지구 둘레의 길이를 처음으로 계산한사람. 지리상의 위치를 위도. 경도로 표시한 것은 그가 처음인것으로 알려져있다. -두산백과-
알로리즘을 짜다보면 소수, 약수,최대공약수 등등 익숙하지만 난감한 문제에 봉착할때가 많다.
수학파트에서 살펴본 공약수의판별을 위해 유클리드의 호제법을 알아야하는 것 처럼 말이다.
에라스토테네스의 체는 말그대로 체(고운가루는 통과 시킨다)
고운가루는 소수가아닌수이다.
알고리즘으로 살펴보자.
입력을 받은 수까지의 소수를 출력시켜준다.
배열을 생성하여 첨자찾으려는 수로 인식하고 배열의 값은 1로 초기화한다.
그리고
2의 배수부터 4,6,8,10....
3의배수 6,9,12,15.....
.
.
.
배열의 첨자에 매칭시켜 값을 0으로 변환한다.
그러면 결과는 소수가 아닌 첨자의 배열은 0으로 소수인 첨자인 배열은 초기값그대로 1인채로 남게된다.
배열의 값을 조사하여 1인배열의 첨자i를 출력 시켜주면 소수만 출력이 된다.
반응형