[Mảng 1 Chiều Cơ Bản]. Bài 45. Dãy con nguyên tố

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Tác giả:

28tech.com.vn

Nguồn bài:

28Tech

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho mảng A[] gồm N phần tử, bạn hãy đếm số lượng dãy con liên tiếp của A[] có tổng các phần tử là số nguyên tố. 2 dãy con [l, r] và [l1, r1] được coi là khác nhau nếu l != l1 hoặc r != r1.

Đầu vào

Dòng 1 là N : số phần tử trong mảng

Dòng 2 là N phần tử cách nhau 1 khoảng trắng

Giới hạn

1<=N<=1000

0<=A[i]<=1000

Đầu ra

In ra số lượng dãy con thỏa mãn

Ví dụ :

Input 01

5
9 2 3 5 4

Output 01

Giải thích :

Các dãy con thỏa mãn : {2}, {3}, {5}, {2, 3}, {9, 2}, {9, 2, 3, 5, 4}, {9, 2, 3, 5}

Bình luận

Hãy đọc nội quy trước khi bình luận.

VDev đã bình luận lúc 15, Tháng 3, 2025, 6:38

FULL AC

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[10000011], cnt = 0, s = 0;
ll check(ll n){
    if(n < 2){
        return 0;
    }
    for(ll i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0;
        }
    }
    return 1;
}
int main(){
    ll n;
    cin >> n;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(ll i = 1; i <= n; i++){
            s = 0;
            for(ll j = i; j <= n; j++){
                s += a[j];
                if(check(s)) cnt++;
            }
    }
    cout << cnt;
    return 0;
}

0

BaoHuangg đã bình luận lúc 3, Tháng 3, 2025, 10:43

full ac:

var n, i, j, dem: longint; a: array[1..1000] of longint; s: int64;

function nt(n: longint): boolean; var i: longint; begin if n < 2 then exit(false); for i := 2 to trunc(sqrt(n)) do if n mod i = 0 then exit(false); exit(true); end; begin // assign(input, 'a.inp'); reset(input); // assign(output, 'a.out'); rewrite(output); readln(n); for i := 1 to n do read(a[i]); dem := 0; for i := 1 to n do begin s := 0; for j := i to n do begin s := s + a[j]; if nt(s) then inc(dem); end; end; writeln(dem);

// close(input); // close(output); end.

-23

tansuperhot2010 đã bình luận lúc 29, Tháng 8, 2024, 8:13

dễ vãi

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.