P1865 A % B Problem-526互联

P1865 A % B Problem

题目链接

题意简述

求区间 \([l,r]\) 内质数的个数

解析

前置知识：

素数判断 / 素数筛法
前缀和

质数是指在大于 \(1\) 的自然数中，除了 \(1\) 和它本身以外不再有其他因子的自然数。

一层循环判断 \(2\sim n-1\) 的每一个数是否是它的因子

设 \(n=a\times b\)，则 \(a,b\) 中必有一个小于等于 \(\sqrt{n}\)，另一个大于等于 \(\sqrt{n}\)

因此，可以只判断 \(2\sim \sqrt{n}\) 的数是否为 \(n\) 的因子

static boolean isPrime(int n) {
    if (n == 1) return false;
    for (int i = 2, sq = (int) Math.sqrt(n); i <= sq; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

那如何处理区间素数个数呢？

常规的思路是对每次询问的区间进行素数判断并求个数

但是对于 \(n\) 次询问，每次都判断区间内的素数个数很大程度上会出现重复，所以我们会想到通过空间换时间的方式，将所询问的所有区间内是否是素数这个东西存下来，用到的时候调用就行，于是我们得到了如下代码

import java.util.Scanner;

public class Main {

    static boolean isPrime(int n) {
        if (n == 1) return false;
        for (int i = 2, sq = (int) Math.sqrt(n); i <= sq; ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        boolean[] a = new boolean[m + 1];
        for (int i = 1; i <= m; ++i) {
            a[i] = isPrime(i);
        }
        while (n-- != 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            if (1 <= l && l <= r && r <= m) {
                int sum = 0;
                for (int i = l; i <= r; ++i) {
                    if (a[i]) {
                        ++sum;
                    }
                }
                System.out.println(sum);
            } else {
                System.out.println("Crossing the line");
            }
        }
    }
}

但是在求区间内素数时，仍然有大量重复循环，每次都进行了区间的累加

我们考虑改变询问的式子

\[\begin{aligned} sum_{[l,r]}&=a_l+\cdots+a_r\\ &=(a_1+\cdots+a_{l-1})+a_l+\cdots+a_r-(a_1+\cdots+a_{l-1})\\ &=(a_1+\cdots+a_{l-1}+a_l+\cdots+a_r)-(a_1+\cdots+a_{l-1}) \end{aligned} \]

可以看到变成 \(1\sim r\) 和 \(1\sim l-1\) 的差，他们都是和所给左右端点有关的前缀的和

若定义 \(S\) 为数列 \(a\) 的前缀的和，即 \(S_n=\sum_{i=1}^n a_i\)，则 \(sum[l,r]=S_r-S_{l-1}\)

因此，我们可以预处理出 \(S\) 这个数列，每次询问时只需通过一个减法求得区间 \([l,r]\) 的和

前缀和的定义如下：

对于一个给定的数列 \(A\)，它的前缀和数列 \(S\) 中的第 \(i\) 项表示从第 \(1\) 个元素到第 \(i\) 个元素的总和，即 \(S_i=A_1+A_2+\cdots+A_i\)

定义区间 \([l,r]\) 的和为 \(sum_[l,r]\)，则有如下式子

\[sum_{[l,r]}=\left\{\begin{array}{ll} S_r-S_{l-1} & l\ge 2\\ S_1 & l=1\\ \end{array}\right. \]

Code

import java.util.Scanner;

public class Main {

    static boolean isPrime(int n) {
        if (n == 1) return false;
        for (int i = 2, sq = (int) Math.sqrt(n); i <= sq; ++i) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] a = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            if (isPrime(i)) a[i] = 1;
        }
        // 求 素数个数 的前缀和
        for (int i = 1; i <= m; ++i) {
            a[i] += a[i - 1];
        }
        while (n-- != 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            if (1 <= l && l <= r && r <= m) {
                System.out.println(a[r] - a[l - 1]);
            } else {
                System.out.println("Crossing the line");
            }
        }
    }
}