백준 1929번 - 에라토스테네스의 체(C++)

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제 자체는 개념만 알면 정말 쉽다. 그런데 이상하게 잔실수가 많이 나오는 문제이기도 하다. 처음에 이 문제를 풀었을 떄 당연히 맞은 줄 알았는데 아직도 왜 틀렸는지 모르겠다(..)

 

 

문제 풀이 과정

1. 0번째와 1번째를 제외한 모든 list 값을 전부 true로 초기화

   ( 1은 소수가 아니다)

2. 처음부터 끝까지 모든 수를 순차 탐색하면서 에라토스테네스의 체 적용

   ㄴ 이 때, sqrt(N) 또는 i*i<N을 사용하면 시간을 절약할 수 있음

3. 결과값 출력

 

※ 주의사항

- i*i 를 이용할 시 오버플로우가 발생할 수 있으므로 int가 아닌 long long int를 사용할 것

- endl 구문은 버퍼를 flush하기 떄문에 느림. 따라서 '\n'을 사용

- 이상, 이하 구분 잘 하기

 

- 정답 코드 -

 

참고로 sqrt(N)이나 i*i<N이 가능한 이유는, 만약 어떤 자연수 x에 sqrt(x)보다 큰 소인수가 존재한다면, x를 그 소인수로 나눈 값은 sqrt(x)보다 작아야 하기 떄문에 이미 그 전에 그 수로 나누어보았을 것이기 때문이다.

 

 

정말 별거 아닌거 같은데 아까운 시간만 다 잡아먹었다.. 마지막으로 에러가 떴던 코드를 첨부하고 끝내겠습니다. 혹시 뭐가 문제인지 보이신다면 댓글 부탁드립니다. ㅠㅠ

 

- 에러 코드 -