【ybt高效进阶6-2-4】反素数（贪心）（质因数）

题目描述

给定一个正整数 $n$，求小于等于 $n$ 的正整数中，质因数个数最多的数。

输入格式

一个正整数 $n$。

输出格式

一个正整数，表示小于等于 $n$ 的正整数中，质因数个数最多的数。

数据范围

$1 \leq n \leq 10^6$

输入样例

30

输出样例

30

算法1

(暴力枚举) $O(n\sqrt n)$

枚举每个数，统计其质因数个数，取最大值。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(贪心) $O(n\log n)$

时间复杂度

参考文献

C++ 代码

算法3

(暴力枚举) $O(n\sqrt n)$

时间复杂度

参考文献

C++ 代码