SỐ SONG NGUYÊN TỐ

Dạng bài

Đ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

Bình luận

#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;
}

-4

Phản hồi

2 bình luận nữa