[Mảng 1 Chiều Cơ Bản]. Bài 47. Dãy nguyên tố dài nhất

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem source:
28Tech
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.



  • -2
    perkbevis2k4  commented on Nov. 24, 2024, 5:15 a.m.

    include <iostream>

    using namespace std;

    int prime[1000001];

    void sieve() { for (int i = 0; i <= 1000000; i++) { prime[i] = 1; // Ban đầu giả sử tất cả các số đều là nguyên tố } prime[0] = prime[1] = 0; // 0 và 1 không phải số nguyên tố

    for (int i = 2; i * i <= 1000000; i++) {  // Lấy đến sqrt(1000000) thay vì 1000
        if (prime[i]) { // Nếu i là số nguyên tố
            for (int j = i * i; j <= 1000000; j += i) {
                prime[j] = 0; // Loại bỏ các bội số của i
            }
        }
    }
    

    }

    int main() { sieve(); // Tạo mảng sàng số nguyên tố int n; cin >> n; // Nhập số lượng phần tử trong mảng int a[n]; for (int i = 0; i < n; i++) { cin >> a[i]; }

    // Biến lưu trữ kết quả
    int maxPrimeCount = 0;    // Số lượng số nguyên tố lớn nhất
    int maxSum = 0;           // Tổng lớn nhất của dãy con nguyên tố
    int currentCount = 0;     // Số lượng số nguyên tố hiện tại
    int currentSum = 0;       // Tổng của dãy con nguyên tố hiện tại
    
    int bestStart = -1;       // Vị trí bắt đầu của dãy tốt nhất
    int bestEnd = -1;         // Vị trí kết thúc của dãy tốt nhất
    int currentStart = 0;     // Vị trí bắt đầu của dãy hiện tại
    
    for (int i = 0; i < n; i++) {
        if (prime[a[i]]) { // Nếu a[i] là số nguyên tố
            if (currentCount == 0) {
                currentStart = i; // Đánh dấu vị trí bắt đầu của dãy mới
            }
            currentCount++;
            currentSum += a[i];
        } else { 
            // Nếu gặp số không phải nguyên tố, kiểm tra kỷ lục
            if (currentCount > maxPrimeCount || 
                (currentCount == maxPrimeCount && currentSum > maxSum)) {
                maxPrimeCount = currentCount;
                maxSum = currentSum;
                bestStart = currentStart;
                bestEnd = i - 1; // Kết thúc trước số không nguyên tố
            }
            // Reset biến đếm và tổng để xét dãy mới
            currentCount = 0;
            currentSum = 0;
        }
    }
    
    // Kiểm tra lần cuối sau khi duyệt hết mảng
    if (currentCount > maxPrimeCount || 
        (currentCount == maxPrimeCount && currentSum > maxSum)) {
        maxPrimeCount = currentCount;
        maxSum = currentSum;
        bestStart = currentStart;
        bestEnd = n - 1;  // Dãy con kết thúc tại cuối mảng
    }
    
    // Nếu không có dãy con nguyên tố nào, bạn có thể in ra 0 hoặc thông báo thích hợp
    if (maxPrimeCount == 0) {
        cout << 0 << endl;
    } else {
        cout << maxPrimeCount << endl; // In số lượng số nguyên tố lớn nhất
        for (int i = bestStart; i <= bestEnd; i++) {
            cout << a[i] << " "; // In dãy con tốt nhất
        }
        cout << endl;
    }
    
    return 0;
    

    }


  • 0
    tuyen_pham  commented on Aug. 26, 2024, 3:18 p.m.

    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]<<" ";
    

    }


  • -5
    minhquan2905  commented on July 28, 2024, 4:54 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -4
    hackerlo2803  commented on June 27, 2024, 3:43 p.m. edited

    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;
    

    }


  • -5
    NTH11112222  commented on June 14, 2024, 12:04 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    Tu  commented on June 4, 2024, 3:22 a.m.

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


  • -3
    quyetbnaz09  commented on May 27, 2024, 8:24 a.m.

    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  commented on May 15, 2024, 10:17 a.m.

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


  • -1
    vudinhlong  commented on April 6, 2024, 3:50 p.m.

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


    • -1
      nhr1410x  commented on April 7, 2024, 5:00 a.m.

      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  commented on April 9, 2024, 5:20 p.m.

        À 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  commented on April 9, 2024, 5:18 p.m.

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