☑️소수 구하기 알고리즘

백준 단계별 풀어보기 기본 수학2의 1929번을 풀면서 내가 모르는 소수 구하기 알고리즘을 알게 되었다 뿐만 아니라 굳이 n까지 확인할 필요가 없다는 것을 알게 되었다

N의 제곱근까지만 확인해도 되는 이유

지금까지 나는 n이 주어지면 2부터 n까지 나눠서 소수인지 합성수인지 판별했다

int i=2
while (i<n){
	if(n%i==0) return false;
	i++;
}

하지만 n이 아니라 n의 제곱근까지만 확인을 해도 된다. 증명은 다음과 같다

• n은 자연수이므로 n=a*b (a,b는 자연수)로 표현할 수 있다
• m=sqrt(n) 이라고 할 때 a*b=m*m이 된다
• 따라서 a와 b가 자연수가 되기 위해선
  • a=m, b=m
  • a<m, b>m
  • a>m, b<m 의 3가지 경우가 있다
• 즉, min(a,b)<=m 이다 (더 작은 값은 무조건 제곱근 이하)
• 따라서 a나 b가 어떤 약수이더라도 둘 중 하나는 무조건 제곱근 이하이므로 m까지만 조사해도 n이 소수인지 아닌지를 알 수 있다

에라토스테네스의 체

에라토스테네스의 체 이론은 다음과 같다
K=2부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다
이렇게 하면 남는 수는 모두 소수이다

코드는 다음과 같다

public static boolean arr[];
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int N = in.nextInt();
        arr=new boolean[N+1];//소수는 false 합성수는 true, N이하까지만
        isPrime(N);
        for (int i=1;i<=N;i++){
            if (!arr[i]) System.out.println(i);
        }
    }

• arr[] 은 전역변수로 선언한다
• 배열은 N+1개로 생성하여 1부터 N까지의 소수, 합성수 여부를 판별한다

private static void isPrime(int N) {
        if(N<2) return;
        arr[0]=arr[1]=true; //0과 1은 합성수

        for (int i=2;i<=Math.sqrt(N);i++){ 
            if(arr[i]==true) continue; 
            for (int j=i*i;j<arr.length;j+=i)
                arr[j]=true;
        }
    }

• 2부터 sqrt(N)까지의 배수까지 반복문 실행
• 이미 합성수라면 (arr[i]==true) 동작 x
• i는 제외, i * (i 미만) 은 이미 이전 반복문에서 소수 혹은 합성수가 판별났으므로 i*i부터 배수를 true로 초기화

갱장히 효율적이다!