40번도 넘게 시도해본거같습니다

서브태스크 2인 n <= 10,000,000까지는 N == 1 일때를 제외하곤 다 O인걸 구현을 통해 알아냈지만

서브태스크 3으로 오니

10억을 배열로 나열하면 메모리 초과를 맞고,

테스트케이스도 1,000,000 까지라 주어지는 n마다 찾기도 시간초과 걸릴거같고

굳이 1 ~ 10억까지 중에 소수를 다 안찾아도 되는 문제인가요?

아니면 소수 찾는 방법이 다 있는건가요?

차마 시도해본 여러 소스들이 도움이 안될거같아서 소스코드는 올리지않겠습니다..

어떠한 문제 힌트라도 주시면 감사하겠습니다