에라토스테네스의 체 (1 에서 N까지의 모든 소수 구하기), 골드바흐의 추측

에라토스테네스의 체는 1에서 N까지 모든 소수를 구하기위해 쓰는 방법이다.

가장 작은 소수인 2부터 시작하여 N까지 소수의 배수를 모두 지우는 방식으로 진행된다.

그림을 통해서 살펴보자.

맨 처음에 소수인 2를 발견한 후 2의 배수를 모두 지운다.

그 다음 소수인 3을 발견한 후 3의 배수를 지운다 이 때 3의 배수중에 3보다 작은 수인 

3*1 , 3*2에 대해서는 이미 해결이 됐기 떄문에 3*3부터 지워주면 된다.

이런 방식으로 3보다 큰 수에 대해서도 n*n부터 지워주면 된다.

이렇게 3의 배수도 지워주고 나면 다음 소수인 5가 발견되고 

5*5부터 5의 배수를 지운 후 계속 같은 방법을 반복하면 N까지 모든 소수를 발견할 수 있다.

에라토스테네스의 체를 적용하는 문제를 통해 

코드로 구현하는 것에 대해 살펴보겠다.

에라토스테네스의 체를 통해 나온 결과를 특정 배열에 저장해놓고

M부터 N까지의 수만 뽑아내면 쉽게 결과를 출력할 수 있을것이다.

#include <iostream>
#include <algorithm>

using namespace std;

bool result[1000001];
void func(long long N);
int main()
{
	long long M, N;

	cin >> M >> N;
	func(N);

	result[1] = 1; // 1은 소수가 아니므로
	for (long long i = M; i <= N; i++) {
		if (result[i] == 0) {
			printf("%lld\n", i);
		}
	}
}
void func(long long N) {
	for (long long i = 2; i <= N; i++) {
		if (result[i] == 0) { //만약 result[i]가 소수라면
			for (long long j = i*i; j <= N; j += i) {
				result[j] = 1; //소수의 배수는 1(true)로 설정
			}
		}
	}
}

골드바흐의 추측

골드바흐의 추측이란 2보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다는 것이다.

이것은 완전히 증명되지는 않았고 10^18 이하에서 참인 것만 증명되었다.

에라토스테네스의 체를 이용한다면 이 문제 또한 코드로 구현하기 어렵지 않다.

문제를 풀기 위해서

주어진 N까지의 범위에 대해 에라토스테네스의 체를 통해 소수를 걸러내고

반복문을 돌면서 주어진 N에서 에라토스테네스의 체를 통해 걸러진 result[i]을 뺐을 때 그 결과도

소수인지만 확인하면 되는것이다. 역시 문제를 통해 확인해 보겠다.

#include <iostream>

using namespace std;

bool result[1000000];
void func(long long N);
int main()
{
	long long testcase;
	result[1] = 1;

	func(1000000);
	while (1) {
		scanf("%lld", &testcase);
		if (testcase == 0) break;
		for (long long i = 3; i <= testcase/2; i += 2) {
			if (result[i] == 0 && result[(testcase - i)] == 0) {
				printf("%lld = %lld + %lld\n", testcase, i, testcase-i);
				break;
			}
			else if (i == testcase/2)
				printf("Goldbach's conjecture is wrong.\n");
		}
	}
}
void func(long long N) {
	for (long long i = 2; i <= N; i++) {
		if (result[i] == 0) { //만약 result[i]가 소수라면
			for (long long j = i*i; j <= N; j += i) {
				result[j] = 1; //소수의 배수는 1(true)로 설정
			}
		}
	}
}

이 문제가 유난히 시간초과가 나올 가능성이 높은데

두 수의 짝을 찾는 과정에서 굳이 반복문을 끝까지 돌리지 않고 testcase/2 까지만 검사하면서

복잡도를 줄이는 요령이 필요하다

또한 만약 입력이나 출력을 cin이나 cout을 통해서 했다면

printf나 scanf를 쓰는것이 좋다.