에라토스테네스의 체를 이용한 소수 구하기 알고리즘 java

알고리즘알못 비전공자 수학싫어함인 내가 어쩌다 개발자를 하고있는지 매번 신기하다.

언제까지 할 수 있을런지....

무튼 M이상 N이하의 소수를 모두 출력하는 알고리즘 문제를 푸는데(백준 1929번)

M~N사이 숫자 하나하나 약수의 개수를 검사하는 방법으로 했더니

자꾸 시간초과가 떠서 스터디원에게 조언을 구하니 '에라토스테네스의 체'를 이용해야한다고 들어서 알아보았다.

하아 저건 또 뭐야 검색 ㄱㄱ 뚫어져라 보다가 백퍼 이틀 뒤 까먹을거같아서 나를 위해 정리

1. 에라토스테네스는 뭐고 체는 뭐지?

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 

그렇다고 합니다. 땡큐 나무위키

 

2. 그래서 그게 뭔데 어떻게 하는건데

겁나 단순하다.

예를 들어 1에서 20까지의 수 중에 소수만을 골라내려 한다고 가정.

 

1부터 20까지 쭉 써보자

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

 

여기서 1은 소수가 아니다. 소수는 1과 자기 자신만을 약수로 갖는 수. 무튼 소수 아님. 그냥 빼자.

 

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20

 

이제 잘 봐야되는데 1을 지우고나서 2가 가장 작은 수이다.

2의 배수가 되는 수를 다 거른다. (넘무 당연한 얘기지만 자기 자신은 지우면 안댐;)

 

	2	3		5		7		9
11		13		15		17		19

 

그리고 그 다음 숫자인 3!

3의 배수가 되는 수를 다 거른다. 

 

	2	3		5		7
11		13				17		19

 

그리고 그 다음 숫자인 5!

4는 걸려져서 없음.

이제 5의 배수가 되는 수를 다 거른다. 근데 없네? 자 그다음은 7..

여기서 눈치가 좀 빠르거나 소수를 잘 알고 있는 사람은 알겠지만 20까지의 소수는 여기가 끝이다.

더 이상 거를 수가 있는지 없는지 체크하지 않아도 된다.

 

그 기준 숫자를 정하는 방법이 있다.

소수가 아닐 조건은 합성수인데 합성수는 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수이다.

그냥 간단히 말하면 1보다 큰 모든 정수는 소수 / 합성수로 나뉜다.

우리는 소수를 구하고 싶은거니까 지금 이 알고리즘은 합성수를 제거하는 알고리즘이라고도 할 수 있다.

 

즉!

만약 어떤 합성수가 m이고 m=ab라면 a와 b 중 적어도 하나는 루트n​이하이다.

n(여기서는 20, 1~20까지 수 중에 소수를 구하기로 했으니까)보다 작은 합성수 m은

루트n​보다 작은 수의 배수만 체크해도 전부 지워진다는 의미.

다시 표현하면 어떤 수 m을 제곱했을 때 n보다 크다면 더 체크할 필요가 없단 의미이다.

 

위의 예로 적용시켜보면 루트20은 4.xx가 될테니 4는 진즉 없어졌고 사실상 3의 배수까지 거르고 끝내도 무방하다. 5는 4.xx..보다 크니까.

이해안되면 그냥 그렇구나 하고 넘어가면 댄다. 대신 알긴 알아야 함.

 

3. 왜 굳이 저거를 쓰는건데? 그냥 하나하나 소수인지 아닌지 검사해서 분별해내도 되지 않음?

위에도 언급했지만 하나하나 검사하면 계속 시간초과가 떴다.

속도 상관 없으면 그냥 아무 방법이나 써도 되지만 빠른 연산을 해야한다면 이 방법을 써야한다 ㅠ

 

2중 for문 돌려서 나누어 떨어지는 수가 하나라도 있을 경우 boolean값 false넣어서 true인 경우만 출력해서 싹 검사했더니 계속 시간초과 떠서 통과를 못했뜸...

무튼 에라토스테네스의 체를 이용하도록 하자.

 

위의 이해를 바탕으로 java로 옮기면.

 

public static void calculate(){
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int start = 1; //구하고자 하는 범위의 가장 작은 수
		int end = 20; //구하고자 하는 범위의 가장 큰 수

		boolean[] array = new boolean[end + 1]; // 소수면 true, 그렇지 않으면 false가 들어있는 배열

		for (int i = 2; i <= end; i++) { //배열을 다 true로 채운다.
			array[i] = true;
		}

		for (int i = 2; i * i <= end; i++) {
			for (int j = i + i; j <= end; j += i) { //배수를 찾아가며 false로 바꿈.
				array[j] = false;
			}
		}

		for (int i = start; i <= end; i++) {
			if (array[i] == true) { //false로 바뀌지 않은 수들은 소수이다.
				bw.write(String.valueOf(i));
				bw.newLine();
				bw.flush();
			}
		}

		bw.close();// 스트림을 닫음
	}

 

 

잘 보면 이해가 될것임니다.

미용실에 가야하므로 급 올리고 떠나야겠다.

두번째 포문이 난 되게 헷갈렸는데 보다보면 이해된다.

천천히 처언천히 이해해나가자

난 진짜 알고리즘 머리가 없는건지 뭔지 알못에 드럽게 못하지만 그래도 희망을 갖고 풀어나갈꺼다ㅠㅠ