标签： 埃氏筛

目标

给你两个 正整数 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

提示：

• A special number must be a square of a prime number.
• We need to find all primes in the range [sqrt(l), sqrt(r)].
• Use sieve to find primes till sqrt(10^9).

思路

返回给定区间 [l, r] 内不是特殊数字的数字个数，所谓特殊数字指除了它本身恰好有两个正因数的数字。

一看到数据范围是 10^9 就不可能使用使用暴力解法去判断每一个数字是不是 l 或 r 的因数，要么使用二分要么预处理。特殊数字是确定的，它除了自身以外只有两个因数，1 一定是一个，即除了 1 和它本身只有一个因数。看了提示说特殊数字是质数的平方，我们需要找到所有在 [√l, √r] 范围内的质数，可以预处理 √10^9 内的质数。二分查找 [l, r] 范围内质数的个数，然后减掉即可。

埃氏筛的基本思想是创建一个 boolean[] 标记查询范围内的数是否为质数，初始时均标记为 true。从 2 开始遍历（0和 1 后面直接过滤掉了)，直到 i < √end 即 i * i < end。在循环内部，如果当前值是质数，则将 i * i，i * (i + 1)，i * (i + 2)，…… 标记为非质数。比如在 2 的循环内，所有大于 2 的偶数都被标为非质数，以此类推，像筛子一样将质数筛选出来。

// todo 最后也可以使用前缀和计算个数

代码

/**
 * @date 2024-11-22 9:07
 */
public class NonSpecialCount3233 {

    public static int[] primes;

    static {
        List<Integer> primeList = new ArrayList<>();
        int end = (int) Math.ceil(Math.sqrt(1000000001));
        boolean[] isPrime = new boolean[end + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i * i <= end; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= end; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        // 前面没有将 isPrime[0] isPrime[1] 置为false，这里从2开始
        for (int i = 2; i <= end; i++) {
            if (isPrime[i]) {
                primeList.add(i);
            }
        }
        int cnt = primeList.size();
        primes = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            primes[i] = primeList.get(i);
        }
    }

    public int nonSpecialCount_v1(int l, int r) {
        int ceilLeft = (int) Math.ceil(Math.sqrt(l));
        int right = (int) Math.sqrt(r);
        if (ceilLeft > right) {
            return r - l + 1;
        }
        int a = Arrays.binarySearch(primes, ceilLeft);
        if (a < 0) {
            // 获取插入点，说明原来该位置的值大于ceilLeft
            a = -a - 1;
        }
        int b = Arrays.binarySearch(primes, right);
        if (b < 0) {
            // 这里多减了1，因为插入点是第一个大于right的位置，减1则小于 right
            b = -b - 2;
        }
//        return r - l + 1 - (b - a + 1);
        return r - l - b + a;
    }

}

性能

目标

给你一个整数数组 nums。

返回两个（不一定不同的）质数在 nums 中 下标 的 最大距离。

示例 1：

输入： nums = [4,2,9,5,3]
输出： 3
解释： nums[1]、nums[3] 和 nums[4] 是质数。因此答案是 |4 - 1| = 3。

示例 2：

输入： nums = [4,8,2,8]
输出： 0
解释： nums[2] 是质数。因为只有一个质数，所以答案是 |2 - 2| = 0。

说明：

• 1 <= nums.length <= 3 * 10^5
• 1 <= nums[i] <= 100
• 输入保证 nums 中至少有一个质数。

思路

找出数组中质数的最远距离（下标之差）。

知识点：

• 自然数：非负整数
• 质数：只能被1和它本身整除的大于1的自然数
• 合数：不是质数的大于1的自然数

如果 n 是一个合数，那么它可以分解为两个自然数 a、b 的乘积，即 n = a * b。设 a ≤ b ，如果 a ≥ √n ，那么 a * b ≥ n。 也就是说 a、b 要么同时等于 √n，要么一个大于一个小于 √n，不可能同时大于√n。于是判断一个数是否是质数，只需判断 n 是否能够整除 1 ~ √n 。

除了2的偶数都不是质数，因此自增的步长可以设为2。

更进一步分析，所有质数除了2和3外，都形如 6k - 1 或 6k + 1。考虑 n % 6 ：

• 余数为0，首先6不是质数，能被6整除的数也不是质数
• 余数为2、4，表明能够被2整除，不是质数
• 余数为3，表明能被3整除，不是质数
• 余数为5，6k - 1
• 余数为1，6k + 1

从5开始，步长可以设为6。

代码

/**
 * @date 2024-07-02 9:13
 */
public class MaximumPrimeDifference3115 {

    public int maximumPrimeDifference_v2(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (!isPrimeNumber(nums[i])) {
            i++;
        }
        while (!isPrimeNumber(nums[j])) {
            j--;
        }
        return j - i;
    }

    public boolean isPrimeNumber(int num) {
        if (num == 1) {
            return false;
        }
        if (num == 2) {
            return true;
        }
        if (num % 2 == 0) {
            return false;
        }
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static boolean isPrimeNumber_v1(int num) {
        if (num <= 1) {
            return false;
        }
        if (num <= 3) {
            return true; 
        }
        if (num % 2 == 0 || num % 3 == 0) {
            return false; 
        }
        for (int i = 5; i * i <= num; i += 6) {
            // i = 6k - 1, i + 2 = 6k + 1
            if (num % i == 0 || num % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

性能