백준 1929 소수 구하기 (JAVA)

문제

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

입력

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

출력

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

소수를 구하여 출력하는 문제였다.

앞선 문제들에서 소수를 이미 다뤘기 때문에 비슷한 형식으로 작성해 보았다.

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

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));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int cnt = 0;

        for(int i=M;i<=N;i++,M++){
            for(int j=2;j<M;j++){
                if(M%j==0){
                    cnt++;
                }
            }
            if(cnt <= 0){
                bw.write(Integer.toString(M)+"\n");
            }
            cnt = 0;
        }

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

오잉, 근데 결과에서 시간초과가 나왔다....

허허,,, 문제에서 제한시간이 2초였는데,,,

반복문이 시간을 많이 잡아먹기 때문에 문제를 수정해주어야했다.

어떻게 줄일까 고민하다 중간에 break문을 넣어 약수가 존재하면 빠르게 반복문을 탈출하는 코드를 작성해 보았다.

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

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));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int i = 2;

        if(M==1 || N==1){
            M = 2;
        }

        for(int j=M;j<=N;j++,M++){
            while(true){
                if(i<M && M%i==0){
                    break;
                }
                if(i>=M){
                    bw.write(Integer.toString(M)+"\n");
                    break;
                }
                i++;
            }
            i =2;
        }

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

 

2중 for문이 아닌, for문 안에 while문을 사용하고 중간중간 break를 넣어 빠르게 반복문을 탈출할 수 있도록 했다.

하지만,,

이 역시 시간초과가 나왔다......

역시 이 문제는 수학적으로 식을 세우거나 수학적 사고를 통해 푸는 문제였다...

결국 고민하다 다른 블로그를 찾아보니, '소수'에 대해 알고리즘의 관점으로 잘 설명해 주신 글이 있었다.

https://st-lab.tistory.com/81

JAVA [자바] - 소수 구하는 알고리즘 및 구현

이 글을 읽고 힌트를 얻어 다시 작성해 보았다.

 

 

---

 

기존에는 처음 입력값 M을 중심으로 j를 하나씩 늘려가며 %를 활용해 나머지가 있는지 검사하였다.

for(int i=M;i<=N;i++,M++){
            for(int j=2;j<M;j++){
                if(M%j==0){
                    cnt++;
                }
            }

이번에는 M이 아닌, 루트M을 중심으로 계산하였다.

 

갑자기 루트(제곱근)가 나온 이유는 다음과 같다.

 

우선 16을 소인수분해 해보자

1 X 16

2 X 8

4 X 4

8 X 2

16 X 1

위와 같은 약수들이 존재한다.

특징을 잘 살펴보면 16의 제곱근 이하로 나눠질 경우 16은 약수가 존재한다는 사실을 알 수 있다.

즉 16의 제곱근 4이하의 숫자로 16이 나눠진다면, 16은 소수가 아닌 것이다.

 

몇가지 예를 더 보자.

'19'

19의 제곱근은 약 4.35이다.

4.35이하의 자연수 중에서 19로 나눠지는 것이 있는가? 없다.

19는 소수이다.

 

'25'

25의 제곱근은 5이다.

5이하의 자연수 중에서 25로 나눠지는 것이 있는가? '5'가 있다.

25는 소수가 아니다.

 

이를 활용해 조건문이 반복되는 횟수를 줄였다.

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

public class Main{

    
    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++){
            if(N == 2){
                System.out.println(N);
                break;
            }
            prime(i);
        }

    }

    public static void prime(int number){

        if(number < 2){
            return;
        }
        
        
        for(int i=2;i<=Math.sqrt(number);i++){
            if(number%i==0){
                return;
            }
        }
        System.out.println(number);
    }
}

  

위와같이 시간을 줄여주었더니 정답!