质因数的个数

题目描述

给定两个正整数 N 和 M(2≤N≤M≤1e6)，统计 N 到 M 之间（含 N 和 M）每个数所包含的质因数的个数，输出其中最大的个数。

例如：当 N=6，M=10，6 到 10 之间:

• 6 的质因数是 2、3，共有 2 个；
• 7 的质因数是 7，共有 1 个；
• 8 的质因数是 2、2、2，共有 3 个；
• 9 的质因数是 3、3，共有 2 个；
• 10 的质因数是 2、5，共有 2 个。

6 到 10 之间的数中质因数最多的是 8，质因数有 3 个，故输出 3。

输入格式

输入两个正整数 N 和 M(2≤N≤M≤1e6)，两个正整数之间用一个空格隔开。

输出格式

输出一个整数，表示质因数个数中的最大值。

样例

样例输入 1

6 10

样例输出 1

3

数据范围

• 2≤N≤M≤1e6
• 时间限制：1000MS
• 内存限制：128MB

知识点与难度

• 知识点：质数、埃筛和欧筛（质因数分解）
• 难度：Mid+

测试点分布