자연수 N이 주어질 때, N 이하의 소수가 몇 개인지와 그 소수들을 모두 더한 값을 구해 보세요. 소수는 1과 자기 자신으로만 나누어떨어지는 2 이상의 자연수예요.
N이 아주 클 수 있어서, 수마다 하나씩 나눠 보며 소수인지 확인하면 시간이 너무 오래 걸려요.
입력
첫째 줄에 자연수 N이 주어져요. (1 ≤ N ≤ 2,000,000)
출력
N 이하의 소수의 개수와 소수의 합을 공백 하나로 구분해 출력해요. 소수가 없으면 0 0을 출력해요.
합은 int 범위를 넘을 수 있어요. C, C++, Java로 풀 때는 64비트 정수(long long, long)를 쓰세요.
힌트
에라토스테네스의 체는 2부터 N까지의 수를 모두 적어 두고, 지워지지 않은 가장 작은 수를 소수로 고른 다음 그 수의 배수를 모두 지우는 일을 반복하는 방법이에요. 2를 고르면 4, 6, 8, …을 지우고, 3을 고르면 6, 9, 12, …를 지워요. 끝까지 지워지지 않고 남은 수가 소수예요.
어떤 수 p의 배수를 지울 때 p × p보다 작은 배수는 이미 더 작은 소수가 지웠어요. 그래서 p × p부터 지우면 되고, p × p가 N보다 크면 더 지울 것이 없어요.