[Java] programmers-"소수 찾기"

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

---

제한사항

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

---

입축력 예

n	result
10	4
5	3

---

알고리즘

1. 1은 소수에서 제외되므로, 2부터 n까지 for문을 돌린다.
2. 2와 3은 소수이기때문에 따로 계산없이 빼주었고, 그 외의 경우는 Math.sqrt() 사용해서 2부터 해당 수의 제곱근까지 또 for문을 돌려서 그 전까지 나누어떨어지는 수가 있으면 소수가 아니므로 바로 빠져나온다. (런타임 줄이기 위해)

   소수 구하는 알고리즘은 아래 코드와 같다. "에라토스테네스의 접근"

   for(int i=2;i<=Math.sqrt(num);i++) {
   	if(num % i == 0) 소수아님!
   }

   • num을 나누는 모든 숫자 a는 그에 대한 보수 b가 반드시 존재하기 때문이다. (a*b = num, sqrt(n)^2 = n)
   • 수가 수를 나누면 몫이 발생하게 되는데 몫과 나누는 수, 둘 중 하나는 반드시 num의 제곱근 이하이기 때문이다.
   • 주어진 자연수 num이 소수이기 위한 필요충분 조건은 num이 num의 제곱근보다 크지 않은 어떤 소수로도 나눠지지 않는다.

---

내 소스 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int check = 0;
        
        for(int i=2;i<=n;i++) {
            if(i==2) answer++;
            else if(i==3) answer++;
            else {
                for(int j=2;j<=Math.sqrt(i);j++) {
                    if(i%j == 0) {
                        check++;
                        break;
                    }
                }

                if(check > 0) check = 0;
                else {
                    answer++;
                    check = 0;
                }
            }
        }
        
        return answer;
    }
}