마지막에 남길 수 있는 원소의 원래 번호는 정확히 부터 까지이다. 따라서 이 범위의 중 최댓값을 출력하면 된다.
수열을 읽으며 해당 범위의 최댓값을 구하면 시간 복잡도는 , 추가 공간 복잡도는 이다.
증명
지금까지 고른 들의 곱을 라 하자. 처음에는 이고, 남아 있는 원소의 원래 번호는 항상
이다. 여기서 의 배수 번째만 남기면 원래 번호가 의 배수인 원소들만 남으므로 이 성질이 유지된다.
원소가 하나만 남으려면 , 즉
이어야 한다. 반대로 이 범위의 번호 는 첫 연산에서 를 골라 바로 혼자 남길 수 있다. 이면 연산 없이 유일한 원소가 남는다.
따라서 위 범위의 원소들만, 그리고 모두 마지막에 남길 수 있다.
