美素数

小明对数的研究比较热爱，一谈到数，脑子里就涌现出好多数的问题，今天，小明想考考你对素数的认识。
问题是这样的：一个十进制数，如果是素数，而且它的各位数字和也是素数，则称之为“美素数”，如29，本身是素数，而且2+9 = 11也是素数，所以它是美素数。
给定一个区间，你能计算出这个区间内有多少个美素数吗？

Input第一行输入一个正整数T，表示总共有T组数据(T <= 10000)。
接下来共T行，每行输入两个整数L，R(1<= L <= R <= 1000000)，表示区间的左值和右值。Output对于每组数据，先输出Case数，然后输出区间内美素数的个数（包括端点值L,R）。
每组数据占一行，具体输出格式参见样例。Sample Input3 1 100 2 2 3 19Sample Output```
Case #1: 14
Case #2: 1
Case #3: 4

```cpp
#include
using namespace std;
const int MAX = 1e6+454;
int Mark[MAX];
int prime[MAX];
int ms[MAX];
int pri(){
    int index = 0;
    for(int i = 2; i < MAX; i++){
        if(!Mark[i]) prime[index++] = i;
        for(int j = 0; j < index && prime[j] * i < MAX; j++){
            Mark[i * prime[j]] = 1;
            if(i % prime[j] == 0) break; 
        }
    }
    return index;
}        
int add(int x){
    int a = 0;
    while(x){
        a += x%10;
        x /= 10;
    }
    return a;
}
int main(){
    int index = pri();
    int n,m;
    int x = 1e6 + 7;
    for(int i = 0; prime[i] < x; i++){
        int g = add(prime[i]);
        if(binary_search(prime,prime+index,g)) ms[prime[i]]++;
    }
    for(int i = 0; i < x; i++){
        ms[i+1] += ms[i];  
    }
    int t;
    cin >> t;
    for(int i = 1; i <= t; i++){
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        int ans = ms[m] - ms[n];
        if(ms[n] != ms[n-1]) ans++;
        cout << "Case #" << i << ": ";
        cout << ans << '\n';
    }
    return 0;
}

Cake

一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食.

Input每行有两个数p和q.
Output输出最少要将蛋糕切成多少块.
Sample Input2 3Sample Output```
4 

```cpp
#include<bits/stdc++.h>
using namespace std; 
int main(){
    ios::sync_with_stdio(0);
    int n,m;
    while(cin >> n >> m){
        cout << m + n - __gcd(n,m) << '\n'; 
    }
    return 0;
}