소수 (에라토스테네스의 체)

자연수 N을 입력받고, 1부터 N까지의 소수의개수를 출력해야 할 경우

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

   int ans = 0;
   int[] primeList = new int[N+1];
   
   Arrays.fill(primeList, 0);
   
   for(int i = 2; i <= N; i++) {
   	if(primeList[i] == 0) {
   		ans++;
   		for(int j = i; j <= N; j += i) {
   			primeList[j]= 1; 
   		}
   	}	
   }
   

   
   index 2부터 시작해, index만큼 나아가며 소수 여부를 적어놓은 primeList 배열의 값을 1로 바꾸어 나가면
   최종적으로 소수(반복문이 끝나도 primeList[x] = 0 인 x들) 만이 primeList 배열에 남게 되는 방법이다.
   
   대량의 소수를 구해야 하고, 메모리 제한이 충분하다면 제일 좋은 방법이다.