백준 1929 소수구하기

{% embed url=“https://www.acmicpc.net/problem/1929” %}

Solution 1

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        boolean[] isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);

        isPrime[0] = isPrime[1] = false;
        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 = 0; i <= n; i++) {
            if (isPrime[i] && i >= m) {
                System.out.println(i);
            }
        }

    }
}
Java
복사

•

시간 복잡도 : 920 ms

•

공간 복잡도 : 35432 kb

•

풀이 과정 :

◦

에라토스테네스의 체를 이용하여 풀었다.

◦

그를 위해 길이가 n+1 인 boolean 배열을 만들어 소수 여부를 체크했고,

◦

출력시에는 해당 수가 m 이상인지 체크하는 조건을 추가하여 그 이전의 수는 출력되지 않도록 하였다.

Solution 2

string builder 로 답안 모두 더하여 한번만 출력하는 방법

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main {    public static boolean[] prime;    public static void main(String[] args) throws IOException {        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");        int m = Integer.parseInt(st.nextToken());        int n = Integer.parseInt(st.nextToken());        prime = new boolean[n+1];        prime();        StringBuilder sb = new StringBuilder();        for (int i = m; i <=n; i++) {            if(!prime[i]) {                sb.append(i).append('\n');            }        }        System.out.print(sb);    }    private static void prime() {        //false = 소수, true = 소수가 아님        prime[0] = prime[1] = true;        for (int i = 2; i <= Math.sqrt(prime.length); i++) {            if (prime[i]) {                continue;            }            for (int j = i*i; j < prime.length; j += i) {                prime[j] = true;            }        }    }}
Java
복사

•

시간 복잡도 : 224 ms

•

공간 복잡도 : 20196 kb

•

풀이 과정 :

◦

풀이 과정은 비슷하나, BufferedReader, StringBuilder 등을 써서 입출력 시간을 단축하고자 했음

◦

또한 boolean 배열인 isPrime 을 반대로 적용하여, false 요소들만 출력되도록 하여, 최초에 true 로 초기화했던 시간을 단축했음