728x90
📍 에라토스테네스의 체
소수를 찾는 방법으로 시간복잡도는 O(N^1/2)이다.
💡 원리
1. 2부터 시작해 그 수의 배수를 모두 지운다.
2. 배수를 지운 다음, 다음으로 남아 있는 수를 선택해 다시 그 수의 배수를 지운다.
3. 반복한다.
4. 남은 수는 소수이다.
🥑 예시코드
- 2부터 100까지의 소수를 구한다.
- isPrime이라는 boolean 배열을 사용해 소수 여부를 표시한다.
- 배열의 길이는 100이며, 초기값은 모두 true로 설정한다.
- isPrime[0]과 isPrime[1]은 소수가 아니기 때문에 false로 설정한다.
- 2부터 시작해, 현재 수 i가 소수(isPrime[i] == true)라면, 그 수의 제곱부터 시작해 해당 수의 모든 배수를 false로 설정한다.
- 이는 배수들이 소수가 아니라는 것을 의미한다.
- 이 과정은 배열의 크기인 len까지 반복되며, 이 과정이 끝나면 isPrime 배열에는 소수인 인덱스만 true로 남게 된다.
// 2부터 100까지 소수 구하기
public static void PrimeNumber() {
boolean[] isPrime = new boolean[100]; // 소수 여부 표시
int len = isPrime.length;
Arrays.fill(isPrime, true); // 초기 값은 모두 true
isPrime[0] = false; // 소수 아님
isPrime[1] = false; // 소수 아님
for (int i = 2; i * i <= len; i++) {
// 현재 수가 소수라면
if (isPrime[i]) {
// 그 수의 제곱부터 시작해 해당 수의 모든 배수를 false로 설정 (= 소수가 아님)
for (int j = i * i; j < len; j += i) {
isPrime[j] = false;
}
}
} // 반복문이 끝나면 isPrime 배열에는 소수인 인덱스만 true로 남게 됨
}🥊 이중포문과 비교
이중포문
import java.io.IOException;
public class ref_에라토스테네스의체 {
static StringBuilder sb = new StringBuilder();
private static final int NUM = 1000000; // 100만
public static void main(String[] args) throws IOException {
long startTime = System.currentTimeMillis(); // 시작 시간
PrimeNum();
long duration = getTime(startTime); // 소요 시간 측정
System.out.println("prime num : " + sb);
System.out.println("총 소요 시간: " + duration + " ms");
}
/**
* 1-100만까지의 숫자에서 소수 구하기
*/
private static void PrimeNum(){
for(int i=2; i<NUM; i++){
for(int j=2; j<i; j++){
if(i % j == 0) break; // 나눠떨어지는 숫자가 있으면 소수 아님
if(j == i-1) sb.append(i).append(' '); // 소수
}
}
}
/**
* 소요 시간 측정
* @param startTime 시작 시간
* @return 소요 시간(밀리초)
*/
private static long getTime(long startTime) {
return System.currentTimeMillis() - startTime;
}
}
이중포문의 경우, 100만의 숫자에서 소수를 판별하는데 약 81초가 나온다.
에라토스테네스의 체
import java.io.IOException;
import java.util.Arrays;
public class ref_에라토스테네스의체 {
static StringBuilder sb = new StringBuilder();
private static final int NUM = 1000000; // 100만
static boolean[] isPrime = new boolean[NUM+1];
public static void main(String[] args) throws IOException {
long startTime = System.currentTimeMillis(); // 시작 시간
PrimeNumber();
long duration = getTime(startTime); // 소요 시간 측정
System.out.println("prime num : " + sb);
System.out.println("총 소요 시간: " + duration + " ms");
}
/**
* 에라토스테네스의 체를 사용해서
* 1-100만까지의 숫자에서 소수 구하기
*/
private static void PrimeNumber(){
Arrays.fill(isPrime, true);
isPrime[0] = false;
isPrime[1] = false;
int limit = (int) Math.sqrt(NUM); // 최대 반복 범위를 sqrt(NUM)으로 설정
for(int i = 2; i <= limit; i++){ // i의 최대값을 sqrt(NUM)으로 제한
if(isPrime[i]){
for(int j = i * i; j <= NUM; j += i){
isPrime[j] = false;
}
}
}
// sqrt(NUM) 이후에도 소수인지 확인이 필요함
for(int i = 2; i <= NUM; i++){
if(isPrime[i]){
sb.append(i).append(' ');
}
}
}
/**
* 소요 시간 측정
* @param startTime 시작 시간
* @return 소요 시간(밀리초)
*/
private static long getTime(long startTime) {
return System.currentTimeMillis() - startTime;
}
}
에라토스테네스의 체를 사용한 경우, 100만의 숫자에서 소수를 판별하는데 약 0.02초가 걸렸다. 약 400배 차이다.
💎 문제