Wonderprime Brands

Description

The cows are forever competing to see who has the best brand. The latest rage is brands that are ‘Wonderprimes’. You probably already know that a brand consists of a sequence of digits that does not begin with 0; brands actually look a lot like positive integers.
A wonderprime is a number that can be partitioned into two prime numbers, each of which has at least D digits and, of course, doesn’t start with 0. When D=2, the number 11329 is a wonderprime (since it connects 113 and 29, both of which are prime).
Only a few of the cows have wonderprime brands, but they all want one. Your job is to find the first wonderprime greater than or equal to a supplied integer N (1 <= N <= 2,000,000,000). No integer greater than 2,000,000,000 will be required.

Input

Line 1: Two space-separated integers: D and N

Output

Line 1: A line that contains the first wonderprime no smaller than N.

Example Input

2 11328

Example Output

11329

Solution

纯枚举

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll d, n, mod(10), minimum(1);

bool prime(ll x);

bool iskey(ll x);

int main()
{
    scanf("%lld%lld", &d, &n);
    for (ll i = 1; i < d; i++) { mod *= 10; minimum *= 10; }
    if (n < mod * minimum) n = mod * minimum;
    while (!iskey(n)) n++;
    printf("%lld\n", n);;
    
    return 0;
}

bool prime(ll x)
{
    if (x < 2) return false;
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

bool iskey(ll n)
{
    ll x = n / mod, y = n % mod, pow = mod;
    if (n % mod / minimum)
        if (prime(x) && prime(y))
            return true;
    y += x % 10 * pow; x /= 10;
    while (x >= minimum)
    {
        if (y >= pow)
        {
            if (prime(x) && prime(y))
                return true;
        }
        pow *= 10;
        y += x % 10 * pow; x /= 10;
    }
    return false;
}