/ Vijos / 题库 /

真因子

真因子

时间限制:0.1秒  内存限制:256M


【问题描述】

  小H正研究自然数的性质,他需要你帮他完成一项统计工作,即:在\(1\) 到 \(N\) 之间有多少个数的 真因子 个数超过 \(S\) 个 。一个数的 真因子,是指不包括这个数本身的因数,例如 6 的真因子有1, 2, 3。

【输入格式】

  一行包含两个正整数 \(N\),\(S\) 。

【输出格式】

  一个整数,表示 \(1\) 到 \(N\) 中有超过S个真因子的数的个数。

【输入输出样例】

 Input

25 4

 Output

4

【样例解释】

  在 1 到 25 中有 4 个数的真因子个数超过了 4 个,分别是:12,18,20,24。其中:
  ● 12 的真因子有:1, 2, 3, 4, 6。
  ● 18 的真因子有:1, 2, 3, 6, 9。
  ● 20 的真因子有:1, 2, 4, 5, 10。
  ● 24 的真因子有:1, 2, 3, 4, 6, 8, 12。

【数据限制】

  \(50\%\) 的数据满足:\(1≤N≤100000\),\(1≤S≤20\)。
  \(100\%\) 的数据满足:\(1≤N≤10000000\),\(1≤S≤100\)。

【来源】

  Mr.he

信息

ID
2783
难度
9
分类
数论 点击显示
标签
(无)
递交数
5
已通过
1
通过率
20%
被复制
2
上传者