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

에라토스테네스의 체를 이용하는 풀이법이다. 시간 제한도 걸려있어 어려운 문제이다.

 

1. 내 풀이

한번에 끝까지 돌면서 소수의 개수까지 같이 세는 방식이다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] isPrime = new int[n+1];
        
        for(int i = 2 ; i <= n ; i++){
            if(isPrime[i] != 0) continue;
            answer++;
            for(int j = 2; i * j <= n; j++){
                isPrime[i * j] = 1;
            }
        }
        
        return answer;
    }
}

 

 

2. 다른 분 풀이

일단 에라토스테네스의 체 후에 소수의 개수를 구하는 방법이다.

class Solution {
  public int solution(int n) {
      int answer = 0;
      boolean[] check = new boolean[n+1];

      check[0] = check[1] = true;
      for(int i =2; i*i<n+1; i++){
          for(int j= i*i; j<n+1; j+=i)
              check[j] = true;
      }
      for(int i=2; i<n+1; i++){
          if(check[i] == false)
              answer++;
      }
      return answer;
  }
}

 

참고 자료

https://velog.io/@thsdnjst/Java-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4