에라토스테네스의 체 (+ 골드바흐의 추측)

자연수의 집합에서 소수를 찾아내는 방법으로 모든 수를 나눠보며 나머지를 확인하는 방법보다 빠르기 때문에 유용하게 사용된다.

1. 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2의 배수, 3의 배수, 5의 배수… 로 계속 지워나간다.
   위의 움짤에선 숫자가 120까지 있으니 7의 배수 까지만 지워나가면 된다.(7의 다음 소수인 11의 제곱은 121이기 때문)

#include <iostream>
#include <vector>
using namespace std;
bool p[1000001] = {1, 1};
vector<int> prime;
int main() {
	for(int i = 2; i * i <= 1000001; i++) {
		if(p[i]) continue;
		for(int j = i * i; j < 1000001; j += i)
			p[j] = 1;
	}
	for(int i = 0; i <= 1000001; i++)
		if(!p[i]) prime.push_back(i);
}

골드바흐의 추측은 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두개의 소수의 합으로 나타낼 수 있다는 추측이다.
1742년 부터 아직까지도 증명은 안 됐지만 작은 범위의 숫자 내에선 부분적으로 증명해볼 수 있다.

int ll, rr, l, r, sum, tmp;
cin >> tmp;
while(l <= r) {
    sum = prime[l] + prime[r];
    if(sum == tmp) {
      ll = prime[l], rr = prime[r];
      l++;
      r--;
    } else if(sum < tmp) {
      l++;
    } else {
      r--;
    }
  }

두개의 위치 인덱스를 조건이 맞을 때 까지 좁혀오며 답을 구하는 투 포인터 메소드를 사용하면 쉽다.