class Solution {
public:
int nonSpecialCount(int l, int r) {
}
};
100371. 统计不是特殊数字的数字数量
给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。
如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：
返回区间 [l, r] 内 不是 特殊数字 的数字数量。
示例 1：
输入： l = 5, r = 7
输出： 3
解释：
区间 [5, 7] 内不存在特殊数字。
示例 2：
输入： l = 4, r = 16
输出： 11
解释：
区间 [4, 16] 内的特殊数字为 4 和 9。
提示：
1 <= l <= r <= 109相似题目
原站题解
python3 解法, 执行用时: 61 ms, 内存消耗: 17.8 MB, 提交时间: 2024-07-29 17:39:17
def tag_primes_eratosthenes(n): # 返回一个长度n的数组p，如果i是质数则p[i]=1否则p[i]=0
primes = [1] * n
primes[0] = primes[1] = 0 # 0和1不是质数
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i::i] = [0] * ((n - 1 - i * i) // i + 1)
return primes
primes = tag_primes_eratosthenes(31623)
pi = list(accumulate(primes))
class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
return r - l + 1 - (pi[isqrt(r)] - pi[isqrt(l - 1)])
golang 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2024-07-29 17:38:56
const mx = 31622
var pi = [mx + 1]int{}
func init() {
for i := 2; i <= mx; i++ {
if pi[i] == 0 { // i 是质数
pi[i] = pi[i-1] + 1
for j := i * i; j <= mx; j += i {
pi[j] = -1 // 标记 i 的倍数为合数
}
} else {
pi[i] = pi[i-1]
}
}
}
func nonSpecialCount(l, r int) int {
cntR := pi[int(math.Sqrt(float64(r)))]
cntL := pi[int(math.Sqrt(float64(l-1)))]
return r - l + 1 - (cntR - cntL)
}
java 解法, 执行用时: 14 ms, 内存消耗: 40.1 MB, 提交时间: 2024-07-29 17:38:28
class Solution {
private static final int MX = 31622;
private static final int[] PI = new int[MX + 1];
static {
for (int i = 2; i <= MX; i++) {
if (PI[i] == 0) { // i 是质数
PI[i] = PI[i - 1] + 1;
for (int j = i * i; j <= MX; j += i) {
PI[j] = -1; // 标记 i 的倍数为合数
}
} else {
PI[i] = PI[i - 1];
}
}
}
public int nonSpecialCount(int l, int r) {
return r - l + 1 - (PI[(int) Math.sqrt(r)] - PI[(int) Math.sqrt(l - 1)]);
}
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 8.3 MB, 提交时间: 2024-07-29 17:37:38
const int MX = 31622;
int pi[MX + 1];
auto init = [] {
for (int i = 2; i <= MX; i++) {
if (pi[i] == 0) { // i 是质数
pi[i] = pi[i - 1] + 1;
for (int j = i * i; j <= MX; j += i) {
pi[j] = -1; // 标记 i 的倍数为合数
}
} else {
pi[i] = pi[i - 1];
}
}
return 0;
}();
class Solution {
public:
int nonSpecialCount(int l, int r) {
return r - l + 1 - (pi[(int) sqrt(r)] - pi[(int) sqrt(l - 1)]);
}
};
python3 解法, 执行用时: 49 ms, 内存消耗: 16.6 MB, 提交时间: 2024-07-29 17:37:20
'''
正难则反，统计区间 [l, r] 内有多少特殊数字
'''
MX = 31622 # sqrt(10**9)
pi = [0] * (MX + 1)
for i in range(2, MX + 1):
if pi[i] == 0: # i 是质数
pi[i] = pi[i - 1] + 1
for j in range(i * i, MX + 1, i):
pi[j] = -1 # 标记 i 的倍数为合数
else:
pi[i] = pi[i - 1]
class Solution:
def nonSpecialCount(self, l: int, r: int) -> int:
return r - l + 1 - (pi[isqrt(r)] - pi[isqrt(l - 1)])