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