Đếm số lượng bảng vuông (con) trong mảng 2 chiều thoả mãn bảng này chứa toàn số nguyên tố

[Kizu (Nhân)]

Em mới học lập trình và gặp 1 bài như sau:
Cho 1 mảng 2 chiều, tìm một bảng vuông có kích thước lớn nhất chỉ chứa toàn số nguyên tố, xuất kích thước hình vuông tìm được, có bao nhiêu hình vuông có cùng kích thước thõa điều kiện bài toán.
Mảng:

Kết quả:

• Kích thước lớn nhất: 2
• Số ô cùng kích thước thõa điều kiện: 3

Lúc đầu em định hướng là tìm 1 số K = min ( dòng, cột ), mảng K x K lúc đầu là mảng vuông lớn nhất có thể có, xong sau đó trong mảng chính em xét mảng vuông ( phần này em mới nghĩ chứ chưa code được ), nếu trong mảng K x K có chứa phần tử không phải là số nguyên tố thì giảm K xuống. Nhưng về sau ý tưởng bị bí vì nếu cho 1 mảng khác lớn rất nhiều thì không biết phải duyệt đến bao giờ ( và em cũng chưa nghĩ ra đc code ). Nên em đăng bài lên để tìm kiếm sự giúp đỡ, định hướng của m.n cho bài này ạ. Mong mọi người giúp đỡ. Cám ơn!

[rogp10]

Đầu tiên đổi hết số nguyên tố thành 1 và còn lại là 0 => bài tìm hòn đảo hình vuông. Bài này dùng dầu loang

[noname00 (HK boy)]

Bạn có thể làm thế này:

prime_count[i][j] đếm (tổng) số lượng số nguyên tố trong bảng từ ô (1, 1) đến ô (i, j).

Như vậy, 1 bảng vuông thoả mãn nếu số lượng số nguyên tố trong bảng đó bằng kích thước của nó.

Bài toán đưa về tìm 1 bảng vuông có tổng các ô trong bảng là bằng kích thước của nó. Áp dụng “tổng tiền tố” với mảng 2 chiều.