#O1007. 素数个数

素数个数

素数个数

题目描述

给定整数 nn,请求出 1∼n1 \sim n 中素数的个数,以及其中最大的素数。

输入格式

一行一个整数 nn。

输出格式

一行两个整数,依次为素数个数与最大的素数,之间用一个空格隔开。

若 1∼n1 \sim n 中不存在素数(即 n<2n < 2),输出 0 0。

样例 #1

样例输入 #1

10

样例输出 #1

4 7

样例说明

1∼101 \sim 10 中的素数为 2,3,5,72, 3, 5, 7,共 44 个,最大的为 77。

数据规模与约定

数据范围 nn
全部测试点 1≤n≤1071 \le n \le 10^7
  • 逐个数字试除判断素数的时间复杂度为 O(nn)O(n\sqrt{n}),在 n=107n = 10^7 时无法在时限内完成。
  • 1∼1071 \sim 10^7 内共有 664579664579 个素数。