알고리즘 - 에라토스테네스의 체 - 소수 판별 알고리즘

안녕하세요, 알고리즘을 정리하는 포스팅입니다. 다른 알고리즘을 참고하시려면 해당 카테고리를 이용해주세요. 😊

'🌻 JAVA/알고리즘, 자료구조' 카테고리의 글 목록

 

 

 

소수 란?

---

 1을 제외한 수들 중, 그 수의 약수가 1 과 자기 자신으로만  이루어진 수를 말한다.
ex) 2, 3, 5, 7, 11, 13 ......

 

소수를 찾아보자

---

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

이 중에서 소수인 2, 3을 이용해서 2와 3의 배수들을 차례로 다 지워 보겠다.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20

그러면 남는 수는 소수가 된다.  [2, 3, 5, 7, 11, 13, 17, 19 ...] 

 

코드로 옮겨보자

---

// 소수 찾기
int number = 20;
int[] num_arr = new int[number];

// 0부터 20까지 배열에 넣는 코드 생략.

for(int i=2; i <= number; i++){
	if(num_arr[j] == 0) continue;
    
	for(int j=i+i; j <= number; j += i){        
        num_arr[j] = 0;
    }
}

일단 2중 for문을 이용하여, 바깥 for문에 i는 2부터 시작하고 안쪽 for문에 2의 배수만 찾아서 0을 넣어준다. (그렇다면 해당 수의 해당하는 배열의 값이 0 이면 소수가 아닌 것이다.) 그렇게 2부터 20까지 쭉 반복한다. 중복 체크를 피하기 위해 배열의 값이 이미 0인 경우는 건너뛰도록 한다.

 

이게 바로 에라토스테네스의 체 이다.

 

소수인지 판별하기

---

// num_arr[i] != 0 이면 소수이다!
for(int i=2; i< num_arr[i]; i++){
	if(num_arr[i] != 0)
		System.out.println( num_arr[i] + " ");
}

이미 구해놓은 배열을 순회하면서, num_arr[i] 값이 0이 아닐때만 출력해주면 된다.

 

 

 

 

+ 배열 없이 소수 판별하는 코드

---

public Boolean isPrimeNumber(int num) {
        int sqrt = (int)Math.sqrt(num); // 제곱근까지만 체크(시간복잡도 줄이기)
        for (int i = 2; i <= sqrt; i++) {
            if (num % i == 0) { 
                return false;
            }
        }
        return true;
    }

시간복잡도를 줄이기 위해서 주어진 수의 제곱근 까지만 순회를 하면서, num을 한번이라도 나누어 진다면 그 수는 소수가 아닌 것이다.