Little Jay

2학년때 정수론 배울때 잠깐 언급됬던 골드바흐 추측 에라토스테네스 체를 활용한 문제였다. 주어진 n의 max값이 1000000이기 때문에 접근할때 for문을 두개 돌려버리면 당연히 시간초과가 날 것 같았다. (실제로 시간초과가 났다) 그래서 algorithm stl에 들어있는 binary_search를 활용했다. 처음에 에라토스테네스의 체를 초기화해줄때 소수의 개수를 셌는데, 78498개나 나왔다. 어차피 배열에 저장할때는 오름차순으로 정렬이 되니, 정렬되어 있는 배열에서 이진탐색으로 찾으면 빠를거라고 예상했다. 찾기만 하면 나머지 수는 입력된 수에서 빼면 된다. 다른분의 숏코딩을 보니 문제에서 골드바흐 추측을 벗어나는 문제는 없었다. 이럴거면 나도 중간에 조건문 쓰지 말껄이라는 후회는 들긴 한다. 그리..

에라토스테네스 체를 이용해서 구하는 문제 처음에는 쉽게 소수 구하는 알고리즘을 적용했는데 (앞 수랑 비교하는거) 이러다보니 시간 초과가 발생했다. 아무래도 효율적인 알고리즘을 찾다가, 결국 구글에 검색을 해보니 에라토스테네스의 체라는 알고리즘이 있었다. 다른분들의 코드를 참고해서 작성했다. #include #include using namespace std; bool primeArr[1000001]; int main(void) { int m, n; cin >> m >> n; for (int i = m; i