UVa 10533 - Digit Primes

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

數字其本身為質數，各項和也為質數，此時稱它為 digit prime 。
找出 t1 ~ t2 間有幾個 digit prime ? (含 t1 , t2)

Solution

先建出質數表後，再從建好的質數表拿質數出來，可利用 sieve[] 來判斷各項和是否也為質數，來完成 digit prime 表。

題目要求範圍內的 x ，把 0 ~ x 的 digit prime 個數打好表。

記得輸入給的兩數是包含在內的!

Code

UVa 10533UVa 10533 - Digit Primes

#include<cstdio>
#include<cmath>
#define N 1000000
#define M 100000

bool sieve[N] = { true, true };
int prime[M], digit_prime[M], ans[N];
int main()
{
    int i, j, k;
    int m = sqrt(N), count = 0;
    //建質數表
    for (i = 2; i <= m; i++)
    {
        if (!sieve[i])
            for (j = i << 1; j < N; j += i)
                sieve[j] = true;
    }
    for (i = 2; i < N; i++)
        if (!sieve[i])
            prime[count++] = i;

    k = 0;
    //建 digit prime
    for (i = 0; i < count; i++)
    {
        int sum = 0, temp = prime[i];
        while (temp)
        {
            sum += temp % 10;
            temp /= 10;
        }
        if (!sieve[sum])
            digit_prime[k++] = prime[i];
    }

    j = count = 0;
    //0 ~ i 有多少個 digit prime
    for (i = 1; i < N; i++)
    {
        if (i == digit_prime[j])
            count++, j++;

        ans[i] = count;
    }

    int Case;
    //I/O
    scanf("%d", &Case);
    while (Case--)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", ans[b] - ans[a-1]);//有包含a,b
    }

    return 0;
}