99클럽 코테 스터디 8일차 TIL + 에라토스테네스의 체 알고리즘(소수 판별)

백준

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

- 오늘의 학습 키워드 : 에라토스테네스의 체 알고리즘

- 공부한 내용 본인의 언어로 정리하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int M = Integer.parseInt(st.nextToken());
    int N = Integer.parseInt(st.nextToken());

    boolean[] isPrime = new boolean[N + 1];
    for (int i=2; i<=N; i++) isPrime[i] = true; // 초기 값 세팅

    for (int i=2; i*i<=N; i++) {
      if (isPrime[i]) {
        for (int j=i*i; j<=N; j+=i) isPrime[j] = false;
      }
    }

    for (int i=M; i<=N; i++) if (isPrime[i]) System.out.println(i);
  }
}

- 오늘의 회고 : 소수 판별을 할 때 모든 수를 하나씩 나눠보는 방식을 사용했는데 비효율적이고 시간 초과가 표시됐다.

에라토스테네스의 체 알고리즘을 사용해서 코드를 리팩토링했다.

에라토스테네스의 체 알고리즘은 다음과 같은 방식으로 동작합니다: 2부터 N까지의 모든 수를 리스트에 넣습니다. 2부터 시작하여 현재 숫자의 배수들을 모두 지웁니다. (자기 자신은 지우지 않습니다) 다음으로 남아있는 수를 찾아서 2의 배수들을 모두 지웁니다. 이 과정을 반복하여 모든 소수를 찾습니다.

에라토스테네스 체 알고리즘의 핵심은 숫자의 배수를 모두 false로 두는 것이다.

모든 수를 하나씩 나누는 방식 [시간 초과 이슈]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static int M;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    int N = Integer.parseInt(st.nextToken());

    while (M < N) {
      isPrime(M);
      M++;
    }
  }

  public static void isPrime (int M) {
    if (M < 2) return;
    for (int i=2; i<M; i++) if (M % i == 0) return;
    System.out.println(M);
  }
}

 

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중