[BOJ - JAVA] 1929 - 소수 구하기

# 주소

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

1929번: 소수 구하기

 

# 문제

# 문제 해설 및 코드 리뷰

 

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        
        for(int i = n; i <= m; i++) {
            int count = 0;
            int x = (int)Math.sqrt(i);
            for(int j = 1; j <= x; j++) {
                if(i % j== 0) {
                    count++;
                    continue;
                }
            }
            if(count == 1 && i != 1)
                System.out.println(i);
        }
    }
}

 

진짜 까다로운 문제입니다.

코드는 딱 봤을 때 어려운 것 하나 없어보일 수 있겠지만 사실 이 개념이 수학적인 개념이 많이 들어간 터라

조금 어려우실 수 있겠습니다.

아마 다른 어떤 블로그에도 저처럼 푼 분이 있을까... 싶네요.

정수론 책을 살펴보면(이것도 수학과를 나와야만 알 수 있습니다...) 소수를 찾을 때 이런 내용이 있습니다.

 

"어떤 수를 제곱근을 씌웠을 때 그 수의 이하의 수들로 나뉘어 떨어지지 않는다면 그 수는 소수다" 

라는 내용이 나옵니다.

다른 분들은 현대대수학 개념인 에라토스테네스의 체를 도입하셨지만 저는 이게 더 쉬울 것 같아 이걸로 풀이했습니다.

 

자 예를들어 17이하의 소수를 구해보도록 하겠습니다.

17에 제곱근을 씌우면 루트 17이고 이는 4.xxx 이므로 4이하의 수들로 나누어 보겠습니다.

2,3,4로만 나누면 됩니다.(1은 소수가 아니므로 제외)

그럼 어떤 수로도 나뉘어 떨어지지 않는 것을 확인할 수 있습니다. 그러므로 17은 소수가 됩니다.

이를 토대로 로직을 짜보시면, n과 m을 입력받아 이중 for문으로 풀이하여도 시간초과가 뜨지 않습니다.

그리고 제곱근을 씌울 땐 Math.sqrt를 이용하였고 남는 소수점은 앞에 (int)를 붙여 정수타입으로 변환시키면 자동으로

버림이 이루어집니다.

 

이후, j = 1부터 시작하여 i % j의 나머지가 0이 될때마다 count++를 수행하도록 짰는데, 처음에 j = 2부터 했다가

계속 85%에서 시간 초과가 떠서 한참을 고민했었습니다.

그런데, j = 1 이 입력되어도 1은 알아서 걸러지도록 코딩을 짜야함을 깨달았고(1은 소수가 아니므로)

j = 1부터로 포함하되 if(j != 1) 을 첨가하여 로직을 짰더니 원하는 출력값을 얻을 수 있었습니다. 

감사합니다.