Programmers 소수 찾기 Level 1

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/12921?language=java 

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
• 제한 조건
  • n은 2이상 1000000이하의 자연수입니다.
  입출력 예
• n                                                                                      result

  10	4
  5	3

  입출력 예 설명입출력 예 #1
  1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
• 입출력 예 #2
  1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
• 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
  (1은 소수가 아닙니다.)

---

문제 해석 및 풀이 방법

1. for문을 통해 1부터 n까지 for문을 통해 차례대로 소수인지 판별한다.

2. 소수는 2~입력받은 정수의 제곱근까지 반복문을 진행하며 나머지가 0이면 소수가 아님을 판단한다.

3. 소수가 아니면 answer을 1을 올려준다.

 

내가 작성한 소스코드(Java)

class Solution {
    private boolean primeFind(int n){
        if(n <= 1){
            return false; 
        }
        for(int i = 2; i<=Math.sqrt(n);i++){
            if(n % i == 0) return false;
        }
        return true;
    }
    
    public int solution(int n) {
        int answer = 0;
        for(int i=1;i<=n;i++){
            if(primeFind(i)) answer++;
        }
        
        return answer;
    }
}

1~n까지 1씩 증가시키는 폴문을 이용한다. 그리고 증가되는 값을 primeFind(i)를 통해 소수인지 판별한 후 소수이면 answer을 증가시킨다.

 

이때 소수를 판별하는 기준은 2~입력받은 값의 제곱근을 1씩 증가시키는 반복문을 사용하며 입력받은 값을 i값으로 나누어 나머지가 생기면 소수가 아니기 때문에 false를 반환함.

 

이 과정을 반복하며 결과 값을 도출한다.

결론 및 고찰

처음에 쉽게 풀 수 있는 문제라 생각했고 바로바로 풀었었다. 그런데 효율성 테스트에서 실패가 떠서 심히 고민해 보다가 소수를 판별할때에는 차례대로 나머지값을 구하는 방법은 제곱근을 이용해도 된다는 사실을 기억했었다. (소수 문제를 여러번 풀어봤었다.) 그래서 다시 수정을 했고 성공적으로 수행할 수 있었다.

 

소요 시간 20분