소수(prime number) 판별 알고리즘

1. Problem

- 1부터 n까지의 수 중 소수를 찾아보자.

 

2. Input

1) int n

 

3. Output

1) [1, n]의 자연수 중 소수를 찾아 출력

 

4. Explanation

1) 기본 알고리즘

- x는 1부터 n까지의 수 중 하나이다.

- 2부터 x-1까지 1씩 증가시켜 가며 x를 나눠본다. 1개라도 x를 나누어 떨어지게 한다면 x는 소수가 아니다.

2) n의 제곱근까지만 찾아보는 알고리즘

- x는 1부터 n까지의 수 중 하나이다.

- a*a = x가 되는 a를 구한다. 이때 a가 자연수가 아니라면 소수점 이하를 버린다.

- 2부터 a까지 1씩 증가시켜 가며 x를 나눠본다. 1개라도 x를 나누어 떨어지게 한다면 x는 소수가 아니다.

3) 에라토스테네스의 체를 이용한 알고리즘

- 1부터 n까지의 숫자를 나열한다.

- 2를 제외한 2의 배수를 모두 지운다.

- 3을 제외한 3의 배수를 모두 지운다.

- 4는 이미 지웠으니 넘어간다.

- 이런 식으로 지워지지 않은 수 p가 있다면 p를 제외한 p의 배수를 모두 지운다.

- n까지 모두 살펴봤다면, 남은 수 중 1을 제외한 모든 수가 소수가 된다.

 

5. Code

1) 기본 알고리즘

static void findPrime(int n) {
    for(int i=1 ; i<=n ; i++) { // 1부터 n까지의 수를 모두 훑어본다.
        boolean isPrime = i>1;
        for(int j=2 ; j<i && isPrime ; j++){ // i가 소수인지 판단한다.
            if(i%j==0)
                isPrime = false;
        }
        if(isPrime) // i가 소수일때만 출력한다.
            System.out.print(i+",");
    }
}

// main()
int n = 100;
findPrime(n);
// 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

- 소수 판단 알고리즘은 O(n)을 따른다.

 

2) n의 제곱근까지만 찾아보는 알고리즘

static void findPrime(int n) {
    for(int i=1 ; i<=n ; i++) { // 1부터 n까지의 수를 모두 훑어본다.
        boolean isPrime = i>1;
        for(int j=2 ; j<=(int)Math.sqrt(i) && isPrime ; j++){ // i가 소수인지 판단한다.
            if(i%j==0)
                isPrime = false;
        }
        if(isPrime) // i가 소수일때만 출력한다.
            System.out.print(i+",");
    }
}

// main()
int n = 100;
findPrime(n);
// 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

- 소수 판단 알고리즘은 O(n^(1/2))을 따른다.

 

3) 에라토스테네스의 체를 이용한 알고리즘

static void findPrime(int n) {
    boolean[] nums = new boolean[n+1]; // nums[i]의 초기값은 false
    for(int i=2 ; i<=n ; i++)        // 2부터 n까지 차례대로 훑으면서
        if(nums[i]==false) {         // 아직 지워지지 않았다면
            System.out.print(i+","); // 소수이기 때문에 출력하고
            for(int j=i*2 ; j<=n ; j+=i) // 그 수의 배수들은 모두 지운다.
                nums[j] = true;
        }
}

// main()
int n = 100;
findPrime(n);
// 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

- 소수 판단 알고리즘은 O(n*log(logn))을 따른다.