3233 统计不是特殊数字的数字数量

题目链接

3233. 统计不是特殊数字的数字数量

分析

首先考虑什么样的数才是特殊数字

$1$ 没有真因数，对于质数 $p$ 来说，只有一个真因数，所以排除。由于因数都是成对出现，所以对于其余的数来说，只有质数的平方 $p^2$ 才满足特殊数字的要求，其余的数至少会有三个真因数

所以使用质数筛筛选出区间 $[0, \lfloor \sqrt r \rfloor]$ 中的质数，并判断其平方是否在区间中即可

代码实现

class Solution {
public:
    int nonSpecialCount(int l, int r) {
        int ans = r - l + 1, n = sqrt(r) + 1;
        vector<int> primes;
        vector<bool> isnp(n + 1, 0);
        for (int i = 2; i <= n; i++)
        {
            if (!isnp[i])
            {
                primes.push_back(i);
                if(l <= i * i && r >= i * i)
                    ans--;
            }
            for (int p : primes)
            {
                if (p * i > n)
                    break;
                isnp[p * i] = 1;
                if (i % p == 0)
                    break;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(\lfloor \sqrt r \rfloor)$，$r$ 为区间的右边界
• 空间复杂度：$O(n)$