网站弹窗广告代码,淘宝做女鞋在哪个网站找货,淘客推广怎么做,做网站公司(信科网络)给你两个 正整数 l 和 r。对于任何数字 x#xff0c;x 的所有正因数#xff08;除了 x 本身#xff09;被称为 x 的 真因数。
如果一个数字恰好仅有两个 真因数#xff0c;则称该数字为 特殊数字。例如#xff1a;
数字 4 是 特殊数字#xff0c;因为它的真因数为 1 和…给你两个 正整数 l 和 r。对于任何数字 xx 的所有正因数除了 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 r4) res--;// 从3开始遍历奇数因为偶数都能被2整除for(int i 3; i n; i2){// 判断i是否是质数if(prime_number[i] 0){// 如果该质数的乘积在【lr】范围内则表示范围内有一个特殊数字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;}
}
