반응형

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.


N까지의 수중에 소수를 판단하는 상황이 생길 경우 유용하다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private static void primeNumber(int n){
        // 에라토스테네스의 체
        // N 보다 작은 소수를 구한다.
        boolean[] arr = new boolean[n+1];
        Arrays.fill(arr, true);
        
        for (int i=2; i<=n; i++){
            if (arr[i]){
                
                for (int j=i*i; j<=n; j=j+i){
                    arr[j] = false;
                }
            }
        }
        
        for(int i=0; i<arr.length; i++){
            if (arr[i]){
                System.out.print(i + " " );
            }
        }
    }
cs



참고자료 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4


728x90
반응형

'Development > Algorithm' 카테고리의 다른 글

[Try-catch]대문자 출력  (0) 2013.11.04
[Programing Challenges]반전한 수 더하기  (0) 2013.02.12
[Hacker Cup]Find the Min  (0) 2013.02.01
[Hacker Cup]Balanced Smileys  (0) 2013.01.31
[Programming Challenges] The 3n+1 Problem  (0) 2011.09.01

+ Recent posts