[백준-자바] 1929번 소수 구하기 (에라토스테네스의 체) / 2022.02.07

 

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

1929번: 소수 구하기

 

* 에라토스테네스의 체

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        // 소수이면 false 소수가 아니라면 true
        boolean sosu[] = new boolean[n+1]; // boolean 형 배열 생성
        sosu[1] = true;                    // 1이면 소수가 아님 -> true
        for(int i=2; i*i<=n; i++)          // i가 2부터 n의 절반까지만 (에라토스테네스의 체)
            if(!sosu[i])                   // 배열에 저장된수가 false일 경우
                for(int j=i*i; j<=n; j+=i) // i가 2라면 j는 4, 6, 8, 10  i가 3이라면 j는 6, 9, 12, 15
                    sosu[j] = true;        // 배수는 소수가 아님 -> true 
        for(int i=m; i<=n; i++){           // 우리가 궁금한 범위는 m이상 n이하
            if(!sosu[i])                   // 범위 중에 false만 출력 (false가 소수)
                System.out.println(i);
        }
    }
}

 

자기 자신은 빼고 배수만 다 지워주면 됨

2라면 2는 뺴고 4 6 8 10은 다 지워주고 3이라면 3 6 9 12 

4라면 2의 배수에서 지워 졌으므로 생략 -> 5로 넘어가서 10 15 20 25