에라토스테네스의 채

문제https://www.acmicpc.net/problem/9020풀이수학, 에라토스테네스의 채, 소수 판정 소수 판정에는 에라토스테네스의 채를 사용하여, 알고리즘 시작 전에 10000까지 소수를 판정해 둔다. 두 소수의 차이가 가장 적은 것을 출력해야 하므로, 시작 값(start)을 n / 2로 설정하여, 중앙에 가장 가깝도록 한다. start를 1씩 감소 시키면서, n - start가 소수라면 해당 값이 차이가 가장 적은 소수이므로 이를 출력하고 알고리즘을 중지한다. 처음에는 두 포인터로 문제를 해결하였지만, 위의 방법이 더 효율적이였다. 코드방법 1#include #include using namespace std;const int MAX = 4'000'001;bool prime[MAX];// 에..
KANTAM
'에라토스테네스의 채' 태그의 글 목록