알고리즘
[백준 알고리즘] 1978 - 소수 찾기
DevBee
2021. 6. 16. 06:04
https://www.acmicpc.net/problem/1978
1978번: 소수 찾기
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
www.acmicpc.net
이 문제는 에라토스테네스의 체를 사용하여 문제를 해결할 수 있습니다.
에라토스테네스의 체란 앞에서부터 자기 자신의 배수들을 하나씩 제거하는 방식으로 소수를 찾는 방식입니다.
자바 코드는 다음과 같습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
// 소수인 경우 true, 아니면 false
boolean[] nums = new boolean[1001];
Arrays.fill(nums, true);
nums[0] = false; nums[1] = false;
// 에라토스테네스의 체 방식으로 소수가 아닌 경우를 찾아 false로 변경
for (int i = 2; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
// 이미 소수가 아닌 경우(false)는 다시 확인하지 않음
if (nums[j]) {
nums[j] = j % i != 0;
}
}
}
// 입력 받기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int answer = 0;
for (int i = 0; i < t; i++) {
// 해당 숫자가 소수인 경우(true)
if (nums[input[i]]) {
answer++;
}
}
System.out.println(answer);
}
}