[자바/알고리즘] 프로그래머스 소수찾기

문제

---

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

 

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.

(1은 소수가 아닙니다. )

제한 조건

---

• n은 2이상 1000000이하의 자연수입니다.

입출력 예

---

n	result
10	4
5	3

입출력 예 설명

---

입출력 예 #1

1부터 10 사이의 소수는 [ 2, 3, 5, 7 ] 4개가 존재하므로 4를 반환

 

입출력 예 #2

1부터 5 사이의 소수는 [ 2, 3, 5 ] 3개가 존재하므로 3을 반환

나의 풀이

---

class Solution {
  public int solution(int n) {
      int cnt = 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;
          for( int j = 2*i; j<=n; j += i){
              number[j] = 0;
          }
      }
      for(int i = 0; i< number.length; i ++){
          if(number[i] != 0) cnt++;
      }
      return cnt;
	}
}

단순하게 주어진 조건처럼 반복문으로 나누어 지는지를 확인하며 소수를 판별 했었는데... 효율성 문제에서 시간 초과가 발생 질문하기를 참조해보니 다른사람도 나와 비슷한 사람이 많은것 같았다. 그래서 소수 찾는 방법을 인터넷으로 검색해보 ㄴ결과 에라토스테네스의 접근과 에라토스테네스의 체 라는 방식을 접하게 되었고, 해당 방식을 코드에 적용했더니 효율성을 통과했다. 프로그래머는 수학실력도 중요하다고 들었을 때 체감하지 못했었지만, 실제 적용해서 실행 시간의 차이를 보니 실감이 되는 문제였다.