에라토스테네스의 체
■ 정의
소수를 찾는 방법 중 하나로, '소수가 되는 수의 배수를 지우면 남은 건 소수가 된다' 라는 알고리즘
소수가 무엇인지 찾을 필요가 없으며, 2부터 자기 자신을 제외한 배수가 되는 것을 지움
- 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97이 남는데, 이것이 100 이하의 소수이다.
- 7까지 찾는 이유는 8, 9, 10은 2와 3의 배수이므로 이미 지워진 상태이고, √100 < 11이기 때문이다.
■ 사용 예 (백준 No.17103)
■ Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static boolean isPrime(int num){
if(num == 1)
return false;
for(int i = 2; i <= Math.sqrt(num); i++){
if(num % i == 0)
return false;
}
return true;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int i = 0; i < T; i++){
int N = Integer.parseInt(br.readLine());
int count = 0;
for(int j = 2; j <= N / 2; j++){
if(isPrime(j) && isPrime(N - j))
count++;
}
System.out.println(count);
}
}
}
- 처음 풀 때 에라토스테네스의 체를 사용하지 않았는데, 그럴 경우 시간초과 에러가 발생하였다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
boolean[] num = new boolean[1000001];
num[0] = num[1] = true; // true = 소수 아님, false = 소수
for(int i = 2; i <= Math.sqrt(1000000); i++){
if(!num[i]){
for(int j = i * 2; j <= 1000000; j += i){
num[j] = true;
}
}
}
for(int i = 0; i < T; i++){
int N = Integer.parseInt(br.readLine());
int cnt = 0;
for(int j = 2; j <= N / 2; j++){
if(!num[j] && !num[N - j])
cnt++;
}
System.out.println(cnt);
}
}
}
- 에라토스테네스의 체를 사용하면 시간초과가 발생하지 않았다.
'Java > TIL (Today I Learned)' 카테고리의 다른 글
[TIL] QueryDsl 설정법(SpringBoot 3.0이상) (0) | 2023.11.15 |
---|---|
[JAVA] 추상클래스 (abstract) / 인터페이스 (interface) (0) | 2023.08.07 |
[JAVA] 유클리드 호제법(GCD / LCD) (0) | 2023.03.15 |
[JAVA] contains() / replace() (0) | 2023.02.07 |
[JAVA] StringBuilder (0) | 2023.02.06 |
댓글