[알고리즘] 소수 구하기

소수(A Prime Number)란? 1과 자기자신 이외의 다른 약수를 가지지 않는 1보다 큰 자연수이다.

 

어떤 수 N이 있을 때 N이 소수인지 아닌지 판별하는 방법을 생각해보자.

N을 2부터 N-1까지 나눠보면서 나머지가 0 이면 중단한다. 

int N;
boolean Prime = true;
for(int i=2; i<N;i++){
	if(N%i==0) {
    		Prime = false;
       	 	break;
        }
}

그러나 이 방법은 시간이 너무 오래걸렸다.

 

그래서 N을 나누는 수가 짝을 이뤄진다는 걸 생각해서 i를 2부터 N의 제곱근까지로 설정해봤다.

int N;
boolean Prime = true;
for(int i=2; i<Math.sqrt(N);i++){
	if(N%i==0) {
    		Prime = false;
       	 	break;
        }
}

그러나 이 방법도 여러가지 수를 구하거나 숫자가 커지면 시간이 오래걸리는 문제가 있었다.

 

그래서 찾아본 결과 '에라토스테네스의 체' 라는 것을 알게되었다.( 참조 블로그 : https://pushback.tistory.com/8 )

방법은 구하고자 하는 최대크기의 N만큼의 boolean 배열을 만들고 전부 true를 넣는다.

0과 1은 소수가 아니므로 false를 넣는다.

그 다음 2부터 해당 숫자가 소수면(true) 그 숫자의 배수를 전부 false로 만든다.

(ex. 2는true 4,6,8,10....은 false 3은 true 6,9,12...는 false)

만약 해당숫자가 소수가 아니면(false) 넘어간다. (4의배수는 이미 2를 계산할 때 모두 false 처리 됐음)

 

int N;
boolean[] Prime = new boolean[N];
Arrays.fill(Prime,true);

Prime[0] = false;
Prime[1] = false;

for(int i=2; i<N;i++){
	if(Prime[i]==true){
        for(int j=i*i ;j<N ;j+=i){
    		Prime[j] = false;
   		}	
	}  
}

 

두번째 for문에서 j가 i*2가 아닌 i*i부터 시작하는 이유는 i*i보다 작은 수는 그 이전 단계에서 이미 처리 됐기때문이다.

(ex. i가 5일 때 5*2 는 이전 단계인 2를 처리할 때 이미 확인, 5*3은 3을 처리할 때 확인, 5*4는 4를처리할때(엄밀히 따지면 2를 처리할 때) 확인 하였음  )

 

 

 

 

[ 알고리즘을 공부한 내용을 정리해보는 공간입니다. 부족한 부분이나 잘못된 부분 지적해주시면 감사하겠습니다.]