SWEA] 3131. 100만 이하의 모든 소수

SWEA] 3131. 100만 이하의 모든 소수

SWEA 3131. 100만 이하의 모든 소수(Link)
문제의 저작권은 SWEA에 있습니다

SW Expert Academy

 

소수 문제는 에라토스테네스의 체 의 방법으로 접근해야한다.
소수는 1과 자기 자신만을 약수로 가지는 수를 말한다.
체로 수를 걸러낸다는 하여 에라토스테네스의 체라고 한단다.

에라토스테네스의 체를 다시 떠올려 봤을때, 기억나는 것은

1. 모든 자연수는 소수의 곱으로 표현될 수 있다.
2. 제일 작은 소수 2를 선택한다.
3. N보다 작은 선택한 수의 배수를 지운다. (곱으로 표현되면 소수가 아니므로)
4. 지워지지 않은 수를 반복한다.
5. 이 작업을 N의제곱근까지 진행한다.
   라는 무식해보이지만 간단하고 강력한(소수를구할때) 방법이었다.

그냥 떠오른 기억에 기반하여 진행하면 됐지만,
왜? N의 제곱근까지였지? 라는 의문이 들어서 다시 생각해 봤을때, 그 이유는
N보다 작은 합성수 M은 N의 제곱근보다 작은 배수만 체크해도 모두 지워지기 때문이다.
즉, N의 제곱근이하의 배수만 지우면 된다.


예를 들면 이해가 더 쉬울텐데, 50까지의 소수를 구한다고 해보자.(N=50)
50의 제곱근은 7보다 약간 큰 수일것이다. (7.xxx...)
7까지 위의 작업을 반복한다면, 7의 배수인 49를 지우게 될 것이다.
50의 제곱근은 7보다 조금 큰 수였다.
7의 배수를 모두 지워준 것만으로도 우리가 알아보려고 했던 수의 범위(N,50) 직전을 검사할 수 있다는 것이다.


그렇기 때문에, 배수를 지워주는 작업은 N의 제곱근까지만 진행하면 된다.

//에라토스테네스의 체 
public class d3_3131_100만이하의모든소수 {
    final static int N = 1_000_000;
    static boolean[] prime = new boolean[N+1];
    public static void main(String[] args) {
        
        for(int i=2; i<=Math.sqrt(N); i++) {
            //소수면. 
            if(prime[i]==false) {
                int t=2;
                while(true) {
                    prime[i*t]=true;
                    t++;
                    if(i*t>N)
                        break;
                }
            }//end if
        }
        for(int i=2; i<=N; i++) {
            if(prime[i]==false)
                System.out.print(i+" ");
        }
    }//end main
}