SỐ SONG NGUYÊN TỐ

Xem PDF

Điểm: 100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một số nguyên tố là số tự nhiên lớn hơn 1 có 2 ước dương là 1 và chính nó. Một số n được gọi là sổ song nguyên tố nếu n là số nguyên tố và tổng các chữ số của số n cũng là số nguyên tố. Ví dụ số 23 là số song nguyên tố vì 23 là số nguyên tố và tổng các chữ số của số 23 bằng 5 cũng là số nguyên tố.
Yêu cầu: Cho 2 số nguyên L và R với \(1 < L ≤ R ≤ 10^{6}\), hãy tính số lượng các số song nguyên tố thuộc đoạn [L, R].

Dữ liệu vào

  • Gồm một dòng chứa hai số nguyên L và R, mỗi số cách nhau một dấu cách.

Dữ liệu ra

  • Gồm một dòng là số lượng các số song nguyên tố thuộc đoạn [L, R]. Nếu các giá trị của L và R không thỏa mãn điều kiện bài toán thì ghi là -1.

Giới hạn

  • 10% số test ứng với các giá trị của L và R không thỏa mãn điều kiện bài toán;
  • 70% số test ứng với \(1 < L ≤ R ≤ 10^{4}\);
  • 20% số test ứng với \(1 < L ≤ R ≤ 10^{6}\).

Ví dụ

Input
10 30
Output
3

Bình luận

  • dohuyen 7:14 p.m. 25 Tháng 1, 2025

    #include <bits/stdc++.h>
    using namespace std;
    int main(){
        long long isprime[1000006];
        int l,r;
        int sum;
        cin >> l >> r;
        int snt;
        int dem =0;
        for (int i = 2; i <= r; i++){
            isprime[i] = 1;
        }
    
        for (int i = 2; i <= r; i++){
            if (isprime[i]){
                for (int j = i * i; j <= r; j+= i){
                    isprime[j] = 0;
                }
            }
        }
        for (int i = l; i <= r; i++){
            if (isprime[i]){
                sum = 0;
                snt = i;
                while (snt > 0){
                    sum = sum + snt % 10;
                    snt /= 10;
                }
                if (isprime[sum]){
                    dem +=1;
                }
            }
        }
        if (dem > 0){
            cout << dem;
        }
        else{
            cout << "-1";
        }
    
    
    return 0;
    }
    

    giup em toi uu code vs a

    • hungg_261 5:01 p.m. 27 Tháng 7, 2024 đã chỉnh sửa

      Chú ý là nếu input không thỏa ràng buộc \(1<L<=R<=10^6\) thì trả ra -1 nhé;))

      • SBD20_Caominhduc 2:38 p.m. 24 Tháng 7, 2024
        #include <bits/stdc++.h>
        #define ll long long
        const int N=1e7;
        using namespace std;
        int l,r,d;
        bool kt[N+10];
        int tongcs(int n)
        {
            int res=0;
            while(n>0)
            {
                res=res+(n%10);
                n/=10;
            }
            return res;
        }
        int main()
        {
            ios_base::sync_with_stdio(0);cin.tie(NULL);
            cin >> l >> r;
            if(l<1||r<1||l>(int)1e6||r>(int)1e6||l>r)
            {
                cout << -1;
                return 0;
            }
            for(int i=2;i<=r;i++)kt[i]=true;
            for(int i=2;i*i<=r;i++)
            {
                if(kt[i])
                {
                    for(int j=i*i;j<=r;j+=i)kt[j]=false;
                }
            }
            for(int i=l;i<=r;i++)
            {
                if(kt[i])
                {
                    int num=tongcs(i);
                    if(kt[num])
                    {
                        d++;
                    }
                }
            }
            if(d==0)cout << -1;
            else cout << d;
            return 0;
        }