에라토스테네스의 체

소수를 판별하는 알고리즘

 

소수란 양의 약수를 두  개만 가지는 자연수

2,3,5,7,11.... 등이 해당된다.

이러한 소수를 대량으로 빠르게 구하는 방법이 에라토스테네스 체입니다.

 

 

먼저 소수 판별하는 알고리즘 코드를 보자

function isPrime(x){
	for(var i=2;i<x;i++){
    	if(x%2==0) false;
    }
    return true;
}

위 알고리즘의 시간복잡도는 O(N)입니다.

모든 경우의 수를 모두 다 돌며 약수인지를 확인한다는 점에서 비효율적입니다.

이를 O(N^(1/2))로 가능하게 할 수 있다.

8의 약수는 1 , 2, 4, 8이 존재합니다

8의 약수 중 1과 8을 제외하고 2와 4는 아래와 같은 대칭을 이룹니다.

2*4=4*2 

그러므로 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 된다. (8의 경우 2까지만 구해도 끝이다.)

8의 제곱근은 2.82...이니까

function isPrime(x){
	for(var i=2;i<Math.sqrt(x);i++){
    	if(x%2==0) false;
    }
    return true;
}

이렇게 더 효율적으로 소수를 구할 수 있다.

 

이제 한 두개의 소수를 판별하는 것이 아니라 대량의 소수를 한번에 판별하고자 할 때 사용하는 것이 에라토스테네스의 체입니다.

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열안에 그 인덱스에 해당하는 값을 넣어줍니다.

 

1. 먼저 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

2. 2부터 시작해서 특정숫자의 배수에 해당하는 숫자들을 모두 지운다.

      -> 1은 소수가아니니까 건너뛰고, 2부터 시작한다.

         ->  먼저 2의 배수를 지웁니다.(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

3. 3의 배수를 지운다.(자기자신 제외)

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

4. 이미지워진 숫자의 경우 건너뜁니다.

4는 이미 지워졌으니까 건너뛴다.

5. 5의 배수를 지운다.->이러한 과정은 반복

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

6. 2부터 시작해 남은 숫자들을 출력한다.

2, 3, 7, 11, 13, 19, 23

 

이를 소스코드로 옮겨보자

 

var number=100000;
var arr=Array(number);

function isprime(){
	for(var i=2;i<number; i++){
    	a[i]=i
    }
    for(var i=2;i<number; i++){
    	if(a[i]==0) continue;//이미 지워진 숫자는 무시한다.
        //지워진숫자가 아니라면
        //j=i+i 그 숫자의 배수부터 시작
        //j는 i만큼 증가(배수를 의미)
        for(var j=i+i;j<number; j+=i){
    		a[j]=0; //0은 지워진 숫자라는 의미
    	}
    }
    for(var i=2;i<number; i++){ //지워지지않은 소수들 출력
    	if(a[i]!=0) console.log(a[i]);
    }
}