037 : 소수 구하기

(Briefing)
문제	단 하나의 맥락	입출력과 되어야 하는 그림
M이상 N 이하의 소수를 모두 출력하는 프로그램을 작성하라	에라토스테네스의 체	I // 자연수 M과 N O // 소수 출력

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // Input Supply Cable
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();

        // Preprocessing
        int[] A = new int[N+1];
        for (int i = 2; i < N; i++) {
            A[i] = i;
        }

        // Operating Sieve
        for(int i = 2; i <= Math.sqrt(N); i++) {
            if (A[i] == 0) {
                continue;
            }
            for (int j = i + i; j <= N; j = j + i) {
                A[j] = 0;
            }
        }

        // Output Extracting Cable
        for (int i = M; i <= N; i++) {
            if (A[i] != 0) {
                System.out.println(A[(int) i]);
            }
        }
    }
}

 

(경향성과 모듈)

- 에라스토테네스의 체 : 2배수부터 시작해서 끝 시행 공간까지 3배수 4배수 등을 지운다

- 프로세스 및 아웃풋에 영향이 가는 것이 아닌, M~N은 그저 계산된 값의 공간을 쪼개는 범위일 뿐이다

그래서 소수를 먼저 구하고, M이상 출력함으로써 원하는 결과를 추출한다

 

(절차적 부분)

- N까지 다 계산하는 것이 아닌, sqrt(N)까지 계산한다

- value를 0으로 만들고, 0이 아닌 것을 출력함으로써 지운다

- 제곱근 계산? > 마지막에 int로 형변환을 해준다