(Java)프로그래머스 - 소수 찾기

나의 풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] isPrime = new boolean[n + 1]; // 1
        
        for (int i = 2; i <= n; i++) { // 2
            isPrime[i] = true;   
        }
        
        for (int i = 2; i * i <= n; i++){ // 3
            if (isPrime[i]){
                for (int j = i * i; j <= n; j += i) { // 4
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= n; i++){ // 5
            if (isPrime[i]) answer++;
        }
        
        return answer;
    }
}

과정

1. 배열의 크기가 n + 1인 boolean 배열을 선언한다
2. 2부터 모든 배열의 값을 true로 선언한다
3. i가 2부터 i * i가 n보다 작거나 같은 범위에 isPrime[i]가 참이라면
4. j가 i * i부터 n보다 작거나 같은 범위에 i를 더해주면서 해당하는 배열을 false로 만든다
5. isPrime[i]가 참이면 answer++

참조

다른 사람 풀이

class Solution {
  public int solution(int n) {
      int answer = 0;
      for(int i = 2; i <= n; i++){
          int j = 2;
          int cnt = 0;
          while(j <= (int)Math.sqrt(i)){
              if(i % j == 0){
                cnt += 1;
                break;
              } 
              j += 1;
          }
          if(cnt == 0) answer += 1;
      }
      return answer;
  }
}