BOJ 1929
BOJ 1929 소수 구하기 [Java]
BOJ 1929 소수 구하기 1. 문제 링크 https://www.acmicpc.net/problem/1929 2. 문제 해설 주어지는 두 수의 범위가 1부터 1,000,000 사이이다. 1부터 1,000,000까지 모두 나눠보는 방식은 시간 제한에 걸리기도 하고 굉장히 비효율적이다. 주어진 범위 내에서 소수 판별을 하는 가장 좋은 방법으로 '에라토스테네스의 체' 라는 방식이 있다. 예를 들어 1부터 100까지의 수 중에서 소수를 판별한다고 할 때, 에라토스테네스의 체가 어떻게 동작하는지 살펴보자. 일단 소수도 합성수도 아닌 1을 제외한다. 2를 제외한 범위 내의 2의 배수를 전부 제외한다. 3을 제외한 범위 내의 3의 배수를 전부 제외한다. 4의 배수는 이미 2의 배수를 제외하는 과정에서..