15711번 환상의 짝꿍(골드바흐의 추측, 에라토스테네스의 체)

#문제링크 : https://www.acmicpc.net/problem/15711

T : 테스트 케이스
x, y : 입력받을 두 숫자
sum : 입력받은 두 숫자의 합
e : x,y가 소수이고 sum이 홀수면 무조건 2가 포함되므로 2를 빼주고 남은 수
sel : 에라토스테네스의 체로 거른 1~200만까지의 소수들
check : e가 소수인지 아닌지 판별하기 위한 변수

전략 : x, y가 각각 2조까지 최대값이므로 sum의 최대는 4조. sum이 2를 제외한 짝수일때, 골드바흐의 추측에 의해 두 소수로 표현 가능하므로 짝수면 YES. 홀수일 때는 무조건 2를 하나 포함하므로 2를 뺀 나머지 수가 소수가 되느냐 안되느냐를 판별해야한다. 나머지 수가 최대 4조까지이기에 제곱근인 200만까지 나눠주면서 소수인지 검사를 해야하지만, 테스트 케이스가 500이므로 200만x500 = 10억으로 연산횟수 1억을 초과한다. 잘 생각해보면 200만까지 전부 나눠줄 필요가 없고, 200만까지의 소수들로만 나눠서 소수인지 판별하면 된다. 이유는 모든 수는 "소수 x 어떤 수" 로 이루어져 있다. 다시말하면, 모든 수의 약수에는 소수가 포함되어 있으므로 200만까지의 소수들만 따로 모아서 나눠주면 연산횟수를 많이 줄일 수 있다.

※주의사항

1. 에라토스테네스의 체로 sel 배열을 거르는 for문 도중에 v,push_back(i)처럼 해버리면 i는 sqrt(MAX)까지만 돌기 때문에 루트(200만)까지만 담게 된다. 따라서 sel배열을 다 거르고 난 다음 추가적인 for문을 통해 벡터에 담도록 한다.

2. 최대값이 2조, 4조이기 때문에 자료형을 long long으로 해주어야 하고 for문 조건식에서 v[j]는 int형이므로 형변환을 해주어야 정상적인 연산이 가능해진다.

3. sqrt 함수에 들어갈 수 있는 자료형 타입을 잘 확인하자.

4. 마지막 for문을 for(auto &ev : v) 형태의 반복문으로 바꾸어주면 더 간단하게 작성가능하다.

5. 예외처리 잘 확인하자.

Code