궤도

문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토스테네스의 체가 무엇이냐고 물어본다면... 이런식으로 특정 소수의 배수를 전부 지우는 과정을 통해 소수를 구하는 방법이다. 만약 1~n 사이의 소수를 구하고 싶다면 √n 까지만 구하면 된다. 왜일까? n보다 작거나 같은 합성수 m=ab가 있다고 하자. a와 b가 모두 최대일 때는 a=b=√n 일 때이다. a가 이보다 커지면 b가 √n보다 작아지고 반대의 경우엔 a가 √n보다 작아질 것이다. 그러므로 √n 까지만 체크해도 모든 합성수는 지워진다는 것이다. 그렇다면 이제 구현을 할 차례이다. 0과 1은 소수가 아니니 지워주고 2부터 시작한다. 2의 배수를 전부 지워주고, 3의 배수를 전부 지워주고, 4의 배수를 지울 필요는 없다. 왜냐하면 ..