prime factorization geeksforgeeks
Algoritmo para encontrar números de la suerte (10)
Me encontré con esta pregunta. Un número se llama afortunado si la suma de sus dígitos, así como la suma de los cuadrados de sus dígitos es un número primo. ¿Cuántos números entre A y B son afortunados? 1 <= A <= B <= 10 18 . Intenté esto.
- Primero, generé todos los números primos posibles entre 1 y el número que podría obtenerse sumando los cuadrados (81 * 18 = 1458).
- Leo en A y B averigua el número máximo que podría generarse sumando los dígitos Si B es un número de 2 dígitos (el número máximo es 18 generado por 99).
- Para cada número primo entre 1 y un número máximo. Apliqué algoritmo de partición entera.
- Para cada posible partición, verifiqué si su suma de cuadrados de sus dígitos forma primo. Si es así, se generan las posibles permutaciones de esa partición y si están dentro del rango son números de la suerte.
Esta es la implementación:
#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++;
}
}
El algoritmo es demasiado lento. Creo que la respuesta se puede encontrar en función de la propiedad de los números. Comparta sus pensamientos de forma amable. Gracias.
A veces la solución más rápida es increíblemente simple:
uint8_t precomputedBitField[] = {
...
};
bool is_lucky(int number) {
return precomputedBitField[number >> 8] & (1 << (number & 7));
}
Simplemente modifique su código existente para generar "precomputedBitField".
Si le preocupa el tamaño, para cubrir todos los números del 0 al 999 solo le costará 125 bytes, por lo que este método probablemente será más pequeño (y mucho más rápido) que cualquier otra alternativa.
De acuerdo con los requisitos, puede hacerlo de diferentes maneras. Si lo estuviera haciendo, calcularía los números primos usando ''Tamiz de Eratóstenes'' en el rango requerido (A a (9 * 2) * B.length), los almacené en caché (nuevamente, dependiendo de su configuración, puede usar en -Memoria o caché de disco) y úselo para la próxima ejecución.
Acabo de codificar una solución rápida (Java), como se indica a continuación ( NOTA : no se verifica el desbordamiento de enteros. Solo un ejemplo rápido. Además, mi código no está optimizado.):
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;
}
}
Y la salida fue:
[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, 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, 896, 896, 904, 911, 917, 919 , 922, 928, 937, 940, 944, 955, 968, 971, 973, 977, 982, 986, 991]
Debe utilizar DP para esta tarea. Aquí está mi solución:
#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;
}
Breve explicacion:
- Estoy calculando todos los números primos hasta 9 * 9 * MAX_LENGTH utilizando el método de Eratóstenes;
- Más tarde, usando DP, estoy construyendo la tabla dyn_table donde el valor X en dyn_table [i] [j] [k] significa que tenemos exactamente X números de longitud i con suma de dígitos igual a j y suma de sus cuadrados igual a k
- Luego podemos contar fácilmente la cantidad de números de la suerte del 1 al 999..999 ( len veces de 9). Para esto solo resumimos dyn_table [len] [j] [k] donde j y k son primos.
- Para calcular la cantidad de números de la suerte de 1 a X aleatorio, dividimos el intervalo de 1 a X en intervalos con una longitud igual a 10 ^ K (consulte la función * count_lucky *).
- Y nuestro último paso es restar count_lucky (a-1) (porque estamos incluyendo a en nuestro intervalo) de count_lucky (b).
Eso es todo. El trabajo de precálculo para O (log (MAX_NUMBER) ^ 3), cada paso tiene también esta complejidad.
He probado mi solución contra una lineal directa y los resultados fueron iguales
En lugar de enumerar el espacio de los números, enumere las diferentes "firmas" de los números que tienen suerte. y luego imprimir toda la combinación differnet de esos.
Esto se puede hacer con backtracking trivial:
#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;
}
Cuando lo ejecuto lo hace:
$ time ./lucky
did 13123091 signature checks, found 933553 lucky signatures
./lucky 0.20s user 0.00s system 99% cpu 0.201 total
En lugar de ++ encontrado, desea generar todas las permutaciones distintas de dígitos que puede construir con ese número. También precomputo el primer 1M de números primos de la historia.
No he comprobado si el código es correcto al 100%, puede que tenga que depurarlo un poco. Pero la idea principal está aquí, y puedo generar toda la permutación de la suerte por debajo de 0.2s (incluso sin errores, no debería ser más del doble de lento).
Y, por supuesto, desea generar las permutaciones que verifican que A <= B. Es posible que desee ignorar la generación de particiones que tengan más dígitos que B o menos que A también. De todos modos puedes mejorar mi idea general desde aquí.
(Nota: la publicidad al inicio se debe a que corté y pegué el código que escribí para el proyecto euler, por lo tanto, el muy rápido is_prime que funciona para N <= 1M;))
Estaba tratando de encontrar una solución utilizando el método de enumeración de Pierre, pero nunca se me ocurrió una manera suficientemente rápida de contar las permutaciones. El método de conteo de OleGG es muy inteligente, y las optimizaciones de los piratas son necesarias para que sea lo suficientemente rápido. Se me ocurrió una mejora menor, y una solución a un problema grave.
Primero, la mejora: no tienes que pasar por todas las sumas y los cuadrados una por una para verificar los números primos en los bucles j y k del pirata. Usted tiene (o puede generar fácilmente) una lista de números primos. Si usa las otras variables para determinar qué números primos están dentro del rango, puede pasar por la lista de números primos adecuados para la suma y el cuadrado. Es útil una matriz de números primos y una tabla de búsqueda para determinar rápidamente en qué índice está el número primo> = un número. Sin embargo, esta es probablemente una mejora bastante menor.
El gran problema es con la matriz de caché ans de pirata. No es 45MB como se afirma; Con entradas de 64 bits, es algo así como 364MB. Esto está fuera de los límites de memoria permitidos (actuales) para C y Java. Se puede reducir a 37 MB deshaciéndose de la dimensión "l", que es innecesaria y perjudica el rendimiento del caché de todos modos. Está realmente interesado en el almacenamiento en caché de l + sum y l * l + squaresum, no l, sum y squaresum individualmente.
Excelente solución OleGG, pero tu código no está optimizado. He realizado los siguientes cambios en su código,
No requiere pasar por 9 * 9 * i para k en la función count_lucky, porque para 10000 casos se ejecutaría tantas veces, en lugar de eso, he reducido este valor hasta el inicio y el final.
He utilizado una matriz ans para almacenar resultados intermedios. Puede que no parezca mucho, pero en más de 10000 casos, este es el factor más importante que reduce el tiempo.
He probado este código y pasó todos los casos de prueba. Aquí está el código modificado:
#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;
}
Explicación:
gen_primes () y gen_table () son bastante auto explicativos.
count_lucky () funciona de la siguiente manera:
divida el número en split_max [], simplemente almacene números de un solo dígito para las posiciones de unidades, decenas, centenas, etc. La idea es: supongamos que split_map [2] = 7, por lo que necesitamos calcular el resultado para
1 en posición de centenas y todas de 00 a 99.
2 en posición de centenas y todas de 00 a 99.
. .
7 en posición de centenas y todas de 00 a 99.
esto se hace realmente (en l bucle) en términos de suma de dígitos y suma de cuadrados de dígitos precalcutados. para este ejemplo: la suma variará de 0 a 9 * i y la suma de cuadrados variará de 0 a 9 * 9 * i ... esto se hace en los bucles j y k. Esto se repite para todas las longitudes en i loop
Esta fue la idea de OleGG.
Para la optimización se considera lo siguiente:
es inútil ejecutar la suma de cuadrados de 0 a 9 * 9 * i ya que para sumas particulares de dígitos no iría hasta el rango completo. Como si i = 3 y la suma es igual a 5, la suma del cuadrado no variará de 0 a 9 * 9 * 3. Esta parte se almacena en las matrices de inicio [] y final [] utilizando valores precomputados.
el valor para un número particular de dígitos y un dígito particular en la posición más significativa de número y hasta suma particular y hasta suma particular de cuadrado se almacenan para memorización. Es demasiado largo, pero sigue siendo de unos 45 MB. Creo que esto podría optimizarse aún más.
No he analizado cuidadosamente su solución actual, pero esto podría mejorarla:
Dado que el orden de los dígitos no importa, debe pasar por todas las combinaciones posibles de dígitos 0-9 de longitud 1 a 18, realizar un seguimiento de la suma de dígitos y sus cuadrados y agregar un dígito a la vez, usando el resultado de cálculo.
Entonces, si sabe que para 12 la suma de los dígitos es 3 y la de los cuadrados es 5, mire los números 120, 121, 122 ... etc. y calcule las sumas para ellos de forma trivial a partir del 3 y 5 para 12.
Para aquellos que no lo sabían ya, este es un problema en el sitio web InterviewStreet.com (y en mi opinión, el más difícil allí). Mi enfoque comenzó similar a (y se inspiró en) OleGG a continuación. Sin embargo, después de crear la primera tabla [19] [163] [1459] que hizo (a la que llamaré tabla1), fui en una dirección ligeramente diferente. Creé una segunda tabla de longitud irregular [19] [x] [3] (tabla 2), donde x es el número de pares de suma únicos para el número de dígitos correspondiente. Y para la tercera dimensión de la tabla, con longitud 3, el primer elemento es la cantidad de "pares de suma" únicos con los valores de suma y suma cuadrada que tienen los elementos segundo y tercero.
Por ejemplo:
//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]
Los números que tengo para la longitud de la segunda dimensión de la matriz (10, 55, 204, 518, ..., 15552, 17547) se pueden verificar consultando la tabla 1, y de manera similar se puede completar la tabla 2. Ahora, utilizando table2, podemos resolver grandes consultas "afortunadas" mucho más rápido que el método publicado de OleGG, aunque aún empleamos un proceso de "división" similar como lo hizo él. Por ejemplo, si necesita encontrar afortunado (00000-54321) (es decir, los números de la suerte entre 0 y 54321), se desglosa hasta la suma de las siguientes 5 líneas:
lucky(00000-54321) = {
lucky(00000-49999) +
lucky(50000-53999) +
lucky(54000-54299) +
lucky(54300-53319) +
lucky(54320-54321)
}
Que se descompone aún más:
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
Cada uno de estos valores se puede obtener fácilmente consultando table2. Por ejemplo, la suerte (40000-49999) se encuentra al agregar 4 y 16 a los elementos 2 y 3 de la tabla de la tercera dimensión 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
O para la suerte (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
Ahora, la solución de OleGG funcionó significativamente más rápido que cualquier otra cosa que haya probado hasta entonces, pero con mis modificaciones descritas anteriormente, funciona incluso mejor que antes (en un factor de aproximadamente 100x para un conjunto de pruebas grande). Sin embargo, todavía no es lo suficientemente rápido para los casos de prueba a ciegas en InterviewStreet. A través de un hack inteligente pude determinar que actualmente estoy ejecutando aproximadamente 20x demasiado lento para completar su conjunto de pruebas en el tiempo asignado. Sin embargo, no puedo encontrar más optimizaciones. El mayor sumidero de tiempo aquí es, obviamente, iterando a través de la segunda dimensión de la tabla 2, y la única manera de evitar eso sería tabular los resultados de esas sumas. Sin embargo, hay demasiadas posibilidades para calcularlas todas en el tiempo dado (5 segundos) o almacenarlas todas en el espacio asignado (256 MB). Por ejemplo, el bucle afortunado (54200-54299 anterior) se puede calcular previamente y almacenar como un solo valor, pero si lo fuera, también tendríamos que pre-calcular afortunado (123000200-123000299) y afortunado (99999200-99999299 ), etc. He hecho los cálculos y son demasiados cálculos para realizar un cálculo previo.
Primero me gustaría agregar que un número de la suerte se puede calcular mediante un tamiz, la explicación del tamiz se puede encontrar aquí: http://en.wikipedia.org/wiki/Lucky_number
para que pueda mejorar la velocidad de su solución utilizando un tamiz para determinar los números,
Acabo de resolver este problema.
Es sólo un problema de programación dinámica. TomeDP[n](sum-square_sum) como la función DP, y DP[n](sum-square_sum) es el recuento de todos los números cuyos dígitos son menores o iguales a n, con la suma y square_sum de dígitos del número se representa respectivamente por suma y square_sum. Por ejemplo: 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
Ya que podemos averiguar fácilmente el primer estado DP DP [1] [..] [..], es:
(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
luego podemos deducir DP [1] a partir de DP [1], y luego DP [3] ... DP [18] la deducción anterior se realiza por el hecho de que cada vez que n aumenta en 1, por ejemplo a partir de DP [1 ] a DP [2], obtuvimos un nuevo dígito (0..9), y el conjunto de (suma, square_sum) par (es decir, DP [n]) debe actualizarse.
Finalmente, podemos recorrer el conjunto de DP [18] y contar los números que son afortunados.
Bueno, ¿qué hay de la complejidad de tiempo y espacio del algoritmo anterior? Como sabemos, la suma <= 18 * 9 = 162, square_sum <= 18 * 9 * 9 = 1458, así que el conjunto de pares (suma, square_sum) (es decir, DP [n]) es muy pequeño, menos de 162 * 1458 = 236196, de hecho es mucho más pequeño que 236196; El hecho es: mi programa ruby contando todos los números de la suerte entre 0 y 10 ^ 18 termina en menos de 1 s.
ruby lucky_numbers.rb 0.55s user 0.00s system 99% cpu 0.556 total
y pruebo mi programa escribiendo una función de prueba utilizando el algoritmo de fuerza bruta, y es correcto para números menores de 10 ^ 7.