why 23 in between 21 and 25 is not lucky number,

as we are getting digit sum 5, and sum of square of digits are 13.

This problem is obscenely difficult, and I spent days researching just to get fairly close to the correct solution, then I spent days more tweaking my approach to conform to the extra constraints created by the problem itself. In order to complete this in a reasonable time, you have to dig into number theory by realizing that, at least for a=1 to b=(some number of consecutive 9's), the problem resembles a permutation problem (since we take the sums/squares of these numbers, the question becomes 'how many combinations of k digits result in a prime number between 1 and 999999999999999999 when (summed) or (squared)?' and 'how can you exclude permutations that are less than a, and greater than b?'

Honestly, I'm still not even finished trying to make the damn thing work, I just know the approach WILL work, once I've debugged everything.

can anyone let me know how i can optimize it further

!/bin/python3

import math import os import random import re import sys

#

Complete the 'luckyNumbers' function below.

#

The function is expected to return a LONG_INTEGER.

The function accepts following parameters:

1. LONG_INTEGER a

2. LONG_INTEGER b

#

def luckyNumbers(a, b): # Write your code here temp = 0 total = 0

for i in range(a,b+1):
    temp = i
    totalsum = 0
    totalsumsq = 0
    while temp != 0:
        digit = temp % 10
        temp = temp // 10
        totalsum = totalsum + digit
        totalsumsq = totalsumsq + (digit**2)

    def isprime(n):
        if n > 1:
            for k in range(2,n):
                if (n % k) == 0:
                    return False
            return True
        else:
            return False 


    isprime(totalsum)
    isprime(totalsumsq)

    if isprime(totalsum) and isprime(totalsumsq):
        total = total + 1

return total        

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

t = int(input().strip())

for t_itr in range(t):
    first_multiple_input = input().rstrip().split()

    a = int(first_multiple_input[0])

    b = int(first_multiple_input[1])

    result = luckyNumbers(a, b)

    fptr.write(str(result) + '\n')

fptr.close()

Can someone tell me the error?

include

using namespace std; int sumofd(long long int a) { long long int s=0; while(a!=0) { s=s+a%10; a=a/10; }
return s; } int sumofsq(long long int a) { if(a==0) return 0; else return ((a%10)*(a%10)+sumofsq(a/10));

} int main() { int t; cin>>t; while(t--) { long long int a,b,ans,ans2,c=0; cin>>a; cin>>b; for(long long int i=a ; i<=b ; i++) { ans=sumofd(a); ans2=sumofsq(a); for(long long int j=2 ; j<=ans/2 ; ++j) { if(ans%j==0) c++; } } cout<

Easy C solution:

include

const int MAX_LENGTH = 18;
const int MAX_SUM = 162;
const int MAX_SQUARE_SUM = 1458;
int primes[1460];
unsigned long long dyn_table[20][164][1460];
//changed here.......1
unsigned long long ans[19][10][164][1460];  //about 45 MB

int start[19][163];
int end[19][163];
//upto here.........1
void gen_primes() {
    for (int i = 0; i <= MAX_SQUARE_SUM; ++i) {
        primes[i] = 1;
    }
    primes[0] = primes[1] = 0;

    for (int i = 2; i * i <= MAX_SQUARE_SUM; ++i) {
        if (!primes[i]) {
            continue;
        }
        for (int j = 2; i * j <= MAX_SQUARE_SUM; ++j) {
            primes[i*j] = 0;
        }
    }
}

void gen_table() {
    for (int i = 0; i <= MAX_LENGTH; ++i) {
        for (int j = 0; j <= MAX_SUM; ++j) {
            for (int k = 0; k <= MAX_SQUARE_SUM; ++k) {
                dyn_table[i][j][k] = 0;
            }
        }
    }
    dyn_table[0][0][0] = 1;

    for (int i = 0; i < MAX_LENGTH; ++i) {
        for (int j = 0; j <= 9 * i; ++j) {
            for (int k = 0; k <= 9 * 9 * i; ++k) {
                for (int l = 0; l < 10; ++l) {
                    dyn_table[i + 1][j + l][k + l*l] += dyn_table[i][j][k];
                }
            }
        }
    }
}

unsigned long long count_lucky (unsigned long long maxp) {
    unsigned long long result = 0;
    int len = 0;
    int split_max[MAX_LENGTH];
    while (maxp) {
        split_max[len] = maxp % 10;
        maxp /= 10;
        ++len;
    }
    int sum = 0;
    int sq_sum = 0;
    unsigned long long step_result;
    unsigned long long step_;
    for (int i = len-1; i >= 0; --i) {
        step_result = 0;
        int x1 = 9*i;
        for (int l = 0; l < split_max[i]; ++l) {
//changed here........2
            step_ = 0;
            if(ans[i][l][sum][sq_sum]!=0)
                {
                    step_result +=ans[i][l][sum][sq_sum];
                    continue;
                }
            int y = l + sum;
            int x = l*l + sq_sum;
            for (int j = 0; j <= x1; ++j) {
                if(primes[j + y])
                    for (int k=start[i][j]; k<=end[i][j]; ++k) {
                        if (primes[k + x]) {
                            step_result += dyn_table[i][j][k];
                            step_+=dyn_table[i][j][k];
                        }
                }

            }
             ans[i][l][sum][sq_sum] = step_;
//upto here...............2
        }
        result += step_result;
        sum += split_max[i];
        sq_sum += split_max[i] * split_max[i];
    }

    if (primes[sum] && primes[sq_sum]) {
        ++result;
    }

    return result;
}

int main(int argc, char** argv) {
    gen_primes();
    gen_table();

//changed here..........3
    for(int i=0;i<=18;i++)
        for(int j=0;j<=163;j++)
            {
                for(int k=0;k<=1458;k++)
                        if(dyn_table[i][j][k]!=0ll)
                            {
                                start[i][j] = k;
                                break;                               
                            }

                for(int k=1460;k>=0;k--)
                        if(dyn_table[i][j][k]!=0ll)
                            {
                                end[i][j]=k;
                                break;                               
                            }
            }
//upto here..........3
    int cases = 0;
    scanf("%d",&cases);
    for (int i = 0; i < cases; ++i) {
        unsigned long long a, b;

        scanf("%lld %lld", &a, &b);
//changed here......4
        if(b == 1000000000000000000ll)
            b--;
//upto here.........4
        printf("%lld\n", count_lucky(b) - count_lucky(a-1));
    }
    return 0;

}