반응형 소수판별1 백준 6588번 골드바흐의 추측 - C++ 풀이 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 1. n 이하의 모든 소수 i에 대해 (n-i)가 소수인지 판별한다. 에라토스테네스의 체를 이용하여 백만 이하의 모든 소수를 구한다. n이하의 모든 소수 i에 대해 n-i가 소수인지 판별하면 된다. 이때 i를 오름차순으로 순회하고, 답이 나올 경우 순회를 종료시키면 b-a가 가장 큰 답을 구할 수 있다. 백만 이하의 소수 개수는 약 8만 개이므로, 이 풀이의 시간 복잡도는 O(80,000*T)이다. 이때 T(테스트 케이스 수)가 10^5이므로 시간 초과가 날 것 같았는데 시간 초과가 나지 않았다. 이에 관련된 질문과 답을 아래 게시글에서 발견하였다. 글 읽기 - 이 문제 제한시간이 1초인데 왜 되나요? 댓글을 작성하려면 로그인해야 합니.. 2022. 9. 20. 이전 1 다음 반응형
