https://www.acmicpc.net/board/...

단순히 더해나가면 시간복잡도가 많이 높습니다.

n이라는 수는 sqrt(n)까지만 나누어보면 소수인지 판별할 수 있습니다. 또, %연산은 속도가 오래걸리는 연산이라 bool type의 array를 쓰시는 것을 추천합니다.

에라토스테네스의 체는 i를 증가시켜가며 i 의 배수들을 제거해나간 후 남은 것들이 소수가 되는 알고리즘임을 다시 한 번 잘 생각해보시기 바랍니다.

(스포주의)

스스로 사고하시는 부분에 방해가 될까봐 미리 스포주의를 달고 첨부합니다!! 아래는 관련 위키피디아 슈도코드입니다. 정 안된다 하실때 참고하시면.. 통과는 하실텐데 알고리즘을 이해하는 것이 중요합니다. 저도 찾아보다가 발견하게 됐는데 좀 허무하더라구요. 이해는 되는데 나는 이런 사고를 왜 하지 못했을까.. 라는 생각이 강하게 들었어요.

https://en.wikipedia.org/wiki/...