산 넘어 산 개발일지

풀이 키워드 에라토스테네스의 체 이번 문제는 척 보면 알 수 있듯이 소수를 사용하는 문제이다. 소수하면 바로 에라토스테네스의 체가 떠오른다. 에라토스테네스의 체는 범위 내의 숫자들이 소수인지 아닌지를 미리 판별해내는 계산이다. 간단히 설명하자면, 미리 1~N까지의 배열(boolean)을 만들어 놓는다. 그리고 처음에는 2부터 시작을 한다. 2를 제외한 2의 배수들은 소수가 아니므로 소수가 아니라고 마킹(false)한다. 그리고 다음 숫자 3으로 넘어간다. 3은 소수가 아니라 마킹이 안되었으므로 앞 과정과 동일하게 3을 제외한 나머지 배수들을 소수가 아니라고 마킹한다. 다음 4는 2에 의해 마킹되었으므로 넘어간다. 다음 5는 마킹이 안되었으므로 앞 3과 동일한 작업을 수행한다. 이런 과정을 N까지 반복하면..