S3 백준-1929번: 소수 구하기

BrokenFinger98·2024년 7월 24일

Problem Solving 백준 수학

Problem Solving

목록 보기

1/29

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

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

예제 입력 1

3 16

예제 출력 1

이론

소수란 1과 자기 자신만을 약수로 가지는 수를 말한다.

접근법 1

import java.util.*;
import java.io.*;

public class Main {
    static int M, N;
    static ArrayList<Integer> ret = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        M = sc.nextInt();
        N = sc.nextInt();

        for(int i = M; i <= N; ++i){
            if(i <= 2) ret.add(i);
            int flag = 0;
            for (int j = 2; j < i; j++) {
                if(i % j == 0){
                    flag = 1; break;
                }
            }
            if(flag == 0) ret.add(i);
        }
        for (Integer a : ret) {
            System.out.println(a);
        }
    }
}

일반적인 소수 판결 알고리즘을 사용해서 코드를 작성했다. 시간초과가 발생해서 더 좋은 알고리즘이 있는지 찾아봤다.

접근법 2

import java.io.*;
import java.util.*;

public class Main {
    static int M, N;
    static ArrayList<Integer> a = new ArrayList<>();
    static ArrayList<Integer> ret = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        
        for(int i = M; i <= N; ++i) a.add(i);

        for (int i = 0; i < a.size(); i++) {
            if (checkPrime(a.get(i))) ret.add(a.get(i));
        }
        for (Integer a : ret) {
            bw.write(a + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static boolean checkPrime(int p){
        if(p < 2) return false;
        for (int i = 2; i*i <= p ; i++) {
            if(p % i == 0) return false;
        }
        return true;
    }
}

N이 소수인지 판별하기 위해 N을 2부터 N-1까지의 수로 나눴을 때, 나누어지지 않으면 소수이다.
36의 약수는 1, 2, 3, 6, 12, 24, 36입니다.
대부분의 경우 6이후에는 일일히 대입해보며 약수를 구하지 않으실 겁니다. 앞에서 구한 약수와 대칭을 이루기 때문입니다.
6은 처음에 약수를 찾고자 했던 36의 제곱근입니다. sqrt(36)의 결과값이죠.
다시 말해, 판단할 숫자의 제곱근까지만 확인해도 소수여부를 확인할 수 있습니다.

접근법 3

import java.io.*;
import java.util.*;

public class Main {
    static int M, N;
    static ArrayList<Integer> a = new ArrayList<>();
    static ArrayList<Integer> ret = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        for(int i = 2; i <= N; ++i) a.add(i);

        int j = a.get(0);
        while (j <= N){
            j = a.get(0);
            a.remove(0);
            if(j >= M && j <= N) ret.add(j);
            int size = a.size();
            for (int i = 0; i < size; i++) {
                if(a.get(i) % j == 0){
                    a.remove(i--); size--;
                }
            }
            if(a.isEmpty()) break;
        }
        for (Integer a : ret) {
            bw.write(a + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
그러나 시간 초과가 났다. 아마 ArrayList를 이용해서 맨 앞의 원소를 삭제하는 과정에서 O(n)이 소요된거 같다.

Solution

import java.io.*;
import java.util.*;

class Main {
    static int N, M;
    // 해당 인덱스가 소수면 false, 소수가 아니면 true로 저장하기 위한 배열
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        
        // M이상 N이하의 중에 소수를 판별해야 함으로 편의를 위해 N+1 사이즈의 배열 생성
        check = new boolean[N+1];
        
        // 0, 1은 소수가 아니므로 true저장
        check[0] = true;
        check[1] = true;
        
        // 에라토스테네스의 체와 제곱근을 이용하여 소수 판별
        for (int i = 2; i*i<=N; i++) {
            if(!check[i]){
                for(int j = i+i; j <= N; j+=i) {
                    check[j] = true;
                }
            }
        }
		
        // 소수 출력
        for(int i = M; i <= N; i++) {
            if(!check[i]) bw.write(i + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}