使用C++编写，找到子数组中的质数数量

题意解析

给定一个整数数组，找到其中子数组中质数的数量。质数指大于1且只能被1和它本身整除的整数。

问题分析

本题需要遍历数组中所有可能的子数组，然后判断子数组中质数的数量。对于一个长度为n的数组，其子数组个数可以达到n(n+1)/2，因此暴力枚举所有子数组的时间复杂度为O(n^3)。

我们可以对此进行优化，从O(n^3)降至O(n^2)，具体步骤如下：

Step 1

用isPrime[i]表示数字i是否为质数，在程序中先筛选出0到数组最大元素值max_value之间的全部质数。时间复杂度O(max_value*log(log(max_value)))。

bool isPrime[max_value+1];
memset(isPrime, true, sizeof(isPrime));
for (int i = 2; i*i <= max_value; i++) {
    if (isPrime[i]) {
        for (int j = i*i; j <= max_value; j += i) {
            isPrime[j] = false;
        }
    }
}

Step 2

计算以每个元素为子数组右端点，长度不大于max_len的子数组中质数的数量。将这些数量保存在count[i][j]中，其中i表示右端点，j表示子数组长度。时间复杂度O(n*max_len)。

int count[n][max_len+1];
for (int i = 0; i < n; i++) {
    for (int j = 1; j <= max_len && i+j-1 < n; j++) {
        if (j == 1) {
            count[i][j] = isPrime[arr[i]];
        } else {
            count[i][j] = count[i][j-1] + isPrime[arr[i+j-1]];
        }
    }
}

Step 3

用类似前缀和的方法，计算以每个元素为子数组右端点，从该元素向左延伸的填充为max_len长度的子数组中质数的数量。将这些数量保存在lcount[i][j]中，其中i表示右端点，j表示相对于右端点的偏移量。时间复杂度O(n*max_len)。

int lcount[n][max_len+1];
for (int i = 0; i < n; i++) {
    lcount[i][0] = 0;
    for (int j = 1; j <= max_len && i-j+1 >= 0; j++) {
        lcount[i][j] = lcount[i][j-1] + isPrime[arr[i-j+1]];
    }
}

Step 4

对于以i为右端点，长度为j的子数组，其中的质数数量为count[i][j]，使用lcount[i-j][j]计算左端点到i-j所对应位置的质数数量，从而得出整个子数组中质数的数量。时间复杂度O(n^2)。

int result = 0;
for (int i = 0; i < n; i++) {
    for (int j = 1; j <= min(i+1, max_len); j++) {
        result += isPrime[arr[i]] + lcount[i-j][j-1] - count[i][j-1];
    }
}

完整代码

#include <bits/stdc++.h>
using namespace std;
const int max_len = 100; // 子数组最大长度
const int max_value = 10000; // 数组中可能出现的最大元素值
bool isPrime[max_value+1]; // 数字i是否为质数
int count[max_len+1]; // 数组元素中长度为j的子数组中质数的数量
int lcount[max_len+1]; // 以lcount[i]为右端点的子数组中质数的数量
int solve(int arr[], int n) {
    int result = 0;
    memset(isPrime, true, sizeof(isPrime)); // 初始化所有数字为质数
    memset(count, 0, sizeof(count)); // 初始化数组count
    memset(lcount, 0, sizeof(lcount)); // 初始化数组lcount
    // 筛选出max_value之内的全部质数
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i*i <= max_value; i++) {
        if (isPrime[i]) {
            for (int j = i*i; j <= max_value; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 计算count数组
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= max_len && i+j-1 < n; j++) {
            if (j == 1) {
                count[j] = isPrime[arr[i]];
            } else {
                count[j] = count[j-1] + isPrime[arr[i+j-1]];
            }
        }
        for (int j = 1; j <= min(i+1, max_len); j++) {
            result += count[j];
        }
    }
    
    // 计算lcount数组
    for (int i = n-1; i >= 0; i--) {
        for (int j = 1; j <= max_len && i+j-1 < n; j++) {
            if (j == 1) {
                lcount[j] = isPrime[arr[i]];
            } else {
                lcount[j] = lcount[j-1] + isPrime[arr[i+j-1]];
            }
        }
        for (int j = 1; j <= min(n-i, max_len); j++) {
            count[j] = lcount[j];
        }
        // 计算右端点为i的子数组中质数的数量
        for (int j = 1; j <= min(i+1, max_len); j++) {
            result += count[j];
            if (i-j >= 0 && j < max_len) {
                result -= count[j+1];
                result += lcount[j];
            }
        }
    }
    return result;
}
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = solve(arr, n);
    cout << result << endl;
    return 0;
}