CodeUp[Q_2607] : 쌍둥이 소수

1. 문제

https://codeup.kr/problem.php?id=2607

쌍둥이 소수

[출처 : 코드업(https://codeup.kr/)]

이번 문제는 주어진 구간(a ~ b)안의 숫자 중에 쌍둥이 소수를 구하는 문제입니다.

쌍둥이 소수 : 두수의 차가 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. 풀이방법

STEP 1. 구하려고하는 구간을 1부터 나열한다.
(2를 제외한 짝수는 모두 소수가 아니므로 홀수만 나열)

STEP 2. [n^2 > b] 를 만족하는 가장 작은 n을 구한다.

STEP 3. 2부터 n보다 작은 값까지 "에라토스테네스의 체" 알고리즘을 반복한다.

 

 

3. 해답

#include <stdio.h>
#include <math.h>

int arr[2000000] = { 0, };

int main() {
	int a, b, tmp = 3;
	int p; // 마지막 위치

	scanf("%d %d", &a, &b);

	p = 1;
	// 2를 제외한 짝수는 모두 소수가 아니므로 홀수만 사용
	while (tmp <= b) {
		arr[p++] = tmp;
		tmp += 2;
	}
	arr[0] = 2;
	// n^2 > b
	// b보다 큰 정수 중 루트를 씌워도 정수가 되는 가장 작은 수
	tmp = (int)sqrt(b) + 1;

	// tmp의 위치
	tmp /= 2;

	for (int i = 1; i < tmp; i++) {
		if (arr[i] == 0) continue;

		for (int j = i + arr[i]; j < p; j+= arr[i]) {
			arr[j] = 0;
		}
	}

	for (int i = 1; i < p - 1; i++) {
		if (arr[i] >= a) {
			if (arr[i] != 0 && arr[i + 1] != 0) printf("%d %d\n", arr[i], arr[i + 1]);
		}
	}

	return 0;
}