力扣题解 3233. 统计不是特殊数字的数字数量（中等）
Problem: 3233. 统计不是特殊数字的数字数量
题目重述
给定两个正整数 ( l ) 和 ( r )，我们需要找出在区间 ([l, r]) 内的数字中，不是特殊数字的数量。一个数字被称为特殊数字，当且仅当它有且仅有两个真因数。根据定义，真因数是指除了数字本身之外的所有正因数。
关键词提取
- 正整数
- 真因数
- 特殊数字
- 区间 ([l, r])
- 数量
特殊数字分析
-
因子的性质：
- 一个整数的因子通常成对出现。例如，考虑数字 12，其因子有 1, 2, 3, 4, 6, 和 12，这些因子可以成对匹配：1 和 12，2 和 6，3 和 4。因此，因子的数量通常是偶数。
- 然而，对于完美的平方数（如 4, 9, 16 等），存在一个因子是它自身的平方根（例如，4 的平方根是 2），导致该数字的因子数量不成对，从而使得平方数的因子总数是奇数。
-
特殊数字的特征：
- 由上述性质可得，若某个数是特殊数字，则它必须是一个平方数。
- 进一步分析，若这个特殊数字被表示为 ( n^2 )（其中 n 是正整数），当我们去掉这个数字本身（( n^2 )）和 1 后，该数字只剩下一个因子。为了说明这一点，我们可以表示 ( n^2 ) 的因子为 1、( n ) 和 ( n^2 )。去除 1 和 ( n^2 ) 后，剩下的因子就是 ( n )。
-
质数的要求：
- 由于 ( n ) 是剩余的唯一因子，而根据特殊数字的定义，这个因子也必须是质数。因此，特殊数字的形式可以表示为一个质数的平方。
思路一：使用质数筛法
class Solution {
public int nonSpecialCount(int l, int r) {
// 计算上限，即 r 的平方根加 1
int upperLimit = (int) Math.sqrt(r) + 1;
boolean[] isPrime = new boolean[upperLimit + 1];
// 初始化 isPrime 数组，将所有值设为 true
for (int i = 2; i <= upperLimit; i++) {
isPrime[i] = true;
}
// 埃拉托斯特尼筛法寻找质数
for (int i = 2; i * i <= upperLimit; i++) {
if (isPrime[i]) {
// 将 i 的所有倍数标记为非质数
for (int j = i * i; j <= upperLimit; j += i) {
isPrime[j] = false;
}
}
}
// 收集特殊数字（即质数的平方）
ArrayList<Integer> specialNumbers = new ArrayList<>();
for (int i = 2; i <= upperLimit; i++) {
if (isPrime[i]) {
int square = i * i;
// 判断平方是否在区间 [l, r] 内
if (square >= l && square <= r) {
specialNumbers.add(square);
}
}
}
// 计算非特殊数字的数量
int totalNumbers = r - l + 1;
int nonSpecialCount = totalNumbers - specialNumbers.size();
return nonSpecialCount;
}
}
思路二：使用映射 + 质数筛法
class Solution {
public int nonSpecialCount(int l, int r) {
// 计算上限，即 r 的平方根加 1
int upperLimit = (int) Math.sqrt(r) + 1;
boolean[] isPrime = new boolean[upperLimit + 1];
// 初始化 isPrime 数组，将所有值设为 true
for (int i = 2; i <= upperLimit; i++) {
isPrime[i] = true;
}
// 埃拉托斯特尼筛法寻找质数
for (int i = 2; i * i <= upperLimit; i++) {
if (isPrime[i]) {
// 将 i 的所有倍数标记为非质数
for (int j = i * i; j <= upperLimit; j += i) {
isPrime[j] = false;
}
}
}
// 使用 HashMap 存储特殊数字（即质数的平方）
HashMap<Integer, Integer> specialCountMap = new HashMap<>();
for (int i = 2; i <= upperLimit; i++) {
if (isPrime[i]) {
int square = i * i;
// 判断平方是否在区间 [l, r] 内
if (square >= l && square <= r) {
specialCountMap.put(square, specialCountMap.getOrDefault(square, 0) + 1);
}
}
}
// 计算非特殊数字的数量
int totalNumbers = r - l + 1;
int nonSpecialCount = totalNumbers - specialCountMap.size();
return nonSpecialCount;
}
}
原文地址：https://blog.csdn.net/wxdzuishaui/article/details/143964878
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！