[백준] 1926 - 소수 구하기 JAVA

Solved.ac Class 완전정복 프로젝트

Class : 2 ~ 2 ++

 

 

 

 

 

---

링크

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

1929번: 소수 구하기

문제

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

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

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

 

접근방법

특정 범위 내 소수를 판별하여 출력하는 문제이다. 범위를 보아하니 느낌이 약간 싸하다. 정답률 또한 소수를 판별하는 로직이 가장 쉬운 방법은 아닐 것 같다는 생각이 들게 한다. 딱 이 느낌만 가지고 문제를 보자. 

 

 

실패 원인

나는 문제를 보고 생각했다.

 

'아, 이 문제 X밥이구나, 오늘 포스팅은 신이 내려주신 개꿀 포스팅이다. 빠르게 조지고 딴 거 해야지!'

 

언제나 그렇듯, 조짐을 당한 것은 나였다. 범위가 너무 크고, 하나의 소수가 아닌 여러 개의 소수를 판단하여 찾아야 하기 때문에 숫자마다 반복문을 통해 찾는 것은 너무 나도 많은 연산을 강요한다. 

 

조짐을 당한 본인

더보기란을 참고하여, 본인이 나와 같은 실수로 이곳까지 왔는지 확인해보자.

시간 초과 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main(){
        Scanner sc =new Scanner(System.in);
        StringBuilder sb =new StringBuilder();
        int start = sc.nextInt();
        int end = sc.nextInt();

        for (int i = start ; i < end+1 ; i++){
            if (isPrime(i)){
                sb.append(i + "\n");
            }
        }
        System.out.println(sb);
    }

    public boolean isPrime (int num){
        boolean toggle = false;

        if(divCnt(num) ==2){
            toggle = true;
        }
        return  toggle;
    }

    public int divCnt(int num){
        int cnt = 0;
        int divider = 1;

        while (divider<=num){
            if (num % divider ==0){
                cnt+=1;
            }
            divider++;
        }

        return cnt;
    }
}​

 

풀이

실패 원인에서 말했듯, 반복문을 통해 찾는 방법은 글렀다. 새로운 방법을 생각해야 한다. 

그래서 다음과 같은 두 가지 방식의 풀이를 제시한다. (속도 차이는 꽤나 크게 난다.)

 

1. 제곱을 이용한 방식

 소수의 정의는 '1과 자기 자신의 수만 약수'로 가지는 수다. 그럼 소수와 소수가 아닌 수의 차이를 분석해보자.

 

• 소수 - 7 : 1  7
• 소수가 아닌 수 - 8 : 1 2 4 8
• 소수가 아닌 수 - 16 : 1 2 4 8 16

소수가 아닌 수들은 모두 대칭성을 갖는 약수가 존재한다. 만약 제곱수가 껴 있다면, 제곱수를 기준으로 딱 절반만큼이 대칭이다. 제곱수를 제외한 모든 약수는 대칭(한 쌍)으로 존재한다. 그러므로, 1보다 크고 제곱수보다 작은 부분에서 약수가 있다면, 당연히 대칭이 되는 약수도 있고, 소수도 아니다. 

 

이 말을 바꿔 말하면 다음과 같다.

 

1부터 해당 수의 제곱근까지 약수가 있는지 확인하면, 해당 수가 소수인지 아닌지 판단할 수 있다.

 

이것을 이용한 풀이 방법이다.

 

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main() {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int start = sc.nextInt();
        int end = sc.nextInt();


        for (int i = start; i < end + 1; i++) {
            int cnt = 0;
            int divider = 1;

            
            //나누는 수의 제곱이 i보다 크면 생각하지 않음
            // i의 제곱근 이상은 생각하지 않음(약수는 대칭이므로)
            while (divider * divider <= i) {

                if (i % divider == 0) {
                    //제곱수는 한번만
                    if (divider * divider == i) {
                        cnt += 1;
                    } else {
                        //나머지는 대칭이니 두개씩
                        cnt += 2;
                    }

                }
                divider++;
            }

            //prime number
            if (cnt == 2) {
                sb.append(i + "\n");
            }
        }

        System.out.println(sb);
    }
}

 

2. 에라스토 테네스의 체

 위의 풀이를 채점하는 시간이 너무 오래 걸려, 양치하고 왔다. 나름 수행 속도를 절반으로 줄인 건데, 그것조차 오래 걸렸다. 그래서 다른 방법을 생각해보기로 했다. 내가 이 문제에서 간과한 점이 무엇일까 생각하다가 찾았다. 이 문제는 '범위'가 한정되어있다. 한정된 범위 내에서 많은 소수를 효율적으로 찾아야 한다. 그럼 찾은 수의 특성을 이용하는 것이 같은 일을 반복하는 것보다 효율적일 수 있을 것이다. 생각은 그렇게 출발한다.

 

 어떤 수가 소수면, 그 수의 배수는 소수가 될 수 없다. 당연하다. 그렇다면, 찾은 숫자의 배수들을 다 지워나가다 보면, 연산을 줄일 수 있지 않을까? 그럼 배수가 아닌 것들만 확인하면 속도가 줄지 않을까? 심지어 문제가 범위를 한정해줬네? 그럼 반복문 써서 할 수 있겠네? 

 

 위와 같은 생각으로 범위를 정해 배열을 만들고, 그 배열에서 소수의 배수들은 모두 걸러낼 것이다. 그렇게 하면 소수만 남기 때문이다. 이렇게 소수를 구하는 방법을 에라스토 테네스의 체라고 한다. 

 

에라스토테네스의 체 (출처 : 위키백과)

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Main test = new Main();
    }

    public Main(){
        Scanner sc =new Scanner(System.in);
        StringBuilder sb =new StringBuilder();
        int start = sc.nextInt();
        int end = sc.nextInt();

        //걸러내는 방식
        boolean[] arr = new boolean[end+1];

        arr[0] = true;
        arr[1] = true;
        //해당 수의 제곱수가 존재한다면, 자신을 제외한 범위 내 배수 True
        for (int i = 2 ; i*i < end+1 ; i++){
            int j = 2;

            while (i*j <= end){
                arr[i*j] =true;
                j++;
            }

        }
        
	//true가 아닌 수는 모두 소수 
        for (int i = start ; i < end+1 ; i++){
            if(arr[i]){
                continue;
            }else{
                sb.append(i+"\n");
            }
        }

        System.out.println(sb);
    }
}

 

 

결과

 

 압도적인 2번 방식의 승리. 범위가 한정되어 있기 때문에, 2부터 시작해서 소수를 구한다고 해도 하나씩 확인하는 방식보다 빠를 수밖에 없다.(물론 이 방식은 배열을 쓰기 때문에, 숫자가 크면 자리도 많이 잡아먹는다.) 상황에 따라 어느 것이 효율적인지 고려해서 사용할 수 있는 능력을 확인하는 문제였다고 생각한다.

 

 

32481430 - 에라스토 테네스의 체 사용

32481046 - 제곱근 사용

 

 

---

포스팅에 문제가 있거나, 설명이 잘못된 부분 지적 환영합니다.

더 나은 퀄리티의 콘텐츠를 제공할 수 있도록 노력하겠습니다.

읽어주셔서 감사합니다.