문제 출처 : https://www.acmicpc.net/problem/1929

문제 해결 방법

• 에라토스테네스의 체
  1. 2부터 N까지 모든 수를 써놓는다.
  2. 아직 지워지지 않은 수중에서 가장 작은 수를 찾는다.
  3. 그 수는 소수이다.
  4. 이제 그 수의 배수를 모두 지운다.

코드

• 1차 코드 작성

값은 제대로 나오나, 런타임 에러가 나온다.

그 이유는 인트범위를 초과하기 때문이다.

해결책?

• 이중 반복문의 내부 반복문은 int j = i * i 을 할 경우 입력 최댓값이 1,000,000 이라 i 가 최대 1,000,000 가 된다면 j 의 경우 1,000,000,000,000 으로 int 형 범위를 넘어버릴 수 있어 int j = i + i 로 변경하여 풀어야 한다.

• 2차 코드 작성

주의사항

1. 실수는 근사값을 나타내기 때문에 정수로 표현하는게 안전하고 더 좋은 방식 (최대한 정수를 사용하자) i <= 루트 N 대신 i*i <= N이 더 좋은 표현임