[프로그래머스] Level1) 소수 찾기

문제 설명

 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

 

제한 조건

 

• n은 2이상 1000000이하의 자연수입니다.

 

---

풀이 과정 (자바)

 

int형 배열 arr을 생성했다.

(2를 제외한 짝수는 소수가 아니라 n을 절반으로 나눴고, n이 2인 경우가 있어 1을 더했다.)

arr[0]에는 2를 넣고, for문을 3부터 돌렸다.

i는 i + 2하여 홀수인 경우만 체크했다.

 

처음에 arr 배열에는 임의로 0이 들어가 있으므로 0인 경우에는 for문을 종료했다.

(실제 값이 들어가지 않은 상태로 판단했다.)

입력받은 n의 제곱근이 소수 값보다 크면 for문을 종료했다.

비교 값(= i)을 소수 값(= x)으로 나눴을 때 나머지가 0인 경우는 다른 값으로도 나뉜다는 것을 의미하고, 소수가 아니므로, prime 변수에 false 값을 넣었다.

 

prime이 true일 때 arr 배열에 비교 값(= i)을 넣었다.

 

 

결과

 

 

---

다른 사람의 풀이

 

int형 m 배열을 입력받은 n + 1 크기로 생성했다.

그 배열에 2부터 n까지 값을 넣었다.

2부터 n / 2까지 for문을 돌리는데

i와 i를 더한 값(i의 배수)을 ni로 하고, 해당 배열의 ni 인덱스 값을 0을 넣었다.

(i의 배수를 제거하는 과정으로, 그 값을 0으로 바꿔 넣었다.)

이 과정을 입력받은 n까지 진행했다.

 

마지막으로, for문을 돌려 m 배열에서 값이 0이 아닌 경우가 있으면

배수 값으로 제거되지 않았다는 것이고, 다른 말로 하면 소수라는 것을 의미한다.

그러므로 anwer 값을 1씩 증가했다.

 

 

기타

 

효율성 이슈가 발생하여 문제를 완료할 수 없었다. 소수 값(x)이 제곱근보다 크기가 커질 때, for문을 계속 돌리지 않음으로써 해당 문제를 해결했다.

이번에 에라토스테네스의 체에 대해 배웠다. 소수를 구할 때 반드시 에라토스테네스의 체를 이용할 필요는 없지만, 다른 방식은 꽤 비효율적이었다. 확실히 에라토스테네스의 체를 이용하니 좀 더 빠르게 처리됐다.