자연수 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까지 판별할 필요가 없다는 점을 이용한 것이다.
즉, N의 제곱근 (sqrt 사용) 까지만 탐색을 진행하면 된다. 이 방법의 시간복잡도는 O(N^(1/2))이다. - 에라토스테네스의 체. 제일 시간복잡도 측면에서 우수한 방법이다. 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 배열에 남게 되는 방법이다.
대량의 소수를 구해야 하고, 메모리 제한이 충분하다면 제일 좋은 방법이다.
'[Java] > 문법, 자료구조, 알고리즘' 카테고리의 다른 글
TreeSet, Red-Black Tree (0) | 2023.03.10 |
---|---|
HashMap (0) | 2023.03.10 |
String 클래스 메소드 정리 (0) | 2023.03.06 |
StringBuilder, StringBuffer (0) | 2023.03.03 |
조합(Combination) (0) | 2023.02.24 |