建设投资基金管理有限公司网站市场调研报告模板

给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。

如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：

• 数字 4 是 特殊数字，因为它的真因数为 1 和 2。
• 数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。

返回区间 [l, r] 内 不是 特殊数字 的数字数量。

示例 1：

输入： l = 5, r = 7

输出： 3

解释：

区间 [5, 7] 内不存在特殊数字。

示例 2：

输入： l = 4, r = 16

输出： 11

解释：

区间 [4, 16] 内的特殊数字为 4 和 9。

提示：

• 1 <= l <= r <= 10^9

我的解答：

class Solution {public int nonSpecialCount(int l, int r) {int res = r - l + 1;int n = (int)  Math.sqrt(r);int[] prime_number = new int[n + 1];// 单独判断范围内是否包含4if(l <=4 && r>=4) res--;// 从3开始遍历奇数，因为偶数都能被2整除for(int i = 3; i <= n; i+=2){// 判断i是否是质数if(prime_number[i] == 0){// 如果该质数的乘积在【l，r】范围内，则表示范围内有一个特殊数字i*i，需要减一if(i*i >=l && i*i <= r){res--;}// 后面所有i的倍数都是质数，因为能被i整除for(int j = i * 2;j <= n;j += i){prime_number[j] = 1;}}}return res;}
}