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

 

프로그래머스 1단계
소수 찾기

https://programmers.co.kr/learn/challenges

 

문제 설명

 

 

 

풀이

 

class Solution {
  public int solution(int n) {
      /* 에라토스테네스의 체 알고리즘을 이용해야 효율성이 높아짐 */
      
      int answer = 0;
      boolean [] arr = new boolean[n+1];    //arr값이 true이면 해당 값은 소수이다.
      arr[0] = arr[1] = false;              //0과 1은 소수가 아님으로 간주한다.
      
      for(int i=2; i<=n; i++) {             //2부터 범위 끝까지 우선 소수(true)로 설정한다.
          arr[i] = true;
      }
      
      for(int i=2; i*i<=n; i++) {           // i의 배수들은 소수가 아니므로 제외(false)시킨다
          for(int j=i*i; j<=n; j+=i) {
              arr[j] = false;
          }
      }
      
      for(int i=0; i<=n; i++) {             //true인 값들은 소수이므로 answer에 1씩 카운트한다    
          if(arr[i] == true) {
              answer++;
          }
      }
      
      return answer;
  }
}

 

​