반응형
문제

문제 해결 방법
- 에라스토테네스의 체 이용하여 소수 구하기
- 소수의 합 구하기
시간 제한이 짧으므로, 시간 복잡도를 고려하여 코드를 구성하는 게 중요하다.
에라스토테네스의 체
https://skylarcoding.tistory.com/361
문제 반례 찾는 법
아래 링크에서 확인할 수 있다.
https://skylarcoding.tistory.com/303
코드 해설
- 소수 판별 체를 한번만 만들어 시간 복잡도 개선
- 소수끼리의 합 구할 때, 이중 for 문이 아닌 n = i + (n - i) 공식 이용하여 시간 복잡도 개선
위 두 가지만 유의하고 이전의 에라스토테네스의 체 문제 풀이들을 참고하면 쉽게 풀 수 있다.
[Java] 백준1929 소수 구하기 : 에라스토테네스의 체
출처: https://skylarcoding.tistory.com/361 [코딩 공부하는 블로그:티스토리]
[Java] 백준4948 베르트랑 공준 : 에라스토테네스의 체
출처: https://skylarcoding.tistory.com/362 [코딩 공부하는 블로그:티스토리]
코드
package AlgorithmStudy.src.silver;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class S17103 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long testCase = Integer.parseInt(br.readLine());
if (1 > testCase || testCase > 100) return;
// 소수 판별 체 한번만 만들기
boolean[] list = isPrime();
// 테스트 케이스 입력
for (int i = 0; i < testCase; i++) {
int n = Integer.parseInt(br.readLine());
if (2 >= n || n > 1000000) return;
addPrime(n, list);
}
}
// 에라스토테네스의 체
/*
1. n 보다 작은 수의 소수 구하기
2. 소수끼리 합이 n 인 것 구하기
*/
public static boolean[] isPrime() {
boolean[] list = new boolean[1000001];
list[0] = true;
list[1] = true;
// 소수 구하기
for (int i = 2; i * i <= list.length - 1; i++) {
if (!list[i]) {
for (int j = i * i; j <= list.length - 1; j += i) {
list[j] = true;
}
}
}
return list;
}
public static void addPrime(int n, boolean[] list) {
int cnt = 0;
// 소수끼리 합 구하기
for (int i = 2; i <= n / 2; i++) {
if (!list[i] && !list[n - i]) { // n = i + (n - i) 이기 때문에.
cnt ++;
}
}
System.out.println(cnt);
}
}
반응형