망할 maple 숙제.. -_-;;

결국 끝내고 말았다. Newton Method야 별로 어려울 것이 없었고, 문제는 소수 판정 알고리즘을 만드는 것인데, 아이들은 Robin-Miller의 정리를 이용하는 것에서부터 에라토네스의 체 등 여러 방법으로 제작하고 있었다.

한 친구랑 이야기하다가, 소수는 항상 6n±1 (n은 자연수)에 속하므로 간단히 그 수들로만 나누면 될 거라는 아이디어를 그 녀석이 이야기해 주었다.

사실, 내가 구현하고 있었던 방법은 수의 범위를 어떻게 주든지 간에 무조건 1부터 시작하여 하나씩 수를 증가시키면서 그 동안 나타난 소수들을 배열에 저장하고 그 배열에 든 범위까지는 배열의 소수로만 나누어 본 뒤 그 범위를 넘었을 때만 일일이 나눠보는(물론 sqrt(n)보다 작은 수까지만) 방식이었다.

하지만 태생적인 문제로 수의 시작 범위가 1보다 많이 큰 수들에서는 1부터 계산해야 하기 때문에 불리할 수 밖에 없었다. 게다가 결정적으로 maple 자체가 배열 처리가 느리다는 이야기를 듣게 되었다.

결국 삽질 끝에(?) 그 기본 아이디어에 약간의 최적화를 하니 아래와 같은 엄청난 결과를 얻을 수 있었다. 드디어 성공이다!! (그러나 시험은 일주일 남았다...OTL)