정수론 - 에라토스테네스의 체

소수

1과 자기자신 이외에는 약수가 없는 수

단일 숫자의 소수여부 확인

자연수 N이 소수인지를 판별하는 가장 간단한 방법은 2~(n-1)까지 모두 나눠보는것이다. 하지만 비효율 적이다.

효율적인 방법

N의 약수는 모두 N의 제곱근이하이기 때문에 N의 제곱근 이하의 수로 나누어 나누어 떨어지는지 확인한다.
2~N 사이의 수의 제곱근으로 N을 나누어서 나누어떨어지면 소수가 아니다.

에라토스테네스의 체

N까지의 수에서 소수인 수를 걸러내는 법

• 구현법

1. N크기의 배열을 생성후 2~N까지에 자연수를 모두 배열에 저장
2. 남아있는 수에서 가장 작은 수를 찾는다.
3. 가장 작은 수를 제외한 가장 작은 수의 배수를 모두 제거 한다

루트N 이하인 수를 통해 제거한뒤 제거되지 않은 루트N이상인 수는 모두 소수이다.

구현코드

1. 배열을 이용하여 구현

• 가장작은수의 배수를 배열에서 제거하는 기능을 A[i] = 0 을 통해서 구현한다.

public class A {

	public static void main(String[] args) {
		int[] A = new int[10000001];
				
		for(int i=2; i<A.length; i++) {
			A[i]=i;
		}
		
		for(int i =2; i<Math.sqrt(A.length); i++) {
			if(A[i]==0) {
				continue;
			}
			for(int j=i+i; j<A.length; j=j+i) {
				A[j] = 0;
			}
		}
		System.out.print("finish");
	}
}

2. LinkedList를 사용하여 구현

• 배열에 비해 효율성이 많이 떨어짐

public class A {

	public static void main(String[] args) {
		LinkedList<Integer> arr = new LinkedList<Integer>();				
		for(int i= 2; i<=1000; i++) {
			arr.add(i);
		}
		
		int i = 0;
		int min;
		while(arr.get(i) <= Math.sqrt(1000)) {
			min = arr.get(i);
			for(int j=i+1; j<arr.size(); j++) {
				if(arr.get(j)%min ==0) {
					arr.remove(j);
				}
			}
			i++;
		}
		
		System.out.print("finish");
	}
}

결론

위의 두 코드에서 자료구조의 차이로 인해 시간 복잡도가 상당한 차이를 보였음 에라토스테네스의 체를 구현하기 위해서는 배열을 사용하는 것이 훨씬 효율적이다.