1929.소수구하기

문제

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

입력

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

출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	256 MB	255621	74495	52354	27.211%

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

풀이

알고리즘

이 문제는 에라토스테네스의 체 알고리즘을 사용하여 문제에 접근해야한다. 소수를 구하는 다양한 방법이 있지만 에라토스테네스의 체가 가장 대중적이고 알고리즘 효율이 매우 좋은 방법이다.

일단 소수가 무엇인지 알아보자.

소수 (Prime Number)
소수의 정의는 1보다 큰 자연수 중 1 과 그 수 자기 자신만을 약수로 갖는 자연수를 의미

그럼 에라토스테네스의 체를 이용하여 소수를 구하는 방법을 알아보자.

소수를 구하는 대표적인 방법 중 하나다.

" k=2 부터 √N 이하까지 반복하여 자연수들 중 k를 제외한 k의 배수들을 제외시킨다"

순서는 다음과 같다.

• k = 2 이면 2 를 제외한 2의 배수를 모두 지워준다.
• k = 3 이면 3 을 제외한 3의 배수를 모두 지워준다.
• (4는 이미 k = 2 에서 제외되어 넘어간다.)
• k = 5 이면 5 를 제외한 5의 배수를 모두 지워준다.
• 이렇게 하여 k = √N 까지 반복하는 방법이다.

여기서 √N 이하까지만 반복하면 되는 이유는 뭘까?

소수를 판별한 다는 것은 결국에 1과 자기 자신을 제외한 다른 자연수를 약수로 가지면 안된다는 의미이다.

임의의 자연수 𝐍 (𝐍 > 0) 이 있다고 가정하자.

𝑝 × 𝑞 = 𝐍 을 만족할 때 아래와 같은 부등식을 완성할 수 있다.

( 1 ≤ 𝑝 , 𝑞 ≤ 𝐍 )

그리고 𝑝 와 𝑞 중 하나는 √N 보다 작거나 같다.

예로들어 𝐍 = 12 라고 하자.

그러면 아래와 같이 두 수의 곱으로 표현할 수 있다.

1 × 12

2 × 6

3 × 4

4 × 3

6 × 2

12 × 1

여기서 볼 수 있듯이 만약 𝑝 가 증가한다면 자연스레 𝑞 가 감소하고,

반대로 𝑝 가 감소한다면 자연스레 𝑞 가 증가한다.

그리고 𝑝 와 𝑞 는 𝐍의 약수이기 때문에 결국 𝐍 을 임의의 수로 나누게 되면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수 밖에 없다.

결과적으로 𝑝 와 𝑞 중 하나는 반드시 √N 보다 작거나 같다.

즉, √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미이므로 소수가 아니게 되는 것이다.

참고자료 st-lab 블로그

코드

첫번째시도

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class 소수구하기 {  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  

        int m = Integer.parseInt(st.nextToken());  
        int n = Integer.parseInt(st.nextToken());  

        for(int i=m; i<=n; i++){  
            for(int j=2; j<=i; j++){  
                if(j == i) { //자기자신까지와서 나눠지면 출력하고 다음숫자로  
                    System.out.println(j);  
                    break;  
                }  
                else if (i % j != 0) { //나눠서 0이 아니면 계속진행  
                    continue;  
                }else break; //자기자신이외의 것으로 나눠지면 출력하지않고 종료함  
            }  

        }  

        br.close();  
    }  
}

이방법으로 는 실패하였다.. 시간초과가 뜨는데 for문을 2번 사용한것이 문제였다.

2번째 시도

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class 소수구하기 {  


    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  
        StringBuilder sb = new StringBuilder();  

        int m = Integer.parseInt(st.nextToken());  
        int n = Integer.parseInt(st.nextToken());  

        //소수인지 아닌지 판단하여 저장한다. 배열생성시 디폴트는 false다.  
        boolean[] prime = new boolean[n + 1];  

        for (int i = 2; i <= n; i++) {  
            if (prime[i]) continue; //소수배열이 참일때 넘어간다.  

            if (i >= m) sb.append(i).append("\n"); //i가 m보다 크거나 같으면 i를 출력값에 넣어준다.  

            //true : 소수아님 , false : 소수
            for (int j = i + i; j <= n; j += i) {  
                prime[j] = true; //조건에 맞으면 true로 변경해준다.
            }  
        }  
        System.out.println(sb);  
        br.close();  
    }  
}

성공!
답지를 보고문제를 작성하였다. 하지만 for문이 중복되는 부분을 이해할수가 없어서 좀더 찾아봐야될것같다. 그래서 생각해낸 방법은 아래와 같다.

3번째 시도

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class 소수구하기 {  

    public static boolean[] prime;  

    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");  
        StringBuilder sb = new StringBuilder();  

        int m = Integer.parseInt(st.nextToken());  
        int n = Integer.parseInt(st.nextToken());  

        //소수인지 아닌지 판단하여 저장한다. 배열생성시 디폴트는 false다.  
        prime = new boolean[n + 1];  

        getPrime();  

        for (int i=m; i<=n; i++){  
            if(!prime[i]) System.out.println(i);  
        }  

        br.close();  
    }  

    private static void getPrime() {  
        //true : 소수 아님, false : 소수  
        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;  
            }  
        }  
    }  
}