[Algorithm] 에라토스테네스의 체

소수

• 양의 약수를 두 개만 가지는 자연수를 의미한다.
• 모든 수의 공통적으로 포함되는 양의 약수는 1이 존재하므로 1과 자기 자신만을 약수로 갖는 수를 의미한다. 
• ex ) 2, 3, 5, 7, 9 ... 등

 

에라토스테네스의 체

• 소수(Prime Number)를 판별해주는 알고리즘이다. 
• 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 

 

원리

가장 먼저 소수를 판별할 범위만큼 배열을 할당하여 해당하는 값을 넣어주고 이후에 하나씩 지워나가는 방법을 이용한다. 소수가 되는 수의 배수를 지우면 남은 건은 소수만 된다. 

 

1. 배열을 생성하여 초기화한다. (2부터 소수를 구하고자 하는 구간의 모든 수를 나열)

2. 2부터 시작해서 자기 자신을 제외한 특정 배수를 모두 지운다.

1) 처음에 있는 자기 자신(2)을 제외한 2의 배수를 모두 지운다.

2) 남아있는 수 가운데 3은 소수이므로 제외한다.

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

4) 남아있는 수 가운데 5는 소수미으로 제외한다.

5) 자기 자신(5)을 제외한 5의 배수를 모두 지운다.

6) 위 과정을 반복한다. 

3. 2부터 시작하여 남아있는 수를 모두 출력한다. 

 

 

코드

[ 방법 1 ]

public class Eratos {
	
	static final int NUMBER = 100000;
	static int intArr[] = new int[NUMBER+1];
	static boolean booleanArr[] = new boolean[NUMBER+1];
	
	public static void main(String[] args) {
		
        // 1. 배열을 생성하여 초기화
		for(int i=2; i<=NUMBER; i++) {
			intArr[i] = i;
		}
		
        // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
		for(int i=2; i<=NUMBER; i++) {
			if(intArr[i]==0) continue;
			
			for(int j=2*i; j<=NUMBER; j+=i) {
				intArr[j] = 0;
			}
		}
		
        // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
		for(int i=2; i<=NUMBER; i++) {
			if(intArr[i]!=0) System.out.println(intArr[i]); 
		}
		
	}
}

 

[ 방법 2 ]

 

public class Eratos {
	
	static final int NUMBER = 100000;
	static int intArr[] = new int[NUMBER+1];
	static boolean booleanArr[] = new boolean[NUMBER+1];
	
	public static void main(String[] args) {
		
		booleanArr[0] = booleanArr[1] = true; // 소수는 false, 1과 0 제외
		
		for(int i=2; i*i<=NUMBER; i++) {
			if(!booleanArr[i]) {
				for(int j=i*i; j<=NUMBER; j+=i) booleanArr[j] = true;
			}
		}
		
		for(int i=2; i<=NUMBER ; i++) {
			if(!booleanArr[i]) System.out.println(booleanArr[i]); 
		}
		
	}
}

 

 

 

 

 

[Algorithm] 에라토스테네스의 체

 

[JAVA] 소수 구하는 알고리즘 : 에라토스테네스의 체