[프로그래머스/JAVA] Level 1. 소수 찾기 (에라토스테네스의 체)

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

 

# 풀이

에라토스테네스의 체

그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법으로, 소수가 되는 수의 배수들을 지우면 소수만 남는다는 알고리즘이다. (2부터 자기 자신을 제외한 배수를 지운다.) 더 자세한 설명은 위키백과(클릭)에 있는 설명과 그림을 가져왔다.

 

에라토스테네스의 체 (출처: 위키백과)

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

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

    for(int i=2; i<=n; i++) numbers[i]=i;

      for(int i=2; i<n; i++) {

        if(numbers[i] == 0) continue;

        for(int j=2*i; j<=n; j+=i) numbers[j] = 0;
      }

      for(int i=0; i<numbers.length; i++) {

        if(numbers[i] != 0) answer++;
      }

    return answer;
  }
}

 

#라인6

먼저 1은 소수가 아니므로 2부터 입력받은 수 n까지 배열에 담는다.

 

#라인8, 라인12

2부터 소수의 배수들을 하나씩 지워나간다. (이 코드에서는 값을 0으로 변경한다)

위와 같은 방식으로 3, 5, 7 ... . 수도 반복한다.

 

#라인10

이 때 배열의 값이 이미 0으로 변경된 것은 넘어간다.

 

#라인15~17

작업이 끝나면 0이 아닌 수를 세어서 리턴한다.