[5. 배열] 5.9 n보다 작은 모든 소수 나열하기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

---

Q 5.9 n보다 작은 모든 소수 나열하기

양의 정수 n이 주어졌을 때, 1과 n 사이에 있는 모든 소수를 반환하는 프로그램을 작성해라.
ex) 18이 입력되면 <2,3,5,7,11,13,17>이 반환되어야 한다.

---

간단한 방법은 2부터 n까지의 숫자를 모두 순회하는 것이다. 
예를 들어 n=10 일때 bool배열을 <F,F,T,T,T,T,T,T,T,T,T> 로 초기화 하자 (0과 1은 소수가 아니므로 F)
이제 n=2부터 T로 리스트에 추가하고 2의 배수를 F로 변경, n=3을 추가하고 3의배수를 변경... 을 반복한다.

시간복잡도는 n개를 확인하는데 O(n), 소수판정을 할때 O(n^1/2) 으로 O(n^3/2) 이다. 
해당 코드는 다음과 같다.

공간복잡도 O(n), 시간복잡도O(n^3/2)

 

그러나 "i가 소수라면 i의 제곱근보다 작은 수를 약수로 갖는다."와 "2를 제외한 짝수는 소수가 아니다"라는 점을 이용해 시간을 조금 더 단축할 수 있다.

해당코드와 결과는 다음과 같다.

결과