에라토스테네스의 체는 굉장히 빠르게 동작하는 소수 찾기 알고리즘입니다. 알고리즘에 대해 간단히 요약을 하자면 소수를 구할 때 소수가 아닌 수들의 배수는 소수가 아니기 때문에 그들을 모두 지워나가면서 남은 수(소수) 들을 찾는 방법인데, 수의 범위가 점점 커지면, 메모리 공간이 부족하기 때문에 이를 극복하기 위해 비트 마스크를 이용합니다. (기존 알고리즘 또한 웬만한 범위 내에서는 잘 작동합니다) 따라서 비트마스크를 사용하는 구간도 메모리 영역에 국한되는데, 기존 에라토스테네스의 체 구현 과정에서 bool 배열로 범위 내 소수가 아닌 수들의 인덱스를 모두 false 처리하고, 소수들을 true 처리해서 소수들을 골라냈다면 이번엔 비트마스크를 이용해서, check 역할을 하는 배열을 unsigned char..
비트마스크
문제 링크 : https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 문제 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. toggle x: S에 x가 있으면 x를 제거하고, 없으면..
