소수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

소수 구하기 라는 문제가 풀었다. 먼저 소수란 1과 자기 자신으로만 나눠지는 수이다. 그런데 막상 1 ~ N 까지 의 수중에서 소수를 구하라고 하면 막막하다... 흔히 알고 있는 2,3,5,7,11,13.... 이 뒤는 아마 직접 구하다가는 시간 초과가 나올 것이다. 그래서 찾아보니 '에라토스테네스의 체' 라는 방법이 소수 구하는 데 매우 효과적이라고 하며 이는 O(N^1/2) 만의 시간으로 모든 소수를 탐색할 수 있다고 한다. 소수 및 공약수 구하는 문제는 한번 씩 꼭 나오니 알고 있으면 유용할 듯 하다.

코드는 다음과 같다.

에라토스테네스의 체 구현

1. 구하려고 하는 1 ~ N 까지의 수를 담을 수 있는 배열을 하나 만든다.

2. i * i 가 N 보다 작은 값까지만 탐색하면 충분하다. 그러한 이유는 보통 어떠한 수 N을 구성할 수 있는 배수는 N^1/2 크기 선에서 전부 얻을 수 있기 때문이다.

3. number[i] 가 1이라면 그 수를 제외한 모든 배수는 소수가 아니기 때문에 0으로 만들어서 배제한다.

4. 다음으로 배열을 탐색하며 값이 1인 수를 찾아 똑같이 그 수의 모든 배수를 제거해준다.

5. 이렇게 하면 배열 안에는 소수만이 남게된다.