小Z找质数(标签-矩阵)

Question

有N行M列的整数，小Z从第一行第一列开始观察，他有一个奇怪的想法，当他找到第一个质数时，他想知道，与这个质数在同一行，同一列、同一斜线上的数也是质数的个数有多少个？（包括第一个质数）由于矩阵可能很大，请你帮助小Z实现这个想法。

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

#include <iostream>
#include <vector>
#include <cmath>

bool is_prime(int num) {
    if (num <= 1) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    for (int i = 3; i <= std::sqrt(num); i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

int count_primes_in_matrix(const std::vector<std::vector<int>>& matrix, int row, int col) {
    int N = matrix.size();
    int M = matrix[0].size();
    int count = 0;

    // Check the same row
    for (int j = 0; j < M; ++j) {
        if (is_prime(matrix[row][j])) count++;
    }

    // Check the same column
    for (int i = 0; i < N; ++i) {
        if (is_prime(matrix[i][col])) count++;
    }

    // Check the main diagonal
    int start_row = row - std::min(row, col);
    int start_col = col - std::min(row, col);
    for (int i = 0; i <= std::min(N - start_row - 1, M - start_col - 1); ++i) {
        if (is_prime(matrix[start_row + i][start_col + i])) count++;
    }

    // Check the secondary diagonal
    start_row = row + std::min(N - row - 1, col);
    start_col = col - std::min(N - row - 1, col);
    for (int i = 0; i <= std::min(start_row, M - start_col - 1); ++i) {
        if (is_prime(matrix[start_row - i][start_col + i])) count++;
    }

    return count;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<std::vector<int>> matrix(N, std::vector<int>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            std::cin >> matrix[i][j];
        }
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (is_prime(matrix[i][j])) {
                int count = count_primes_in_matrix(matrix, i, j);
                std::cout << "质数(" << matrix[i][j] << ")在矩阵中同行、同列和对角线上的质数个数为： " << count << std::endl;
                return 0;
            }
        }
    }

    std::cout << "没有找到质数" << std::endl;
    return 0;
}