[JAVA-1929] 소수 구하기 - 에라토스테네스의 체

1929번: 소수 구하기

링크를 클릭하면 해당 문제로 이동합니다.

 

출처 - 백준

---

1. 접근하기

 

알고리즘 문제를 접하다보면 종종 소수와 관련된 문제를 마주치게 되는데

소수 문제는 에라토스테네스의 체를 이용하면 빠르게 해결할 수 있다.

(소수 : 약수로 1과 자기 자신 2개의 숫자만 가지는 수)

 

2. 에라토스테네스의 체

 

TO-DO

1) 문제에서 N 이하의 숫자 중 소수를 구한다고 했으므로 0부터 N까지의 인덱스가 포함된 배열을 생성해준다.

2) 반복문을 통해, 2번 인덱스부터 값을 조사하고 해당 인덱스의 값이 0이면 출력한다.

3) 해당 인덱스의 배수인 인덱스의 값을 1로 초기화한다.

 

3. 코드

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		int[] iArr = new int[N+1];
		
		for(int i = 2; i <= N; i++) {
			if(iArr[i] == 0) {
				if(M <= i) {
					System.out.println(i);
				}
				for(int j = i; j <= N; j = j + i) {
					iArr[j] = 1;
				}
			}
		}
	}
}

 

 

4. 그림 설명

 

Q. 0부터 5까지의 숫자 중 소수의 개수를 구하라

 

int answer = 0; // 소수의 개수를 담을 변수 answer

int[] iArr = new int[6]; // 0부터 5까지의 인덱스가 포함되는 총 길이가 6인 배열을 생성한다.

 

// 배열 생성 시, 모든 인덱스의 초기값은 0으로 설정된다. 

 

// 0과 1은 소수가 아니기 때문에 기본적으로 쓰루한다.

for(int i = 2; i <= iArr.length; i++) {

 if(iArr[i] == 0) {

  // 반복문을 통해 인덱스 2부터 시작해서 해당 인덱스의 값이 0이면 answer의 값을 증가시키고

  answer++;
  for(int j = i; j <= iArr.length; j = j+i) {

  // 해당 인덱스의 배수 인덱스들의 값을 1로 초기화한다.

   iArr[j] = 1;

  }

}

 

3번 인덱스의 값이 0이므로 answer 값이 증가되고

4번 인덱스의 값은 1이므로 answer 값이 증가되지 않고

5번 인덱스의 값은 0이므로 answer 값이 증가된다.

 

반복문이 끝나고 나면 최종적으로는 iArr 배열 각각의 원소의 값은

위와같이 되고 answer의 값은 3이 되겠다.

 

 

5. 결과

 

 

처음에는 이해가 잘 되지 않아서, 노트에 몇 번 끄적이다보니 이해가 되었고

소수와 관련된 문제들은 잘 풀 수 있게 되었다.

이해가 잘 되지 않을 때는 손코딩👍