说明

如果要找出 1 到 n 范围内的所有质数，对每个数都单独判断一次效率不高。埃拉托色尼筛法（简称埃氏筛）是一种更高效的方法。

埃氏筛的基本思想：

1. 创建一个布尔数组，初始全部标记为"是质数"
2. 将 0 和 1 标记为"不是质数"
3. 从 2 开始，如果当前数还标记为"是质数"，则它就是质数，然后将它的所有倍数标记为"不是质数"
4. 重复步骤 3，直到处理完 \sqrt{n} 以内的数

现在给定一个正整数 n，请你使用埃氏筛法求出 1 到 n 之间的所有质数，并输出质数的个数以及所有质数的和。

输入格式

一行，一个整数 n（$2 \le n \le 10^6$）。

输出格式

第一行，一个整数，表示 1 到 n 之间质数的个数。

第二行，一个整数，表示所有质数的和。

10

4
17

提示

核心代码框架：

n = int(input())
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False

for i in range(2, int(n**0.5) + 1):
    if is_prime[i]:
        for j in range(i * i, n + 1, i):
            is_prime[j] = False

# 统计和求和
count = sum(is_prime)
total = sum(i for i in range(n+1) if is_prime[i])

注意：内层循环从 i*i 开始，因为 $i \times 2, i \times 3, \dots, i \times (i-1)$ 已经被更小的质数标记过了。