백준
99클럽 코테 스터디 1일차 TIL - 백준 1929번 : 소수 구하기
킴준현
2025. 3. 31. 18:59
항해99 클럽 코테 스터디 TIL - 자바 미들러 (3/30(월) ~ 4/28(월)) 시작!
https://www.acmicpc.net/problem/1929
✅ 문제
📌 접근방법
일반적인 소수 판별법으로 소수는 자기자신과 1만을 약수로 가지는 수이다.
n미만의 숫자 중에서 나머지 연산을 했을 때 0이 되면 약수를 가져서 소수가 아니다.
public class Algorithm {
static boolean isPrime(int n){ // 시간복잡도 O(N)
if(n<2){
return false; // 1은 소수가 아니기에 false
}else{
for(int i = 2; i < n; i++){
if(n % i == 0) return false; // 나머지연산을 했을 때 0이 나오면 소수가 아니므로 false
}
return true; // 위의 case
}
}
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 소수인지 판별할 숫자 input
System.out.println( (isPrime(N) == true) ? "소수입니다" : "소수가 아닙니다.");
}
}위 코드의 시간복잡도는 O(N)이며, N개의 수를 판별하면 O(N^2)이 된다.
시간이 상당히 오래걸리므로 에라토스테네스의 체로 접근했다.
에라토스테네스의 체는 많은 수의 소수판별을 할 때 유용하다.
이 알고리즘의 원리는 해당 숫자가 소수라면, 해당 숫자의 배수들은 모두 해당 숫자를 약수로 가지고 있으므로 소수가 되지 못한다.
- 먼저 지워지지 않는 가장 작은 수를 찾는다 -> 보통 2부터 시작한다.
- 해당 숫자는 소수이다.
- 해당 숫자의 배수들을 모두 지운다.
예시를 들어 설명하면 N이 100일 때 1~100 사이의 소수를 구해본다.
1은 예외이므로 제외하고 시작한다.
먼저, 지워지지 않는 가장 작은 수는 2이고, 2의 배수들은 소수가 아니므로 다 삭제한다.
(검은 글자는 소수거나 지워지지 않은 수, 회색 글자는 지워진 수)
그 다음 지워지지 않는 가장 작은 수는 3이고, 3의 배수들을 다 삭제한다.
그 다음 지워지지 않는 가장 작은 수는 5이고, 5의 배수들을 다 삭제한다.
이러한 방식으로 하면 아래와 같이 소수들을 구할 수 있다.
import java.io.*;
public class Algorithm {
static boolean[] isPrime;
static void isPrime_check(int n){
isPrime = new boolean[n+1]; // N번째의 수 까지 받기위해 N+1까지 동적할당
for(int i = 0; i < isPrime.length; i++){
isPrime[i] = true; // boolean배열의 default값은 false이므로 true로 바꿔주기
}
isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아니니깐 false
for(int i = 2; i <= Math.sqrt(n); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인
if(isPrime[i]){ // 해당수가 소수라면, 해당수를 제외한 배수들을 모두 false 처리하기
for(int j = i*i; j<= n; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
isPrime[j] = false;
}
}
}
}
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 소수인지 판별할 숫자 input
isPrime_check(N);
}
}위의 시간 복잡도는 O(Nlog(logN))이다.
🔑 풀이
에라토스테네스의 체 알고리즘을 활용하여 문제 풀이에 적용했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 항해 코딩테스트 스터디 Day1 - 자바/미들러
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
boolean[] isPrime = isPrime_check(N);
for (int i = M; i <= N; i++) {
if (isPrime[i]) {
System.out.println(i); // 소수인 경우, 출력
}
}
}
public static boolean[] isPrime_check(int n) {
boolean[] isPrime = new boolean[n + 1];
for (int i = 0; i < isPrime.length; i++) {
isPrime[i] = true; // 모든 수를 소수로 가정
}
isPrime[0] = false; // 0은 소수가 아님
isPrime[1] = false; // 1은 소수가 아님
// 에라토스테네스의 체 알고리즘
for (int i = 2; i <= Math.sqrt(n); i++) {
if (isPrime[i]) { // i가 소수인 경우
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false; // i의 배수들은 소수가 아님
}
}
}
return isPrime;
}
}