Assignment #1 P3-3 최적화 관련 문의

[stevenoh0908]

안녕하세요, 지구환경과학부 오유신입니다.

나머지 문제는 Testcase를 통과했지만, 그렇지 못한 부여된 과제 1의 3-3번 문항의 최적화에 난항을 겪고 있어 관련하여 문의드립니다.

이전 #6 에 의하면 3-3 문제는 3-1 문제의 isPrime 함수를 사용하는 것을 의도하고 출제된 문제라고 말씀주셨는데, 3-1과 3-2 문제를 모두 구현한 isPrime 함수를 사용하여 구현하여 통과하였음에도 불구하고 3-3 문제에 대한 제 구현의 경우 TestSuite.scala의 Line 67-70의 상당히 큰 입력에 대해 큰 소수에 대한 Primality Test 판정에 대부분의 시간이 소요되면서 P3-3 Test의 수행 시간이 41초 정도로 나오는 것 같습니다.

요구되는 tailrec 등을 사용한 최적화를 모두 행했음에도 이런 결과가 발생하는지라, 3-1의 isPrime 함수가 Test를 통과했음에도 단순한 수준을 넘어 아예 Pockllington primality test의 수준까지 구현해야 하는 것인지 망설여집니다.

만약 3-3 문제의 최적화와 관련하여 제가 놓치고 있을 것 같은 부분이 있다면 일러주시면 감사드리겠습니다.

[Yeonwoo-Nam]

1. 문제 3-1에서 주어진 test를 통과했다고 하더라도 최적화가 충분하지 않았다면 3-2, 3-3 문제의 테스트에서 최적화 문제가 발생할 수 있습니다.
   2. 힌트가 주어지지 않은 경우에는 말씀하신 Pockllington primality test 등의 특별한 수학적 지식이 필요하지 않다고 생각하셔도 됩니다.
   3. 문제 3-2, 3-3에서 제공하는 참고 문서(위키피디아) 역시 소수와 관련되어 있기 때문에 일부 내용이 문제 3-1의 해결에도 도움이 될 수도 있습니다.

[stevenoh0908]

감사합니다, 조교님. 답변이 큰 도움이 되었습니다.