알고리즘 단계별로 풀어보기 : BOJ-1929(소수구하기)

문제(출처)

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력

3 16

예제 출력

3

5

7

11

13

내 풀이

\import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

public class Main {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        

        String[] num = br.readLine().split(" ");

        

        int m = Integer.parseInt(num[0]);

        int n = Integer.parseInt(num[1]);

        

        int[] arr = new int[n+1];

        

        for(int i = 2; i <= n+1; i++) {

            for(int j = 2; j * i <= n; j++) {

                arr[i*j] = 1;

            }

        }

        

        arr[0] = 1;

        arr[1] = 1;

        

        for(int i = m; i < arr.length; i++) {

            if(arr[i] == 0) {

                bw.write(String.valueOf(i));

                bw.newLine();

            }

        }

        bw.close();

        

    }

}

내 풀이 해석

동적계획법으로 문제를 해결하는 방법입니다.

m에서부터 n까지 소수를 구하는 과정에서 이미 소수가 아님을 판별한 수는 체크합니다.

2, 3, 5, 7의 배수에 해당 하는 수는 소스가 아니므로 배수로 증가하면서 제외하고 소수만 출력합니다.

아쉬운 점

이미 확인 값에 대해서 중복으로 계산하는 방법만 생각했었습니다.

시간 초과가 발생해서 다른 방법을 생각하게 되었습니다.

링크드 리스트를 생각했으나 100000 이상이 되니까 90초가 걸렸습니다.

배열로 다시 문제를 푸느라 시간이 좀 들었습니다.

학습/검색

참고