【求】庞果网 幸运数算法解决方案

【求】庞果网 幸运数算法
原题型在庞果网上的挑战里，这个题尝试做了下也看了网友的各种解法都不满足3秒

期待看下高人的实现算法，有没有人在这里分享一下，谢谢！


------解决思路----------------------
从网上找的大神代码,我也看不太懂
只是大致使用动态规划算法,希望哪位可以解释其中的原理

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define S_MAX 81
#define SS_MAX 729
#define PRIME_SIZE SS_MAX
void init_prime(int prime []){
    prime[0]=prime[1]=0;
    for(int i=2;i<PRIME_SIZE;++i){
        prime[i]=1;
    }
    for(int i=2;i<PRIME_SIZE;++i){
        for(int j=2;i*j<PRIME_SIZE;++j){
            prime[i*j]=0;
        }
    }
}

void luckall(int cache[10][S_MAX][SS_MAX], int prime []){
    memset(cache,0,10*S_MAX*SS_MAX*4);
    
    for(int s=0;s<S_MAX;s++){
       for(int ss=0;ss<SS_MAX;++ss){
           cache[0][s][ss] = prime[s] && prime[ss];
       }
    }
    
    for(int i=1;i<9;++i){
        for(int s=0;s<S_MAX;++s){
            for(int ss=0;ss<SS_MAX;++ss){
                for(int j=0;j<10;++j){
                    if(s+j<S_MAX && ss+j*j<SS_MAX)
                    cache[i][s][ss] += cache[i-1][s+j][ss+j*j];
                }
            }
        }
    }

    int i = 9,s=0,ss=0;
    for(int j=0;j<10;++j){
        if(s+j<S_MAX && ss+j*j<SS_MAX)
        cache[i][s][ss] += cache[i-1][s+j][ss+j*j];
    }
}

int lucky(int n, int cache[10][S_MAX][SS_MAX]){
    int digits [10];
    memset(digits,0,10*sizeof(int));
    int i =0;
    for(;n>0;n/=10){
        digits[i++]=n%10;
    }
    int dc = --i, s=0, ss=0, r = 0;
    for(;i>=0;--i){
        int d = digits[i];
        for(int j=0;j<d;++j){
            r += cache[i][s+j][ss+j*j];
        }
        s += d;
        ss += d*d;
    }
    return r;
}

int main(int argc, char * argv[]){
    int prime[PRIME_SIZE];
    int cache[10][S_MAX][SS_MAX];
    init_prime(prime);
    luckall(cache,prime);
    printf("Precalc finished, input x and y, 1<=x<=y<=1E9:\n");
    int x,y;
    scanf("%d",&x);
    scanf("%d",&y);
    printf("%d\n",lucky(y+1,cache)-lucky(x,cache));
    return 0;
}

------解决思路----------------------
兄弟，我来打酱油，有木有分整点来。