문제) 입력 받은 n개까지의 소수의 개수를 구하시오. (1은 소수 X)

응용) 소수의 합을 구하시오, 소수를 전부 출력하시오

소수의 개수를 구하는 방식은 간단하며 여러개의 방법이 있다. 

처음에는 안에 있는 for문을 for(int j = 2; j <= i; j++)로 사용하여 if(i % j == 0)일 경우, Count를 해주어서 구하였었다.

하지만 이와 같은 방법은 개수를 구할 수는 있었지만 모든 값들을 다 계산하여야 하기에 효율성이 떨어진다고 생각하여 더욱 효율적인 방법이 있을지 고민을 해보았다.

그 결과 아래와 같이 수정하였다. (Math.sqrt()는 루트 값을 구하는 함수)

(학생 때 수학 좀 열심히 공부할걸....)

public int solution(int n) {
      int answer = 0;
      
      for(int i = 2; i <= n; i++) {
          boolean isPrime = true;
          for(int j = 2; j <= Math.sqrt(i); j++) {
              if(i % j == 0) {
                  isPrime = false;
                  break;
              }
          }
          
          if(isPrime) {
              answer++;
          }
      }
      
      return answer;
 }