[Level 1] 소수 찾기

 

 

 

Algorithm

-  소수 찾기 -

 

---

 

문제

1부터 입력받은 숫자 n사이에 있는 소수의 개수를 반환하는 함수를 완성해보세요.

 

- 소수는 1과 자기 자신만으로만 나누어지는 수를 의미합니다.

- 1은 소수가 아닙니다.

 

입출력 예시

n	result
10	5
5	3

 

문제 풀기

 

이번문제는 코드의 효율성도 따지는 문제라 문제를 해결하는데 약간 시간이 걸렸다.

 

일단 반복문을 3부터 2씩 값을 올려 돌리는 방식으로 반복문이 돌아가는 횟수를 최대한 최소화 할려고 시도하였다.

 

그리고 안쪽 반복문은 바깥쪽에 나온 값이 소수인지 아닌지를 파악하기 위해서 i의 값을 원래라면 1부터 i까지 계속 나누어 나머지가 0이 되는지 아닌지를 파악해보았으나 문제는 해결되지만 반복문이 너무 많이 돌아가서인지 효율성테스트는 시간초과로 실패하였다.

 

그래서 다른 방법이 없을까하는 생각에 검색을 시도해본 결과 i까지 모든 값을 나누는 것이 아니라 i의 제곱근 만큼 횟수를 돌려도 문제없이 돌아간다는 것을 알게 되었다.

 

예를 들면 10은 2*5와 5*2 이 두가지 조합으로 이루어져 있는데 결국은 같은 식이나 마찬가지 이기때문에 2번이 아닌 2의 반인 1번으로도 문제가 해결된다는 것이다.

 

그러기 위해서는 마로 제곱근을 이용해서 문제를 해결하면 된다는 것이다.

 

그렇게 해서 문제를 풀었더니 이상하게 값이 정답보다 -1 된 상태로 값이 나왔다.

 

그래서 곰곰히 생각해보니 2는 짝수이지만 유일한 소수라는 것을 잠시 놓쳤던 것이다.

 

result를 0으로 해놓았던 것을 1로 바꿔서 문제를 풀어보니 드디어 문제가 제대로 해결되는 것을 확인할 수 있었다.