http://acmicpc.net/problem/1929

1929 소수 구하기

문제 분석

(1 ≤ M ≤ N ≤ 1,000,000)

M이상, N이하의 숫자의 모든 소수를 구하기

이거 보니까.

어제 풀었던 다음 소수 문제에서 해당 숫자의 제곱근까지만 소수를 판별하고, 로직 그대로 사용하면 풀릴것 같은데??

오 근데,
범위가 주어진 케이스라서... 2는 소수야 -> 근데 2의 배수 4, 8, 10, 12 --- 는 소수가 아니니까 이것들을 제외하는 로직도 있어야 하겠지??
에라토스테네스의 체 라는건데
참고 블로그를 보면 메모리 할당이 많아져서 보통 N이 1,000,000 이하인 경우만 이 방식으로 해결한다고 하는데 혼자 검증해보면 좋을듯.

결론

1. 해당 숫자의 제곱근까지만 소수 판별
2. 소수로 판정된 수의 배수들은 미리 필터링

2가지가 핵심인데...

오늘 아침밥 안 먹으면 아마 영양실조로 숨쉰채 발견이라 밥좀 먹을게요
:>