数论刷题-uva【10533】 - Digit Primes

98 阅读 0 评论 65 点赞

我是靠谱客的博主超帅大象，最近开发中收集的这篇文章主要介绍数论刷题-uva【10533】 - Digit Primes，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A prime number is a positive number, which is divisible by exactly two different integers. A digit prime
is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime
because 4 + 1 = 5 and 5 is a prime number. 17 is not a digit prime because 1 + 7 = 8, and 8 is not
a prime number. In this problem your job is to find out the number of digit primes within a certain
range less than 1000000.

Input

First line of the input file contains a single integer N (0 < N ≤ 500000) that indicates the total number
of inputs. Each of the next N lines contains two integers t1 and t2 (0 < t1 ≤ t2 < 1000000).

Output

For each line of input except the first line produce one line of output containing a single integer that
indicates the number of digit primes between t1 and t2 (inclusive).

Sample Input

3
10 20
10 100
100 10000

Sample Output

1
10
576

Note: You should at least use scanf() and printf() to take input and produce output for this
problem. cin and cout is too slow for this problem to get it within time limit.

题意：判断所给区间中的位素数的个数，位素数为本身为素数并且各位和也为素数

#include <bits/stdc++.h>

using namespace std;

const int Max = 1100000;

bool vis[Max];

int num[Max];

bool Judge(int s)
{
    int ans = 0;
    while(s)
    {
        ans+=(s%10);

        s/=10;
    }

    return (!vis[ans]);
}

void Get()
{

    vis[1] = true;
    for(int i = 2;i<Max;i++)
    {
        if(!vis[i])
        {
            for(int j =i +i;j<Max;j+=i)
            {
                vis[j] = true;
            }
        }
    }

    num[0] = 0;

    for(int i = 1;i<Max;i++)
    {
        num[i] = num[i-1];

        if(!vis[i] && Judge(i))
        {
            num[i] ++;
        }
    }

}

int main()
{
    Get();
    int n;

    int l,r;

    scanf("%d",&n);

    while(n--)
    {
        scanf("%d %d",&l,&r);

        printf("%dn",num[r]-num[l-1]);
    }

    return 0;
}