에라토스테네스의 체

일단 전에 기출로 풀었는데 다시 복습할 겸 정리하기

만약 16인 소수인지 아닌지 구하는 방법은 단순하게

for(int i=2;i<16;i++){
  if(16%i==0) {
    System.out.println("소수가 아니다.")
    break;
  }
}

이렇게 하나하나 검사할 수도 있다.

하지만 아래 방법은 좀 더 간단하다.

16은
1 16
2 8
4 4
8 2
16 1
일 때
우리는 16의 루트값까지만 검사를 해도 그 절반은 안해도 된다.
즉 2~15까지 검사하는 것이 아니라 2~루트16까지만 검사하는 것이다.
위를 보면 pq=16이라고 보았을 때 하나는 증가하고 하나는 감소한다.
그 규칙이 일정하기 때문에 딱 그 절반만 검사해도 알 수 있다는 의미이다.

이를 에라토스테네스의 체에 응용해보고자 한다.
에라토스테네스의 체는 말 그대로 걸러준다는 것
예를 들어 16까지의 소수를 구할 때 이 에라토스테네스 체의 방법을 소수를 걸러내겠다는 것이다.

이 방법은
2를 제외한 2의 배수를 제거하고
3을 제외한 3의 배수를 제거한다.
4인 경우 2에 의해서 제거되었음으로 패스
5를 제외한 5의 배수를 제거한다.

이렇게 쭉 16까지 간다!
위에 배웠듯이 굳이 우리가 끝가지 갈 필요는 없다 어차피 발전은 제거되었다.
따라서 16까지 존재하는 소수를 구할 때도 그 절반까지만 진행한다.

백준 1929번 풀이방법을 첨부한다.

import java.util.*;
import java.io.*;


class Main{
    public static boolean[] prime ; //boolean 기본값은 False
    public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      StringTokenizer st = new StringTokenizer(br.readLine()," ");
      int M = Integer.parseInt(st.nextToken());
      int N = Integer.parseInt(st.nextToken());

      make_prime(M,N);

      for(int i=M;i<prime.length;i++) {
          if(prime[i]==false) bw.write(Integer.toString(i)+"\n");
      }
      bw.flush();
      bw.close();
      br.close();


    }

    public static void make_prime(int M , int N){

        prime = new boolean[N+1];

        if(N==1) return;

        prime[0]=true; prime[1]=true;

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



        }

    }