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

🕐 풀이 시간 : 30분

🌄시행착오

예전에 백준 문제를 풀면서는 항상 시간, 메모리 제한이 있었는데, 최근에는 프로그래머스만 풀면서 그 제약에 대한 부분에 크게 집중하지 않았다.
그렇기에 쉽고 비효율적인 코드를 사용해서 코딩을 했고 당연히 틀렸다.

💡아이디어

에라토스테네스의 체

EX) 1~15까지의 수들 중에 소수인 것을 찾아본다
핵심) 2부터 시작해서, n보다 작으면서 2의 배수인 것들의 값을0, 3의 배수인 것들의 값을 0,..
이런 식으로 진행하면서 이미 표시하지 않은 배수들에 대해서만 계속 0으로 만든다.

단계 1) 15개의 숫자를 담을 수 있는 배열 생성
단계 2) 반복문 2~15까지 돌면서 배열에 값이 0인 경우는 넘어가고, 0이 아니라면 그 숫자의 배수들 모두는 0으로 해둔다.
단계 3) 배수들에 의해 0으로 되지 못한 수들의 개수를 체크한다.

실패코드

class Solution {
    public int solution(int n) {
        int answer = 1;
        for(int i = 2; i <= n/2; i++){
            for(int a = 2; a < i; a++){
                if(i % a == 0) break;
                if(a == i-1){
                    System.out.println(i);
                    answer++;
                }
            }
        }
        return answer;
    }
}

성공코드

class Solution {
      public int solution(int n) {
          int answer = 0;
          int[] number = new int[n+1];
          for(int i=2; i<=n; i++) number[i] = i;
          
          for(int i=2; i<=n; i++) {
              if(number[i]==0) continue;// x의 배수로 이미 소수가 아니라 판단되었음.
              for(int j= 2*i; j<=n; j += i) number[j] = 0;
          }
          
          //어떤 수에서라도 배수에 포함되지 못한 수는 => 소수
          for(int i=0; i<number.length; i++) {
              if(number[i]!=0) answer++;
          }
          
          return answer;
      }
}