호지

소수를 구하는 에스토스테네스의 체를 기반으로 한 알고리즘 풀이이다. list에 min-max의 최대인 1000001을 할당한다. 2부터 제곱이 max보다 작거나 같을 때까지 모든 수의 제곱의 배수를 탐색한다. 제곱의 배수의 시작점은 값이 min보다 크거나 같을때이다. 따라서 x=min/i*i로 배수의 시작점을 구할 수 있고, i의제곱이 min일 확인하기 위해 min%(i*i)=0이면 x를 1감소한다. list에서 제곱의 배수가 되는 위치는 true로 저장하여 list에서 false인 경우에 제곱 ㄴㄴ수이므로 해당 값을 카운트하여 출력한다. #include #include using ll = long long; using namespace std; bool list[1000001]; int main(){ ..