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

프로그래머스 문제

<소수 찾기>

소수 찾기 문제

입력받은 n숫자 사이에 있는 소수의 개수를 리턴하는 문제이다. 먼저 소수는 1과 자신으로만 나누어져야함을 유의해야한다. 

 

소수 찾기 내 답변

소수 찾기에 대해서 하나 하나 for range로 값을 넣어주는 방법도 있지만, 2로 나누어서 반이 된 값으로 진행할 수도 있다. 

ex) n = 8

1 2 3 4 5 6 7 8 이 8안에 위치하는데 이 때를 확인해보면, 앞 뒤로 (1, 8), (2, 7), (3, 6), (4, 5) 이런식으로 연결해줄 수 있으니 2로 나누어서 사용할 수 있다.

또한 루트를 사용하여서 2를 나눈것보다 범위를 더 줄일 수도 있다. 1/2승은 루트와 같은 의미이다.

맨 처음에 시도한 방법은 일단 2를 나눠서 진행했는데 답변이 맞더라도 이번 문제에서 중요한 점은 효율성이 중요했다. 다른 테스트들이 통과해도 유독 효율성 문제에서 시간초과가 나타났고 최대한 불필요한 요소들을 줄이는게 중요했다. 

if문에 i != j 라는 문구가 들어있었지만, range를 3과 2로 설정해서 알아서 자동으로 앞의 소수들이 넘어가도록 해놓고 진행해서 그 문구를 뺄 수 있었고 효율성에서 합격을 받았다.

효율성이 중요한 이유는 이렇게 돌아가는 것들도 다 돈이 되기에 따질 수 밖에 없다고 했다. 최대한 적고 빠르게 식을 알아내기 위해서 공부를 계속 해야할 것 같다고 느꼈다.