UVa 12065 - Permutation Primes (UVALive 3017, Regionals 2004 >> Asia - Dhaka)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive / spoj), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 1111111

int digit[10], digitLength;
void makeDigit(int n)
{
    digitLength=0;
    while(n)
    {
        digit[digitLength++]=n%10;
        n/=10;
    }
    sort(digit, digit+digitLength);
return;
}

vector<int>prime;
bool status[MX+2];
void PrimeGenerate(int n)
{
    int sq=sqrt(n);
    for(int i=3; i<=sq; i+=2)
    {
        if(!status[i])
            for(int j=i*i; j<=n; j+=(i<<1))
                status[j]=true;
    }
    
    status[0]=status[1]=true;
    for(int i=4;i<=n;i+=2) status[i]=true;
    
    /*prime.push_back(2);
    for(int i=3; i<=n; i+=2)
        if(!stats[i])
            prime.push_back(i);*/
return;
}

int permute(int n)
{
    int num, p;
    makeDigit(n);
    do{
        num=0;
        for(int i=0;i<digitLength;i++)
            num=num*10+digit[i];
        p=abs(n-num)/9;
        if(p<MX && !status[p]) return 1;
    }while(next_permutation(digit, digit+digitLength));
return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int kk=1, tc, n, m, p, q;
    string s;
    PrimeGenerate(MX);
    cin>>tc;
    while(tc--)
    {
        cin>>p>>q;
        if(p>q) swap(p, q);
        int cnt=0;
        for(int i=p;i<=q;i++)
        {
            if(permute(i))
                cnt++;
        }

        cout<<"Case "<<kk++<<": "<< cnt <<"\n";
    }

    return 0;
}