[Mảng 1 Chiều Cơ Bản]. Bài 47. Dãy nguyên tố dài nhấ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 tìm dãy con liên tiếp đều là số nguyên tố dài nhất. Nếu có nhiều dãy con có cùng độ dài thì in ra dãy con có tổng lớn nhất, và nếu có nhiều dãy con có cùng độ dài lớn nhất và có cùng tổng thì lấy dãy con đầu tiên. Trong trường hợp không tồn tại dãy con liên tiếp đều là số nguyên tố thì in ra NOT FOUND.

Gợi ý :

Bước 1. Sàng số nguyên tố để kiểm tra nhanh hơn

Bước 2. Duyệt qua mảng và dùng biến đếm, nếu A[i] là số nguyên tố => tăng đếm còn ko thì cập nhật đếm xem có lớn hơn kỷ lục đang có hay ko, nếu lớn hơn thì cập nhật, còn nếu chỉ bằng kỉ lục thì so sánh thêm tổng của dãy con. Reset biến đếm và tổng về 0 để xét lại dãy mới.

Đầu vào

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

Dòng 2 là N số trong mảng cách nhau 1 dấu cách

Giới hạn

1<=N<=10^6

0<=A[i]<=10^6

Đầu ra

Dòng 1 in độ dài dãy con

Dòng 2 in dãy con thỏa mãn

Ví dụ :

Input 01

10
3 1 1 11 7 13 5 0 10 5

Output 01

4
11 7 13 5

Bình luận

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

tuyen_pham đã bình luận lúc 26, Tháng 8, 2024, 15:18

include <bits/stdc++.h>

using namespace std; int n,a[1000000],s[1000000],res=0,maxx=0; string N; int kiem(int doiso){ for(int i=2;i*i<=doiso;i++){ if(doiso%i==0) return 0; } return 1; } int main() { //freopen("codedao.inp","r",stdin); //freopen("codedao.out","w",stdout);

cin>>n;
for(int i=0;i&lt;n;i++){
    cin>>a[i];s[i]=a[i];
}
for(int i=0;i&lt;n;i++){
    if(a[i]==1||a[i]==0) a[i]=0;
    else if(a[i]==2) a[i]=1;
    else if(kiem(a[i])==1) a[i]=1;
    else a[i]=0;
}
for(int i=0;i<=n;i++){
    if(a[i]==1){
        res++;
    }
    else{
        if(res>=maxx){
            N="";
            for(int j=i-res;j&lt;i;j++){
                N+=to_string(s[j])+" ";
            }maxx=max(res,maxx);
        }
        res=0;
    }
}
cout<&lt;maxx<<endl<<N;
//for(int i=0;i&lt;n;i++) cout<&lt;a[i]<<" ";

}

-3

minhquan2905 đã bình luận lúc 28, Tháng 7, 2024, 16:54

https://www.youtube.com/watch?v=dQw4w9WgXcQ :>

define ll long long

int prime[1000001]; void sang(){ for(int i = 0;i < 1000001;i++){ prime[i]=1; } prime[0] = prime[1] = 0; for(int i=2;i<=sqrt(1000000);i++){ if(prime[i]){ for(int j=i*i;j<=1000000;j+=i){ prime[j] = 0; } } } }

sang();
int n; cin >> n;
int a[n];
for(int &x : a){
    cin >> x;
}
int idx = 0, vt, cnt = 0, l_max=-1e9;
ll tong = 0, max = -1e9;
for(int i=0;i < n;i++){
    if(prime[a[i]]){
        tong += a[i];
        idx = i;
        cnt++;
       if(cnt > l_max){ //chieu dai > ki luc, cap nhat max luon
            l_max = cnt;
            vt = idx;
            max = tong;
        }
        else if(cnt == l_max){
            if(tong > max){
                max = tong;
                vt = idx;
            }
        } 
    }
    else{
        tong = 0, idx = 0, cnt = 0;
    }
    }
if(l_max < 1){
    cout << "NOT FOUND" << endl;
}
else{
    cout << l_max << endl;
    for(int i = vt - l_max + 1; i<=vt;i++){
        cout << a[i] << " ";
    }
}

-3

hackerlo2803 đã bình luận lúc 27, Tháng 6, 2024, 15:43 ← chỉnh sửa →

include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll snt[1000001];

void sang() { memset(snt, 1, sizeof(snt));

snt[0] = snt[1] = 0;
for (ll i = 2 ; i * i <= 1000000; i++){
    if (snt[i]){
        for (ll j = i*i ; j <= 1000000 ; j+=i){
            snt[j] = 0;
        }
    }
}

}

int main() { sang(); iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll n; cin >> n;

ll a[n];
for (ll i = 0; i < n ; i++){
    cin >> a[i];
}

ll dem = 0, vt, kiluc = 0;
bool check = false;

for (ll i = 0 ; i < n ; i++) {
    if (snt[a[i]]) dem++;
    else {
        if (dem > kiluc) {
            kiluc = dem;
            vt = i - dem;
            check = true;
        }
        dem = 0;
    }
}

if (dem > kiluc) { 
    kiluc = dem;
    vt = n - dem;
    check = true;
}

if (check == true){ 
    cout << kiluc << "\n";
    for (ll i = vt ; i < vt + kiluc ; i++){
        cout << a[i] << " ";
    }
    cout << "\n";
} else cout << "NOT FOUND";
return 0;

}

-4
NTH11112222 đã bình luận lúc 14, Tháng 6, 2024, 0:04
include<bits/stdc++.h>

using namespace std; vector<bool> sieve(int maxnum) { vector<bool> isprime(maxnum + 1, true); isprime[0] = isprime[1] = false; for (int i = 2; i * i <= maxnum; ++i) { if (isprime[i]) { for (int j = i * i; j <= maxnum; j += i) { isprime[j] = false; } } } return isprime; } vector<int> tim(const vector<int>& A, const vector<bool>& isprime) { int maxlen = 0; int maxsum = 0; vector<int> a; int currlen = 0; int currsum = 0; vector<int> b; for (int num : A) { if (isprime[num]) { currlen++; currsum += num; b.pushback(num); } else { if (currlen > maxlen || (currlen == maxlen && currsum > maxsum)) { maxlen = currlen; maxsum = currsum; a = b; } currlen = 0; currsum = 0; b.clear(); } } if (currlen > maxlen || (currlen == maxlen && currsum > max_sum)) { a = b; }

return a;

} int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n; cin >> n; vector<int> A(n); for (int i = 0; i < n; i++) { cin >> A[i]; } int maxnum = *maxelement(A.begin(), A.end()); vector<bool> isprime = sieve(maxnum);

vector<int> res = tim(A, is_prime); if (res.empty()) { cout << "NOT FOUND" << endl; } else { cout << res.size() << endl; for (int x : res) { cout << x << ' '; } cout << endl; } return 0;

} Code tham khảo cho ai đang gặp kk nhé!

0

Tu đã bình luận lúc 4, Tháng 6, 2024, 3:22

Anh đẹp trai nào ac rồi vào xem code giúp em với

-1

quyetbnaz09 đã bình luận lúc 27, Tháng 5, 2024, 8:24

mng ơi cái test thứ 5 là j v ạ, e sai test đấy ai AC r ghé qua code e với

-2

zeit_lars2808 đã bình luận lúc 15, Tháng 5, 2024, 10:17

Cho em hỏi test 4 với test 5 là gì v ạ??

0

vudinhlong đã bình luận lúc 6, Tháng 4, 2024, 15:50

ai AC rồi vào xem code em có thiếu sót gì ạ :))

-1

nhr1410x đã bình luận lúc 7, Tháng 4, 2024, 5:00

Cái đoạn mà a[i] == 1 trong cái điều kiện anh thiếu trường hợp cnt < res phải cập nhật thg cnt = 0,cursum= 0 nx á,với đề nói nếu lấy tổng bằng nhau thì lấy dãy đầu tien nên cái đoạn kia a sửa lại thành cursum > max_sum là ok

-1

vudinhlong đã bình luận lúc 9, Tháng 4, 2024, 17:20

À chắc bản best solve của mình là do mình spam thay dấu đấy, chứ đúng là > thôi :DD

-1

vudinhlong đã bình luận lúc 9, Tháng 4, 2024, 17:18

Ôi vc cảm ơn bạn nhớ :33