JAVA/알고리즘

백준 1929번 소수 구하기 문제

위들 wedul 2018. 10. 5. 00:25
반응형

일반적으로 소수 구하는 방식으로 진행하면 시간이 너무 걸려서 에러가 발생한다. 그래서 고민하던 중에이런 생각이 났다. 모든 수는 자신의 제곱근 이상의 수로 나눠지지 않기 때문에 자신의 제곱근까지 2이상의 자연수로 나눠지는지 판단하면 된다고 생각했다. 

그 결과 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
 
        List<Integer> result = new ArrayList<>();
 
        // 순환
        for (int i = n; i <= m; i++) {
            if (isDecimal(i)) {
                result.add(i);
            }
        }
 
        // 결과 출력
        result.stream().forEach((e) -> {
            System.out.println(e);
        });
 
    }
 
    /**
     * 소수 체크
     *
     * @param num
     * @return
     */
    private static boolean isDecimal(int num) {
 
        if (1 == num) {
            return false;
        }
 
        /**
         * 자연수는 자신의 제곱근 이상의 수로 나눠지지 않는다는 조건을 이용해서, 자신의 제곱근 수 까지의 수로 나눠지는지 여부를 판단.
         */
        int sqrpData = new BigDecimal(Math.sqrt(num)).intValue();
 
        for (int i = 2; i <= sqrpData; i++) {
            if (num % i == 0) {
                return false;
            }
        }
 
        return true;
    }
 
}
cs


728x90
반응형