에라토스테네스의 체 알고리즘을 한 번만 사용하여 해결할 수 있습니다.

그렇다는 말씀은 소스코드 31줄 이하의 문장은 불필요하다는 말씀이신거죠??

말씀하신 것들이 크게 와닿지는 않은데.. 어떠한 방법으로 해결할 수 있을지 말씀해주실수 있으실까요??

에라토스테네스의 체 부분과 골드바흐 파티션을 구하는 부분을 분리하시면

각 테스트케이스마다 에라토스테네스의 체를 사용하시지 않으셔도 됩니다.

올려주신 코드로는 테스트케이스마다 각각 에라토스테네스의 체를 사용하게 됩니다

에라토스테네스의 체를 미리 사용한 후 테스트케이스마다 골드바흐 파티션 구하는 과정을 처리해보세요

감사합니다. 이해했습니다. 최댓값으로 주어질 수 있는 n 이하의 소수를  에라토스테네스의 체를 미리 사용하여 구하고,

골드바흐 파티션을 구하는 과정을 각 테스트케이스 별로 구하라는 말씀이군요 이제 이해가 가네요.. 두 분 모두 감사드립니다 :) 

마지막으로 질문드리고자 합니다,...ㅠㅠ

해당 문제에 반례가 있을까요..? 또 같은 풀이 방식으로도 시간 초과가 나는데.. 해당 풀이 방법 자체가 시간 초과가 나는 풀이 방식은 아닌가 의문이 드는데

어떻게 생각하시는지요..?ㅠㅠ

혹시 21행부터 27행까지의 코드에 대한 설명 가능할까요?

21행부터 27행

arr[i] 은 2 ~ SIZE까지 중 1이 들어있는 배열의 원소들을 소수로 판별하였습니다.

Arr[j] 는 arr[i] == 1일 때 즉 소수일 때 이에 해당하는 소수 값 그 자체인 i를 담는 배열을 의미합니다. 

따라서 Arr[j]는 i = 2 부터 i = SIZE 범위안에 소수를 모두 담은 배열이 되고

cnt 는 Arr[j] 에 담긴 소수의 갯수를 의미합니다!

위와 같이 작성한 이유는 printSum 함수에서 42행, 43행의 반복문 조건을 만족시키기 위해 작성했습니다.

i와 j의 값이 동시에 1씩 늘어나기 때문에 arr[i]==0이더라도 j도 함께 증가하게 되어

Arr[] = { 2, 3, ?, ?, 5, ... }가 되어 제출 번호 42611313가 오답이 된 것 같습니다.

cnt의 값은 소수의 개수를 제대로 세고 있지만, printSum에서는 Arr[]의 전체를 탐색하는 것이 아니라

cnt개만을 탐색하기 때문에 모든 소수에 대해 판별하지 못합니다.

만일 Arr[] = { 2, 3, 5, 7, ... }가 되려면 i가 소수일 때만 j를 증가시켜주면 됩니다.

계속 피드백 해주셔서 정말 감사합니다 혹시

직접 작성하셨었던 코드도 업로드 해주실수 있으실까요..?

꼭 참고하여 정리하고 싶습니다!

1. 에라토스테네스의 체

i가 소수가 아닐 경우, i의 배수들은 이미 소수가 아닌 것으로 판정되었기 때문에, 불필요한 연산을 줄일 수 있습니다.

ex) 4는 소수 2의 배수이므로, 4, 8, 12, 16, ... 은 소수가 아니다.

2. 골드바흐 파티션

10,000 이하의 소수는 1200개가 넘으므로, 하나의 테스트케이스 당 1200^2가 넘는 경우를 모두 탐색하여야 합니다.

그러나 합이 n이 되는 두 자연수 쌍의 개수는 n-1개이므로 각 쌍에 대해 두 자연수가 소수인지 확인하는 연산 n-1회만으로

골드바흐 파티션을 구할 수 있을 것입니다.

ex) n=5 --> (1, 4), (2, 3), (3, 2), (4, 1)