[BaekJoon/백준] 1929번 에라토스테네스의 체

범위 안의 다량의 소수를 구할 때에는 '에라토스테네스의 체' 알고리즘을 사용한다.

 

범위 안의 수를 일일히 소수판별하는것보다 훨씬 빠르다.

1 이상 25 이하의 소수를 구해야 할 때, 1 2 3 4... 등의 모든 수를 각각 소수판별하는것보다 훨씬 빠르다는 것.

 

가장 큰 수 만큼 배열을 할당해준 뒤에

숫자 2부터 본인을 제외한 2의 배수를 구한 뒤 소수가 아님을 체크한다.

그리고 다 끝나면 이번엔 숫자 3 차례, 본인을 제외한 3의 배수를 구한 뒤 소수가 아님을 체크한다.

이렇게 쭉 이어나간다. 숫자의 제곱이 가장 큰수보다 커질때까지만.

 

import java.util.Scanner;

public class sosu {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int arr[] = new int[b+1];

        for(int i=2; i<=b; i++) {
            arr[i]=i;
        }

        for(int i=2; i*i<=b; i++) { // i의 제곱이 b 보다 커지면 탈출.
            for(int j=i+i; j<=b; j+=i) {
                if(arr[j]==0) continue;
                arr[j]=0;
            }
        }

        for(int i=a; i<=b; i++) {
            if(arr[i]!=0) System.out.println(arr[i]);
        }
    }
}

위를 보면 주석처리된 부분이 있는데, N 의 약수를 구할 때 1부터 25까지 진행해본다고 치면 1x25, 5x5, 25x1 이런 과정을 거치게 된다.

N의 제곱근을 중점으로 대칭적으로 이루어진다는 특징이 있다. 모든 수가 이렇다. 따라서 굳이 N제곱근을 넘어가는 수 까지 연산을 해줄 필요는 없다.

 

여기 코드에서도 마찬가지로, 100이하의 소수를 구한다고 할 때 100까지가 제곱근이 10이므로 소수를 판별할 때 10을 넘어가는 대칭적인 구도는 100 이하의 수에서는 찾아볼 수 없다. 예를들어 81은 9의 제곱근이며 10을 넘지 않는다. 9를 기준으로 대칭적인 약수를 갖는 것.

따라서 범위 안의 가장 큰 수인 100의 제곱근 까지만 해주면 된다. 나머지 수들은 알아서 10 이하의 수를 기준(제곱근)으로 대칭 구도를 갖을 것이다.

 

'에라토스테네스의 체' 알고리즘은 임의의 수 이하의 모든 소수를 찾는 데에 충족화된 알고리즘이며

2부터 임의의 수의 제곱근이하 까지 본인을 제외한 배수를 지워버리고 남은 수(마찬가지로 2부터)를 소수로 도출하는 알고리즘이다.

(1은 기본으로 제외)