[do it 알고리즘] 백준 1929 (에라토스테네스의 체)

에라토스테네스의 체란?

• 소수를 구할 때 자주 쓰이는 알고리즘
• 구하고자 하는 범위만큼 1차원 배열 생성
• 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열 탐색하며 지우기
• 지워지지 않은 처음 선택된 숫자 = 소수
• 배열의 끝까지 위에 과정 반복

문제 설명

 

풀기 전 생각

• 배열 크기를 N+1로 잡고 0부터 index대로 대입
• 이중 반복문을 사용하여 바깥 반복문은 가장 작은 소수인 i=2부터 시작
• 안쪽 반복문은 j = i +1부터 시작하여 j가 i로 나눠떨어지면 arr [j] = 0으로 지우기
• M~N까지 지워지지 않고 남아있는 소수들 출력

코드

import java.util.*;
public class Baek1929 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[] arr = new int[N+1];
        for(int i = 0; i < arr.length;i++){
            arr[i] = i;
        }

        for(int i = 2; i < arr.length;i++){
            for(int j = i+1; j < arr.length;j++){
                if(j%i==0){arr[j]=0;}
            }
        }

        for(int i = M; i < arr.length;i++){
            if(arr[i] > 1){
                System.out.println(arr[i]);
            }
        }
    }
}

오류 및 개선 

• 테스트 케이스는 통과지만 시간 초과
• j를 하나하나 검사하는 것이 시간 초과의 원인이라고 생각되어 배수만 구해서 지우기

최종 코드

import java.util.*;
public class Baek1929 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[] arr = new int[N+1];

        for(int i = 0; i < arr.length; i++){
            arr[i] = i;
        }

        for(int i = 2; i < arr.length; i++){
            int j = 2;
            while(j*i <= N){
                arr[j*i] = 0;
                j++;
            }
        }

        for(int i = M; i < arr.length;i++){
            if(arr[i] > 1){
                System.out.println(arr[i]);
            }
        }
    }
}

강의 분석

• N의 제곱근까지만 탐색하면 된다.
• N = a * b 일 때, a와 b 모두 N의 제곱근보다 클 수 없기 때문이다.

강의 코드

import java.util.*;
public class Baek1929 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int[] arr = new int[N+1];

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

        for(int i = 2; i <= Math.sqrt(N); i++){ // 제곱근까지만 확인
            if(arr[i]==0) continue; // 무시함으로써 시간 절약
            for(int j = i+i; j <= N; j = j + i){
               arr[j]=0;
            }
        }

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