Java/알고리즘

에라토스테네스의 체 (소수찾기)

SeongWon 2021. 9. 15. 18:01
반응형

1. 소수(prime number)

 

소수란, 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 갖는 자연수를 의미한다.

ex) 7 -> 1,7  <소수O>

     9 -> 1,3,9 <소수X>

 

이처럼 소수는 2개의 약수만을 갖고, 그 약수는 1과 자신 뿐이다. 만약 이 외의 약수를 갖고있는 자연수라면 소수라고 할 수 없으며 합성수라고 부르게 된다.

 

2. 에라토스테네스의 체

 

에라토스테네스의 체는 가장 대표적인 소수(prime number) 판별 알고리즘이다. 

진행 방법은 아래와 같다.

 

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
  2. 2는 소수이므로 오른쪽에 2를 쓴다.
  3. 자기 자신을 제외한 2의 배수를 모두 지운다.
  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
  5. 자기 자신을 제외한 3의 배수를 모두 지운다.
  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
  7. 자기 자신을 제외한 5의 배수를 모두 지운다.
  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
  9. 자기 자신을 제외한 7의 배수를 모두 지운다.
  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

즉, N이하의 수를 모두 나열했을 때, 2부터 시작하여 해당 수가 소수라면 그 수를 제외하고, 그 수의 배수들은 모두 나열한 수에서 지워준다는 의미이다. 이처럼 나열한 수에서 지워나간다면 마지막에는 소수들만이 남게된다.

 

아래의 위키백과를 참고한다면 이해하는데 큰 도움이 될 것이다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서

ko.wikipedia.org

 

 

알고리즘 1

 

위와 같이, '에라토스테네스의 체'의 원리를 이용하여 알고리즘을 구현한다면,

각각의 숫자들을 소수인지 아닌지를 판별하여 리스트에 추가하는 방식으로도 가능하다.

 

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		for(int i=1; i<=N; i++) {
			boolean prime = true;
			for(int j=2; j<i; j++) {
				if(i%j==0) {
					prime = false;
					break;
				}
			}
			if(i>1 && prime==true) {
				list.add(i);
			}
		}
		
		System.out.println(list);
		
		sc.close();
	}
}

// 입력 : 20
// 결과 : [2, 3, 5, 7, 11, 13, 17, 19]

 

 

boolean 타입으로 prime을 상위 반복문이 돌 때마다 true로 초기화 시켜준다.

그리고 i를 j로 계속 나눠보면서 나머지가 0이 되는 값이 하나라도 존재한다면 약수가 자신을 포함해서 3개 이상이

되기 때문에, 그 수는 더 이상 소수가 아니므로 prime을 false로 할당하고 break문으로 바로 빠져나와준다.

 

그러나 위 알고리즘은 내부의 반복문을 N번 반복하므로 시간복잡도는 O(N²) 이다.

 

 

 

알고리즘 2

 

위의 방법은 입력받은 N이 커질수록 처리 효율이 매우 떨어지게 된다.

그래서 N을 √N 이하의 자연수들로만 나누는 방법을 사용한다. 그 이유를 살펴보자.

 

임의의 자연수 N (N > 0) 이 있다고 가정하자.

 𝑝 × 𝑞 = N 을 만족할 때 우리는 아래와 같은 부등식을 완성할 수 있다.  ( 1 ≤  𝑝 , 𝑞 ≤ 𝐍 )

그리고 𝑝 와 𝑞 중 하나는 √N 보다 작거나 같다.

 

예로들어  𝐍 = 16 라고 하자.

그러면 아래와 같이 두 수의 곱으로 표현할 수 있다.

 

1 × 16

2 × 8

4 × 4

8 × 2

16 × 1

 

여기서 볼 수 있듯이 만약 𝑝 가 증가한다면 자연스레 𝑞 가 감소하고,

반대로 𝑝 가 감소한다면 자연스레 𝑞 가 증가한다.

 

그리고 𝑝 와 𝑞 는 N의 약수이기 때문에 결국 N 을 임의의 수로 나누게 되면 임의의 수가 √N 보다 작다면 결국 나머지는 √N 보다 클 수 밖에 없다.

 

결과적으로 𝑝 와 𝑞 중 하나는 반드시 √N 보다 작거나 같다.

 

즉, √N 이하의 자연수 중에 나누어 떨어지는 수가 있다면 이는 1 과 N 을 제외한 다른 자연수가 N 의 약수라는 의미이므로 소수가 아니게 되는 것이다.

 

for(int i=1; i<=N; i++) {
	boolean decimal = true;
	for(int j=2; j<=Math.sqrt(i); j++) {
		if(i%j==0) {
			prime = false;
			break;
		}
	}
	if(i>1 && prime==true) {
		list.add(i);
	}
}

 

즉, 내부 반복문의 횟수를 √N보다 작거나 같을 때까지 반복해주면 효율성이 훨씬 올라간다.

반응형