n까지의 소수의 개수 구하기

문제) 입력 받은 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;
 }