[알고리즘] 에라토스테네스의 체

1. 개념

소수를 구하기 위해 사용하는 방법. 

 

2. 방법

• 구하고자 하는 소수의 범위만큼 1차원 배열을 만든다.
• 1부터 보면서 해당 수가 소수인지 아닌지 판별한다.
  • 만약 소수가 아니면 지운다.
  • 만약 소수면 놔두고, 그 수의 배수를 배열에서 모두 지운다.
• 배열 끝까지 위 과정을 반복한 후 남아있는 수들이 해당 범위 내에서의 소수다.

 

3. 특징

• 이중 for문을 사용해야 하므로 이론적인 시간 복잡도는 O(n2)이다.
• 하지만, 배수를 삭제하는 과정이 있기 때문에, 실제로 실행을 해 보면 바깥쪽 for문을 건너뛰는 경우가 많이 발생한다. 그래서 실제 시간복잡도는 O(nlog(logn))이다.

 

4. 코드

nums[0] = -1;
nums[1] = -1;
for(int i = 2; i<=end; i++){
    nums[i] = i;
}
for(int i = 2; i<=end; i++){
    if(nums[i] == -1){
        continue;
    }
    for(int j = i+i; j<=end; j=j+i){
        nums[j] = -1;
    }
}
for(int i = start; i<=end; i++){
    if(nums[i] != -1){
        System.out.println(nums[i]);
    }
}

// 제곱근까지만 for문 도는 코드

nums[0] = -1;
nums[1] = -1;
for(int i = 2; i<=end; i++){
    nums[i] = i;
}
for(int i = 2; i<=Math.sqrt(end); i++){
    if(nums[i] == -1){
        continue;
    }
    for(int j = i+i; j<=end; j=j+i){
        nums[j] = -1;
    }
}
for(int i = start; i<=end; i++){
    if(nums[i] != -1){
        System.out.println(nums[i]);
    }
}

제곱근 까지만 for문 돌아도 되는 이유

만약 마지막 수가 16이라고 해보자. 그러면 2부터 살피기 시작했을 때, 2의 배수 싹 없애고, 3의 배수 싹 없애고, 4의 배수 싹 없애면 5의 배수와 6의 배수를 살필 때는 지울 것이 없어진다. 즉, 제곱근보다 작은 수의 배수를 없애버리면 제곱근보다 큰 수의 배수는 자동으로 없어지는 것. 그래서 굳이 제곱근보다 큰 수를 for문에 넣고 돌려야 할 필요가 없다.

 

5. 관련 문제

백준 1929

GitHub - Lee-Min-Jung/coding_test_practice

백준 1456

GitHub - Lee-Min-Jung/coding_test_practice

백준 1747

GitHub - Lee-Min-Jung/coding_test_practice

백준 1016

GitHub - Lee-Min-Jung/coding_test_practice