Menu

Subscribe

[JAVA/프로그래머스] 연습문제: 소수 찾기

HEESOO on Programmers

👀 문제

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

👊 도전

1. 설계

  1. 에라토스테네스의 체를 이용한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

import java.util.*;
/**
 *
 * @author HEESOO
 *
 */
class Solution {
  public int solution(int n) {
      int answer = 0;
      boolean[] prime=new boolean[n+1];
      Arrays.fill(prime, true);
      prime[0]=prime[1]=false;
      int rootN=(int)Math.sqrt(n);
      for(int i=2;i<=rootN;i++){
          if(!prime[i]) continue;
          for(int j=i+i;j<=n;j+=i){
              prime[j]=false;
          }
      }
      for(boolean num:prime){
          if(num) answer++;
      }
      return answer;
  }
}

3. 결과

실행결과 🤟 성공 🤟

4. 설명

  1. 에라토스테네스의 체를 이용한다.
    • 인덱스 번호가 n까지 있는 boolean형 배열을 선언한다. 이때 인덱스가 숫자를 뜻한다.
    • 0은 사용하지 않기 때문에, 1은 소수도 합성수도 아니므로 false로, 나머지는 true로 초기화한다.
    • 숫자가 소수일 경우 true를 저장한다.
    • 2부터 루트n까지 중 소수는 true로, 소수의 배수는 false를 저장한다.
    • 첫 번째 for문에서 2부터 루트n까지 중 소수를 찾는다. prime[i]가 false라면 i는 합성수라는 뜻이므로 continue한다.
    • prime[i]가 true일 경우 소수이므로 해당 i는 살려두고 두 번째 for문을 사용하여 n까지의 i의 배수를 모두 false처리한다.
    • 이중 for문이 끝난 후, 다시 prime배열을 순회하며 true인 값의 갯수를 리턴한다.

👏 해결 완료!

소수를 구하는 알고리즘에는 에라토스테네스의 체가 제일 효율성이 좋다는 것을 명심해두어야겠다.

참고