자연수 N을 입력받고, 1부터 N까지의 소수의개수를 출력해야 할 경우 편입했을 당시 학교 온라인저지에서 풀었던 코드를 발견했는데 각각 숫자에 대해 2부터 x-1까지 반복문을 돌려 나머지==0 인 경우가 있으면 소수가 아님을 판별하는 brute force 방식, 전체 탐색 방식의 코드였다. O(N)의 시간복잡도를 갖는 비효율적인 방법이지만 1학년 초반의 수업이었음을 감안하여 Time Limit Exceeded가 발생하지 않는 테스트케이스들을 주셨던게 아닐까 한다.. 다음 방법은 N의 약수들이 대칭을 이루고 있다는 성질을 이용한 방법으로, N=20일 때 약수는 1, 2, 4, 5, 10, 20 이고 1과 N을 제외하고, 4와 5는 4*5=20 으로 대칭 관계이기 때문에 굳이 5까지 판별할 필요가 없다는 점을..
