Алгоритм поиска счастливых чисел

Question

Я сталкивался с этим вопросом. Число называется счастливым, если сумма его цифр, а также сумма квадратов его цифр - простое число. Сколько чисел между А и В счастливое? 1 <= A <= B <= 10 <sup>18 . Я пробовал это.

• Сначала я сгенерировал все возможные простые числа от 1 до числа, которое могло бы быть получено суммированием квадратов (81 * 18 = 1458).
  
  
• Я прочитал в A и B, чтобы узнать максимальное число, которое может быть сгенерировано суммированием цифр. Если B - двузначное число (максимальное число - 18, сгенерированное 99).
  
  
• Для каждого простого числа от 1 до максимального числа. Я применил алгоритм целочисленного разбиения.
  
  
• Для каждого возможного разбиения я проверял, образует ли их сумма квадратов их цифр простое число. Если так, то возможные перестановки этого раздела генерируются, и если они лежат в диапазоне, они являются счастливыми числами.
  

---

Это реализация:

#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include <stdlib.h>
#include<string.h>
long long luckynumbers;
int primelist[1500];

int checklucky(long long possible,long long a,long long b){
    int prime =0;
    while(possible>0){
            prime+=pow((possible%10),(float)2);
            possible/=10;
    }
        if(primelist[prime]) return 1;
        else return 0;
}
long long getmax(int numdigits){
        if(numdigits == 0) return 1; 
        long long maxnum =10;
             while(numdigits>1){
                        maxnum = maxnum *10;
                        numdigits-=1;
             }
         return maxnum; 

}
void permuteandcheck(char *topermute,int d,long long a,long long b,int digits){
    if(d == strlen(topermute)){
            long long possible=atoll(topermute);
            if(possible >= getmax(strlen(topermute)-1)){  // to skip the case of getting already read numbers like 21 and 021(permuted-210

                if(possible >= a && possible <= b){

                    luckynumbers++;
                }
            }
    }
    else{
        char lastswap ='\0';
        int i;
        char temp;
        for(i=d;i<strlen(topermute);i++){
            if(lastswap == topermute[i])
                continue;
            else
                lastswap = topermute[i];
            temp = topermute[d];
            topermute[d] = topermute[i];
            topermute[i] = temp;

            permuteandcheck(topermute,d+1,a,b,digits);

            temp = topermute[d];
            topermute[d] = topermute[i];
            topermute[i] = temp;
        }

    }

}


void findlucky(long long possible,long long a,long long b,int digits){
    int i =0;
    if(checklucky(possible,a,b)){
        char topermute[18];
        sprintf(topermute,"%lld",possible);
        permuteandcheck(topermute,0,a,b,digits);
    }
}


void  partitiongenerator(int k,int n,int numdigits,long long  possible,long long a,long long b,int digits){
    if(k > n || numdigits > digits-1 || k > 9) return;
    if(k == n){

        possible+=(k*getmax(numdigits));

        findlucky(possible,a,b,digits);
        return;
    }
    partitiongenerator(k,n-k,numdigits+1,(possible + k*getmax(numdigits)),a,b,digits);
    partitiongenerator(k+1,n,numdigits,possible,a,b,digits);

}


void calcluckynumbers(long long a,long long b){
    int i;
    int numdigits = 0;
    long long temp = b;
    while(temp > 0){
        numdigits++;
        temp/=10;
    }

    long long maxnum =getmax(numdigits)-1;
    int maxprime=0,minprime =0;
    temp = maxnum;
    while(temp>0){
        maxprime+=(temp%10);
        temp/=10;
    }
    int start = 2;
    for(;start <= maxprime ;start++){
            if(primelist[start]) {
                partitiongenerator(0,start,0,0,a,b,numdigits);
            }
    }   

}   
void generateprime(){
    int i = 0;
    for(i=0;i<1500;i++)
        primelist[i] = 1;
    primelist[0] = 0;
    primelist[1] = 0;
    int candidate = 2;
    int topCandidate = 1499;
    int thisFactor = 2;
    while(thisFactor * thisFactor <= topCandidate){
        int  mark = thisFactor + thisFactor;
        while(mark <= topCandidate){
            *(primelist + mark) = 0;
            mark += thisFactor;
        }
        thisFactor++;
        while(thisFactor <= topCandidate && *(primelist+thisFactor) == 0) thisFactor++;
    }

}
int main(){
        char input[100];
        int cases=0,casedone=0;
    long long a,b;
    generateprime();
        fscanf(stdin,"%d",&cases);
        while(casedone < cases){
        luckynumbers = 0;
                fscanf(stdin,"%lld %lld",&a,&b);
        int i =0;
               calcluckynumbers(a,b);
                casedone++;
        }

}

---

Алгоритм слишком медленный. Я думаю, что ответ может быть найден на основе свойства чисел. Пожалуйста, поделитесь своими мыслями. Спасибо.

Answer 1

Отличное решение OleGG, но ваш код не оптимизирован.Я внес следующие изменения в ваш код:

1. Не требуется проходить через 9 * 9 * i для k в функции count_lucky, потому что для 10000 случаев он будет выполняться столько раз,вместо этого я уменьшил это значение через начало и конец.

2. я использовал массив ans для хранения промежуточных результатов.Это может показаться немного, но более 10000 случаев - это основной фактор, который сокращает время.

Я протестировал этот код, и он прошел все тестовые случаи.Вот модифицированный код:

    #include <stdio.h>

    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;

}

Объяснение:

gen_primes () и gen_table () в значительной степени говорят сами за себя.

count_lucky () работает следующим образом:

разделить число в split_max [], просто сохранив однозначное число для единиц, десятков, сотен и т. Д.Идея такова: предположим, что split_map [2] = 7, поэтому нам нужно вычислить результат для

1 в позиции сотен и всех от 00 до 99.

2 в позиции сотен и всех от 00 до 99.

..

7 в сотнях позиций и все от 00 до 99.

это фактически делается (в цикле l) с точки зрения суммы цифр и суммы квадратов цифр, которые были предварительно рассчитаны.для этого примера: сумма будет варьироваться от 0 до 9 * i, а сумма квадратов будет варьироваться от 0 до 9 * 9 * i ... это делается в циклах j и k.Это повторяется для всех длин в цикле i

Это была идея OleGG.

Для оптимизации рассматривается следующее:

1. его бесполезно запускатьсумма квадратов от 0 до 9 * 9 * i, так как для конкретных сумм цифр она не будет идти до полного диапазона.Например, если i = 3, а сумма равна 5, сумма квадратов не будет меняться от 0 до 9 * 9 * 3.Эта часть сохраняется в массивах start [] и end [] с использованием предварительно вычисленных значений.

2. значение для определенного количества цифр и конкретной цифры в наиболее значимой позиции числа и до конкретной суммы и до конкретной суммы квадрата, сохраненного для запоминания.Это слишком долго, но все еще около 45 МБ.Я считаю, что это может быть дополнительно оптимизировано.

Answer 2

Вы должны использовать DP для этой задачи.Вот мое решение:

#include <stdio.h>

const int MAX_LENGTH = 18;
const int MAX_SUM = 162;
const int MAX_SQUARE_SUM = 1458;
int primes[1459];
long long dyn_table[19][163][1459];

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];
                }
            }
        }
    }
}

long long count_lucky (long long max) {
            long long result = 0;
    int len = 0;
    int split_max[MAX_LENGTH];
    while (max) {
        split_max[len] = max % 10;
        max /= 10;
        ++len;
    }
    int sum = 0;
    int sq_sum = 0;
    for (int i = len-1; i >= 0; --i) {
        long long step_result = 0;
        for (int l = 0; l < split_max[i]; ++l) {
            for (int j = 0; j <= 9 * i; ++j) {
                for (int k = 0; k <= 9 * 9 * i; ++k) {
                    if (primes[j + l + sum] && primes[k + l*l + sq_sum]) {
                        step_result += dyn_table[i][j][k];
                    }
                }
            }
        }
        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();

    int cases = 0;
    scanf("%d", &cases);
    for (int i = 0; i < cases; ++i) {
        long long a, b;
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", count_lucky(b) - count_lucky(a-1));
    }
    return 0;
}

Краткое объяснение:

• Я вычисляю все простые числа до 9 * 9 * MAX_LENGTH, используя метод Eratosthenes;
• Позжеиспользуя DP, я создаю таблицу dyn_table, где значение X в dyn_table [i] [j] [k] означает, что у нас есть ровно X чиселдлина i с суммой цифр, равной j и суммой его квадратов, равной k
• Тогда мы можем легко посчитать количество счастливых чиселот 1 до 999 ... 999 ( len times of 9).Для этого мы просто суммируем все dyn_table [len] [j] [k] , где оба j и k являются простыми числами.
• Toрассчитать количество счастливых чисел от 1 до случайного X мы разбиваем интервал от 1 до X на интервалы с длиной, равной 10 ^ K (см. функцию * count_lucky *).
• И наш последний шаг - вычитание count_lucky (a-1) (потому что мы включаем a в наш интервал) из count_lucky (b).

Это все.Работа по предварительному вычислению для O (log (MAX_NUMBER) ^ 3), каждый шаг также имеет эту сложность.

Я проверил свое решение по сравнению с линейным прямым и результаты были равны

Answer 3

Вместо того, чтобы перечислять пространство чисел, перечисляйте различные «подписи» чисел, которым повезло.и затем распечатайте все их комбинации.

Это можно сделать с помощью простого обратного отслеживания:

#define _GNU_SOURCE
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#define bitsizeof(e)   (CHAR_BIT * sizeof(e))
#define countof(e)     (sizeof(e) / sizeof((e)[0]))
#define BITMASK_NTH(type_t, n) ( ((type_t)1) << ((n) & (bitsizeof(type_t) - 1)))
#define OP_BIT(bits, n, shift, op) \
    ((bits)[(unsigned)(n) / (shift)] op BITMASK_NTH(typeof(*(bits)), n))
#define TST_BIT(bits, n)    OP_BIT(bits, n, bitsizeof(*(bits)), &  )
#define SET_BIT(bits, n)    (void)OP_BIT(bits, n, bitsizeof(*(bits)), |= )

/* fast is_prime {{{ */

static uint32_t primes_below_1M[(1U << 20) / bitsizeof(uint32_t)];

static void compute_primes_below_1M(void)
{
    SET_BIT(primes_below_1M, 0);
    SET_BIT(primes_below_1M, 1);
    for (uint32_t i = 2; i < bitsizeof(primes_below_1M); i++) {
        if (TST_BIT(primes_below_1M, i))
            continue;
        for (uint32_t j = i * 2; j < bitsizeof(primes_below_1M); j += i) {
            SET_BIT(primes_below_1M, j);
        }
    }
}

static bool is_prime(uint64_t n)
{
    assert (n < bitsizeof(primes_below_1M));
    return !TST_BIT(primes_below_1M, n);
}

/* }}} */

static uint32_t prime_checks, found;

static char     sig[10];
static uint32_t sum, square_sum;

static void backtrack(int startdigit, int ndigits, int maxdigit)
{
    ndigits++;

    for (int i = startdigit; i <= maxdigit; i++) {
        sig[i]++;
        sum        += i;
        square_sum += i * i;
        prime_checks++;
        if (is_prime(sum) && is_prime(square_sum)) {
                found++;
        }
        if (ndigits < 18)
            backtrack(0, ndigits, i);
        sig[i]--;
        sum        -= i;
        square_sum -= i * i;
    }
}

int main(void)
{
    compute_primes_below_1M();
    backtrack(1, 0, 9);

    printf("did %d signature checks, found %d lucky signatures\n",
           prime_checks, found);
    return 0;
}

Когда я его запускаю, он делает:

$ time ./lucky
did 13123091 signature checks, found 933553 lucky signatures
./lucky  0.20s user 0.00s system 99% cpu 0.201 total

Вместоиз found ++ вы хотите сгенерировать все различные комбинации цифр, которые вы можете построить с этим числом.Я также предварительно вычисляю первые 1M простых чисел.

Я не проверял, является ли код на 100% правильным, возможно, вам придется немного его отладить.Но здесь есть приблизительная идея, и я могу генерировать всю счастливую перестановку ниже 0,2 с (даже без ошибок она не должна быть более чем в два раза медленнее).

И, конечно, вы хотите сгенерироватьперестановки, которые проверяют A <= B. Вы можете игнорировать создание разделов, которые имеют больше цифр, чем B, или меньше, чем A.В любом случае, вы можете улучшить мою общую идею здесь. </p>

(Примечание: реклама в начале состоит в том, что я вырезал и вставлял код, написанный для проекта euler, поэтому очень быстрый is_prime, который работает для N <= 1M;)) </p>

Answer 4

Для тех, кто еще не знал, это проблема на сайте InterviewStreet.com (и, на мой взгляд, самая сложная там).Мой подход начался примерно так (и был вдохновлен) ниже OleGG.Однако после создания первой таблицы [19] [163] [1459], которую он сделал (которую я назову table1), я пошел в несколько ином направлении.Я создал вторую таблицу рваной длины [19] [x] [3] (table2), где x - количество пар уникальных сумм для соответствующего количества цифр.А для третьего измерения таблицы длиной 3, 1-й элемент - это количество уникальных «пар сумм» со значениями sum и squareSum, которые содержатся во 2-м и 3-м элементах.

Например:

//pseudocode

table2[1] = new long[10][3]
table2[1] = {{1, 0, 0}, {1, 1, 1}, {1, 2, 4},
             {1, 3, 9}, {1, 4, 16}, {1, 5, 25},
             {1, 6, 36}, {1, 7, 49}, {1, 8, 64}, {1, 9, 81}}

table2[2] = new long[55][3]
table2[3] = new long[204][3]
table2[4] = new long[518][3]
    .
    .
    .
    .
table2[17] = new long[15552][3]
table2[18] = new long[17547][3]

Числа, имеющиеся у меня для длины второго измерения массива (10, 55, 204, 518, ..., 15552, 17547), можно проверить с помощью запроса table1, и аналогичным образом table2 можетбыть заселённымТеперь, используя table2, мы можем решать большие «счастливые» запросы намного быстрее, чем опубликованный метод OleGG, хотя все еще использую тот же процесс «split», что и он.Например, если вам нужно найти счастливых (00000-54321) (т. Е. Счастливых чисел между 0 и 54321), он разбивается на сумму следующих 5 строк:

lucky(00000-54321) = {
    lucky(00000-49999) +
    lucky(50000-53999) +
    lucky(54000-54299) +
    lucky(54300-53319) +
    lucky(54320-54321)
}

Что разбивает дальше:

lucky(00000-49999) = {
    lucky(00000-09999) +
    lucky(10000-19999) +
    lucky(20000-29999) +
    lucky(30000-39999) +
    lucky(40000-49999)
}
    .
    .
lucky(54000-54299) = {
    lucky(54000-54099) +
    lucky(54100-54199) +
    lucky(54200-54299)
}
    .
    .
    .
    etc

Каждое из этих значений может быть легко получено с помощью запроса table2.Например, удача (40000-49999) определяется добавлением 4 и 16 ко 2-му и 3-му элементам таблицы третьего измерения2:

sum = 0
for (i = 0; i < 518; i++)
    if (isPrime[table2[4][i][1] + 4] && isPrime[table2[4][i][2] + 4*4])
        sum += table2[4][i][0]
return sum

Или для удачи (54200-54299):

sum = 0
for (i = 0; i < 55; i++)
    if (isPrime[table2[2][i][1] + (5+4+2)]
    && isPrime[table2[2][i][2] + (5*5+4*4+2*2)])
        sum += table2[2][i][0]
return sum

Теперь решение OleGG работало значительно быстрее, чем все, что я пробовал до этого, но с моими модификациями, описанными выше, оно работает даже лучше, чем раньше (примерно в 100 раз для большого набора тестов).Тем не менее, он все еще недостаточно быстр для слепых тестов, представленных на InterviewStreet.С помощью некоторого умного взлома я смог определить, что в настоящее время я работаю примерно в 20 раз медленнее, чтобы завершить тестовый набор за отведенное времяОднако я не могу найти дальнейших оптимизаций.Очевидно, что самая большая временная задержка - это итерация по второму измерению таблицы 2, и единственный способ избежать этого - это табулировать результаты этих сумм.Однако существует слишком много возможностей для того, чтобы вычислить их все за заданное время (5 секунд) или сохранить их все в заданном пространстве (256 МБ).Например, приведенный выше цикл lucky (54200-54299) может быть предварительно вычислен и сохранен как одно значение, но если бы это было так, нам также нужно было бы предварительно вычислить lucky (123000200-123000299) и lucky (99999200-99999299)) и т. д. и т. д. Я сделал математику, и слишком много вычислений для предварительного вычисления.

Answer 5

Я только что решил эту проблему.

Это просто проблема динамического программирования. Возьмите DP[n](sum-square_sum) в качестве функции DP, а DP[n](sum-square_sum) - это число всех чисел, цифры которых меньше или равны n, при этом сумма и квадратная сумма цифр номера соответственно представлены суммами и квадратными суммами. Например:

DP[1](1-1) = 1      # only 1 satisfies the condition                        
DP[2](1-1) = 2      # both 1 and 10 satisfies the condition                        
DP[3](1-1） = 3      # 1 10 100
DP[3](2-4） = 3      # 11 110 101

Поскольку мы можем легко определить первое состояние DP DP [1] [..] [..], оно равно:

(0-0) => 1     (1-1) => 1    (2-4) => 1     (3-9) => 1     (4-16) => 1    
(5-25) => 1    (6-36) => 1   (7-49) => 1    (8-64) => 1    (9-81) => 1

тогда мы можем вывести DP [1] из DP [1], а затем DP [3] ... DP [18] вышеприведенный вывод сделан из того факта, что каждый раз, когда n увеличивается на 1, например, от DP [1] до DP [2], мы получаем новую цифру (0..9) и набор (sum, square_sum ) пара (т.е. DP [n]) должна быть обновлена.

Наконец, мы можем пройти через набор DP [18] и посчитать числа счастливчиков.

Ну, а как насчет временной и пространственной сложности алгоритма, описанного выше? Как мы знаем sum <= 18 * 9 = 162, square_sum <= 18 * 9 * 9 = 1458, поэтому набор (sum, square_sum) пары (т. е. DP [n]) очень маленький, менее 162 * 1458 = 236196, фактически он намного меньше, чем 236196; Дело в том, что моя программа ruby, считающая все счастливые числа от 0 до 10 ^ 18, заканчивается менее чем за 1 с. </p>

ruby lucky_numbers.rb  0.55s user 0.00s system 99% cpu 0.556 total

и я тестирую свою программу, написав тестовую функцию с использованием алгоритма грубой силы, и она подходит для чисел меньше 10 ^ 7.

Answer 6

Я пытался найти решение, используя метод перечисления Пьера, но никогда не придумал достаточно быстрый способ подсчета перестановок.Метод подсчета OleGG очень умный, и пиратская оптимизация необходима, чтобы сделать его достаточно быстрым.Я придумал одно незначительное улучшение и один обходной путь для серьезной проблемы.

Во-первых, улучшение: вам не нужно перебирать все суммы и квадраты один за другим, проверяя простые числа в пиратском j иk петель.У вас есть (или вы можете легко сгенерировать) список простых чисел.Если вы используете другие переменные, чтобы выяснить, какие простые числа находятся в диапазоне, вы можете просто просмотреть список подходящих простых чисел для суммы и квадрата.Полезно использовать массив простых чисел и таблицу поиска, чтобы быстро определить, по какому индексу находится простое число = = число.Тем не менее, это, вероятно, лишь незначительное улучшение.

Большая проблема связана с массивом кеша и пиратского кэша.Это не 45 МБ, как заявлено;с 64-битными записями это что-то вроде 364MB.Это вне (текущих) допустимых пределов памяти для C и Java.Его можно уменьшить до 37 МБ, избавившись от измерения «l», которое не является необходимым и в любом случае снижает производительность кэша.Вы действительно заинтересованы в подсчете кэширования для l + sum и l * l + squaresum, а не для l, sum и squaresum по отдельности.

Answer 7

Сначала я хотел бы добавить, что счастливое число может быть вычислено ситом, объяснение сита можно найти здесь: http://en.wikipedia.org/wiki/Lucky_number

, так что вы можете улучшить скорость решения с помощью сита, чтобыопределить цифры,

Answer 8

Иногда самое быстрое решение невероятно просто:

uint8_t precomputedBitField[] = {
    ...
};

bool is_lucky(int number) {
    return precomputedBitField[number >> 8] & (1 << (number & 7));
}

Просто измените существующий код, чтобы сгенерировать "precomputedBitField".

Если вас беспокоит размер, для покрытия всех чисел от 0 до 999 это будет стоить вам всего 125 байтов, поэтому этот метод, вероятно, будет меньше (и намного быстрее), чем любая другая альтернатива.

Answer 9

Я не тщательно проанализировал ваше текущее решение, но это может улучшить его:

Так как порядок цифр не имеет значения, вам нужно пройти через все возможные комбинации цифр 0-9 длины 1до 18, отслеживая сумму цифр и их квадратов и добавляя по одной цифре за раз, используя результат предыдущего вычисления.

Так что, если вы знаете, что для 12 сумма цифр равна 3, а для квадратов - 5посмотрите на числа 120, 121, 122 и т. д. и рассчитайте для них суммы тривиально из 3 и 5 для 12.

Answer 10

Исходя из требований, вы можете сделать это по-разному. Если бы я делал это, я бы вычислял простые числа, используя «Сито Эратосфена» в требуемом диапазоне (от A до (9 * 2) * B. длина), кэшировал их (опять же, в зависимости от вашей настройки, вы можете использовать в -память или кэш диска) и использовать его для следующего запуска.

Я только что написал быстрое решение (Java), как показано ниже ( ПРИМЕЧАНИЕ : Целочисленное переполнение не проверяется. Просто быстрый пример. Кроме того, мой код не оптимизирован.):

import java.util.ArrayList;
import java.util.Arrays;

public class LuckyNumbers {
    public static void main(String[] args) {
        int a = 0, b = 1000;
        LuckyNumbers luckyNums = new LuckyNumbers();
        ArrayList<Integer> luckyList = luckyNums.findLuckyNums(a, b);
        System.out.println(luckyList);
    }

    private ArrayList<Integer> findLuckyNums(int a, int b) {
        ArrayList<Integer> luckyList = new ArrayList<Integer>();
        int size = ("" + b).length();        
        int maxNum = 81 * 4; //9*2*b.length() - 9 is used, coz it's the max digit
        System.out.println("Size : " + size + " MaxNum : " + maxNum);
        boolean[] primeArray = sieve(maxNum);

        for(int i=a;i<=b;i++) {
            String num = "" + i;
            int sumDigits = 0;
            int sumSquareDigits = 0;

            for(int j=0;j<num.length();j++) {
                int digit = Integer.valueOf("" + num.charAt(j));
                sumDigits += digit;
                sumSquareDigits += Math.pow(digit, 2);
            }

            if(primeArray[sumDigits] && primeArray[sumSquareDigits]) {
                luckyList.add(i);
            }
        }

        return luckyList;
    }

    private boolean[] sieve(int n) {
        boolean[] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        prime[0] = false;
        prime[1] = false;
        int m = (int) Math.sqrt(n);

        for (int i = 2; i <= m; i++) {
            if (prime[i]) {
                for (int k = i * i; k <= n; k += i) {
                    prime[k] = false;
                }
            }
        }

        return prime;
    }
}

И вывод был:

[11, 12, 14, 16, 21, 23, 25, 32, 38, 41, 49, 52, 56, 58, 61, 65, 83, 85, 94, 101, 102, 104, 106, 110, 111, 113, 119, 120, 131, 133, 137, 140, 146, 160, 164, 166, 173, 179, 191, 197, 199, 201, 203, 205, 210, 223, 229, 230, 232, 250, 289, 292, 298, 302, 308, 311, 313, 317, 320, 322, 331, 335, 337, 344, 346, 353, 355, 364, 368, 371, 373, 377, 379, 380, 386, 388, 397, 401, 409, 410, 416, 434, 436, 443, 449, 461, 463, 467, 476, 490, 494, 502, 506, 508, 520, 533, 535, 553, 559, 560, 566, 580, 595, 601, 605, 610, 614, 616, 634, 638, 641, 643, 647, 650, 656, 661, 665, 674, 683, 689, 698, 713, 719, 731, 733, 737, 739, 746, 764, 773, 779, 791, 793, 797, 803, 805, 829, 830, 836, 838, 850, 863, 869, 883, 892, 896, 904, 911, 917, 919, 922, 928, 937, 940, 944, 955, 968, 971, 973, 977, 982, 986, 991]