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

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

🖊️문제

문제 설명

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를 반환

 

🖊️문제 풀이

약수 구할 때 보통 자주 사용하는 재귀함수를 이용한 방식으로 문제를 풀어보면 몇 개의 테스트에서 시간 초과가 발생한다.

 public int solution(int n) {
    int answer = 0;
    for (int i = 1; i <=n ; i++) {
      if(prime(i)){
        answer++;
      }
    }
    return answer;
  }

  private boolean prime(int num) {

    for (int i = 2; i <num ; i++) {
      if(num % i==0){
        return false;
      }
    }
    return true;
  }

 

제한 조건을 확인하면 2≤n≤ 1000000로 재귀를 이용한 방식이 시간 복잡도가 너무 커져서 발생하는 문제같다.

재귀 대신 에라토스테네스의 체를 이용해 문제를 풀었다.

 

에라토스테네스의 체는

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성하고
2. 2부터 시작해서 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 지우면서 탐색한다. 처음 선택된 숫자는 지우지 않는다.
3. 배열의 끝까지 두 번째 단계를 반복하고 배열에 남아있는 수는 소수가 되는 것이다.

일반적으로 이중for문을 사용해 시간 복잡도가 O(N제곱)이지만 최적화 정도에 따라 O(N log(log N))정도로 시간 복잡도가 줄어든다.

아래는 에라토스테네스의 체를 이용해 이 문제를 해결한 코드이다.

 

🖊️코드

  public int solution(int n) {
    int answer = 0;
    int[] arr = new int[n + 1];
    for (int i = 2; i < n + 1; i++) {
      arr[i] = i;
    }

    for (int i = 2; i <= Math.sqrt(n); i++) {
      if (arr[i] == 0) {
        continue;
      }
      for (int j = i + i; j <= n; j = j + i) {
        arr[j] = 0;
      }
    }

    for (int item : arr) {
      if (item != 0) {
        answer++;
      }
    }
    return answer;
  }