megaprime-numbers.cpp

#include <bits/stdc++.h>

using namespace std;

long mulmod(long a, long b, long c){
    long x = 0, y = a%c;
    while(b){
        if(b&1){
            x += y;
            if(x >= c) x -= c;
        }
        y = y * 2;
        if(y >= c) y -= c;
        b >>= 1;
    }
    return x;
}

long BigMod(long a, long b, long mod){
    if(b == 0) return 1;
    long x = BigMod(a, b >> 1, mod);
    x = mulmod(x,x,mod);
    if(b&1)
        x = mulmod(x,a,mod);
    return x;
}

int miller_rabin(long n, int itr = 3){
    if(n < 2) return 0;
    else if(n == 2) return 1;
    if(n%2 == 0) return 0;
    long d = n - 1;
    while(d%2 == 0)
        d /= 2;
    while(itr--){
        long rnd = rand() % (n - 2) + 2;
        long temp = d;
        long x = BigMod(rnd, temp, n);
        while(temp != (n - 1) && x!=1 && x!=(n-1) )
        {
            temp *= 2;
            x = mulmod(x,x,n);
        }
        if(x != (n - 1) && temp%2 == 0)
            return false;
    }
    return true;
}

long next(long x) {
    if (x == 0) return 0;
    long d = x / 10;
    long d1 = next(d + (x % 10 > 7 ? 1 : 0));
    if (d != d1) return 10 * d1 + 2;
    return d1 * 10 + (x % 10 <= 2 ? 2 : x % 10 <= 3 ? 3 : x % 10 <= 5 ? 5 : 7);
}

int main(){
    long first;
    long last;
    cin >> first >> last;
    int count = 0;
    for (long i = next(first); i<=last; i=next(i+1)) if (miller_rabin(i)) count++;
    cout << count;
    return 0;
}