여러 문제가 있는데, 제일 눈에 띄는건 여러 개의 테스트 케이스에서 이전에 소수 여부를 계산해 놓은 결과를 재사용하지 않고 있다는 것입니다. 123456을 여러 개 주는 테스트 케이스에서 매 번 123456개 숫자의 소수 판정을 계산해야 하죠.
이 이외에도 문제점은 꽤 있습니다. 간략하게 적자면:
- 각 수에 O(sqrt N)의 소수 판별 검사를 하고 있음 => 에라토스테네스의 체를 이용하면 됩니다.
- 소수 판별 검사가 비효율적임.
- 매번 sqrt 함수를 호출하고 있음.
- k가 2부터 1씩 증가함. k=2를 제외하고 짝수는 검사할 필요 없습니다. 짝수 여부를 체크한 다음에는, k를 3부터 2씩 증가시키면 됩니다.
- 소수가 아님을 판단했을 때, 그 자리에서 break하지 않고 굳이 sqrt(2*N)까지 전수 검사를 하고 있음.
- input을 굳이 vector에 저장해 넣고 있고, 처음에 reserve를 하지도 ᅟ않고 굳이 매번 shrink_to_fit을 불러주고 있음. 매번 메모리 할당을 해야 하니, 실행 시간이 줄어들게 됩니다.

cksgml3808 1년 전
n+1 부터 2*n 까지의 숫자를 vector에 저장하여
vector의 첫번째 요소부터 마지막요소까지 소수인지 확인하고 소수가 아니면 ++count해주어
전체 vector의 길이에서 소수가 아닌 숫자의 개수를 빼주면 될것이다라고 생각하여 코드를 작성하였습니다.
10% 이후에 시간초과가 뜨는데 어떻게 개선해야될지 여쭤봅니다.