1000ms

Difficulty: 5

所属公司 : 阿里

时间 :2025年8月30日-阿里淘天(算法岗)

算法与标签>数学

会员或题库专享

请先，开通会员或购买题库阿里系机考题库，可解锁完整内容。

购买阿里系机考题库开通会员

会员专享

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

购买题库开通会员

解题思路

一个大于 $1$ 的整数恰好有三个不同的正因子，当且仅当它是某个素数的平方。
- 设 $n = p^2$ （ $p$ 为素数），其因子为 $1, p, p^2$ 共三个。
- 反之，若 $n$ 恰有三个因子，其素因数分解必须为 $p^2$ 的形式。
  因此，题目中的“三叶数”等价于素数的平方。
给定查询区间 $[L, R]$ ，三叶数的数量等于满足 $p^2 \in [L, R]$ 的素数 $p$ 的个数。

题目内容

小蓝在翻阅数学书籍时，注意到一类特殊的正整数：如果一个大于 $1$ 的整数恰好有三个不同的正因子，她就称之为“三叶数”。例如， $4$ 的因子有 $1,2,4$ ，一共三个，因此 $4$ 是一个三叶数；而 $6$ 的因子有 $1,2,3,6$ ，共四个，不是三叶数。

现在她有一个长度为 $Q$ 的查询列表，每个查询给出一个区间 $[L,R]$ 。你需要帮助小蓝计算每个区间内有多少个三叶数。

数据范围：查询次数 $Q$ 不超过 $10^4$ ，区间端点的绝对值不超过 $10^{14}$ ，且保证 $1 \le L \le R \le 10^{14}$ 。

输入描述

第一行包含一个整数 $Q$ （ $1 \le Q \le 10^4$ ），表示查询的次数。