1000ms

Difficulty: 6

所属公司 : 美团

时间 :2025年4月5日-开发岗

算法与标签>数学

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

题解

题面描述

给定一个正整数 $n$ ，要求统计所有不超过 $n$ 的 “卓越数” 的个数。
这里“卓越数”的定义为：

$x$ 为正整数；
存在一个质数 $p$ 满足 $x \bmod p = 0$ 且 $p \times p \ge x$ 。

题目内容

我们定义一类特殊的正整数，称为「卓越数」。一个正整数 $x$ 被称为卓越数，当且仅当存在一个质数 $p$ 同时满足以下两个条件：

$p$ 整除 $x$ ；
$p * p \ge x$ 。

现在给定一个正整数 $n$ ，请你求出所有不超过 $n$ 的卓越数的个数。

约束条件： $n$ 满足 $1 \le n \le 5 * 10^6$ 。