소수를 판별하는 알고리즘 중에는 굉장히 유명한 에라토스테네스의 체라는 알고리즘이 존재한다. 소수 판별 문제는 대부분 이 알고리즘으로 풀기 때문에 잘 익혀두면 큰 도움이 된다. 오늘 풀어볼 문제인 boj 1929 번 문제다. 💡에라토스테네스의 체란? 배열을 원하는 범위만큼 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이때, 자기 자신은 지우지 않고, 이미 지워진 수인 경우 건너뛴다. 지워지지 않은 테이블이 소수로 판별된 테이블이다. 위 예시는 2의 배수를 모두 지우고, 3의 배수를 지우는 과정이다. 이런 식으로 $N/2$까지 진행하고 남은 테이블을 확인한다. ❓에라토스테네스의 체의 시간복잡도 naive한 방법으로는, 일반적으로 어떤 정수의 소수를 판별할때는 2부터 판..