백준 1978 소수 찾기
에라토스테네스의 체
소수판별을 하는 방법은 다양하게 있겠지만, 나중을 위하여 에라토스테네스의 체에 대해 공부하였습니다.
에라토스테네스의 체란?
에라토스테네스의 체는 소수를 거르는 ‘체’ 그 자체입니다. 아래 gif 를 보면 쉽게 파악할 수 있습니다.
•
초반의 수 2, 3, 5, 7 .. 의 소수를 판별하고, 그의 배수를 제거합니다.
•
이렇게 제거하고 나서 색깔이 칠해지지 않은 수가 소수입니다.
구현은 어떻게 해야할까?
아래와 같은 논리로 작성하였습니다.
•
수의 범위 확인
•
해당 수 까지의 인덱스를 가지는 배열을 생성합니다.
◦
이때 배열은 boolean 값을 가집니다.
•
메인 메서드에 숫자를 입력받는 메서드를 작성합니다.
•
동시에 에라토스 테네스의 체를 구현하는 메서드도 작성합니다.
◦
이때 for 문을 사용하여 문제에서 제시된 수의 범위 까지의 소수를 걸러냅니다.
◦
조금 더 효율적인 탐색을 위해, 배수를 찾기위한 수는 N 의 제곱근으로 제한합니다.
문제 풀이
package baekjoon.level.bronze;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class PROB1978 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N;
static int[] numbers;
static boolean[] isPrime;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
numbers = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
isPrime = new boolean[1001];
solve();
System.out.println(find());
}
public static void solve() {
for (int i = 2; i < isPrime.length; i++) {
isPrime[i] = true;
}
for (int i = 2; i <= Math.sqrt(isPrime.length); i++) {
if (isPrime[i]) {
for (int j = i * i; j < isPrime.length; j += i) {
isPrime[j] = false;
}
}
}
}
public static int find() {
int result = 0;
for (int i = 0; i < N; i++) {
if (numbers[i] > 1 && isPrime[numbers[i]]) {
result++;
}
}
return result;
}
}
Java
복사