Números perfectos (lenguaje C)

[NOB2014]

Hola a todos.

Código (c) [Seleccionar] Expandir

#include <stdio.h>

#define MAX 10000
void numerosPerfectos();

int main(void){

numerosPerfectos();

return 0;
}

void numerosPerfectos(){
int acumulador=0, i, j=1;

printf("\n\n N%cmeros perfectos...: ", 163);

for(i=1; i<MAX; i++){
acumulador = 0;
for(j=1; j<i; j++){
if(i % j == 0){
acumulador += j;
}
}
if(i == acumulador){
printf(" %d ", i);
}
}
}

El inconveniente es que si pongo #define MAX 10000 el resultado lo muestra en un periodo de tiempo aceptable, pero si deseo saber del 1 al 100000 muestra ==> 6- 28 – 496 – 8128 y de aquí en más tarda en términos de computación una eternidad (para terminar el programa).-
La consulta es, ¿sabe alguien otra manera de hacerlo?, mi computadora si bien es un poco vieja (2gb de ram) me parecería que tendría que mostrarlo al instante, pero no es así.-

Desde ya muchas gracias.-
   
Saludos.
Daniel   

[ivancea96]

*La capacidad de la RAM en este caso no es especialmente relevante.

En cuanto al tema, no necesitas dar X iteraciones para un número X. Basta con poner de tope la raíz cuadrada del número.

Una vez encontrados los divisores inferiores a la raiz cuadrada, los divisores superiores son, siendo el divisor inferior 'N', X/N.

Dado que K*N = X, una vez sacamos un divisor, por ejemplo N, ya tenemos también K.

En caso de que X sea un cuadrado perfecto, X/N==N, por lo que no habría que sumarlo.

En definitiva, esto no es un problema de C++, esto es un problema de algoritmia y matemáticas, quizás fuera más correcto colocarlo en el Foro Libre o en Programación General.

[engel lex]

rayos ivancea96 te me adelantaste! estaba preparando la respuesta jejeje igual allí voy (en gran parte para repetirte)


lo importante aquí no es la ram, ya que el programa solo usa 3 int (en total 12bytes) + el programa en si que dudo que llegue a 100kb... esto no llegará a 1mb de ram...

el problema aquí es el tiempo de procesamiento, es decir la velocidad del procesador contra la cantidad de operaciones hechas, por la estructura de tu programa el hace x! operaciones donde x es MAX

es decir cada paso la cantidad de cálculos aumenta brutalmente

por otro lado algo que tarda es el printf, es preferible que guardes en un array y luego imprimas, es más rápido guardar 4bytes en la ram que iniciar todo un proceso para imprimir en pantalla

realmente no estoy claro sobre tu proceso de los "números perfectos" pero intenta buscar alguna formula que te resuma el ciclo

-------agrego--------

estuve investigando y según Euclides los números perfectos se basan en esta formula

donde "n" es un numero primo... esa es tu solucion
ej:

n = 2:   2¹ × (2² – 1) = 6
n = 3:   2² × (2³ – 1) = 28
n = 5:   2⁴ × (2⁵ – 1) = 496
n = 7:   2⁶ × (2⁷ – 1) = 8128

esa forma debe ser infinitamente más ligera para el procesador especialmente si lo haces con desplazamiento de bits, porque son potencias de 2

[NOB2014]

Hola ivancea99.

Te agradezco el aporte, si en algún momento te encuentras con tiempo libre te agradecería si pones un poco de código, con mis 62 años me cuesta recordar raíz cuadradas y demás, sé que es algo  que indefectiblemente voy a tener que estudiar si quiero aprender a programar, pero en este momento estoy en el tema funciones en c y es lo que me pide el libro hacer.-

Mientras estaba tratando de solicitar ayuda y agradecer a ivancea99 me aparece el cartelito rojo advirtiendo  que hubo otra respuesta al tema...
engel lex creo que estas en lo cierto "si lo haces con desplazamiento de bits" lo voy a intentar, aunque a fuerza de ser prejuicioso no creo que lo logre por mi mismo    
 
Saludos.
Daniel

[Shout]

Hola ivancea99.     
Mientras estaba tratando de solicitar ayuda y agradecer a ivancea99 me aparece el cartelito rojo advirtiendo  que hubo otra respuesta al tema...
engel lex creo que estas en lo cierto "si lo haces con desplazamiento de bits" lo voy a intentar, aunque a fuerza de ser prejuicioso no creo que lo logre por mi mismo   
   
Saludos.
Daniel

Hazlo multiplicando, seguramente el compilador lo optimice a bitshifts.

[engel lex]

es muy simple, resumes toda la operacion a una sola linea... pero ahora tienes un problema diferente pero más simple, buscar numeros primos jejeje la operacion de numeros primos se ha hablado mucho en el foro y hay soluciones rapidas y creativas... eso si, descubrirás el uso de unsigned y long porque estás usando numero MUY grandes...

me diste algo que investigar, estuve viendo la progesion completa (sin importar si eran primos o no) en binario y son muy simple en ese aspecto... pero me da un error que no descubro la razón...

alquien me da ayuda?

Código [Seleccionar] Expandir

2 = resultado: 0000000000000000000000000000000000000000000000000000000000000110
3 = resultado: 0000000000000000000000000000000000000000000000000000000000011100
4 = resultado: 0000000000000000000000000000000000000000000000000000000001111000
5 = resultado: 0000000000000000000000000000000000000000000000000000000111110000
6 = resultado: 0000000000000000000000000000000000000000000000000000011111100000
7 = resultado: 0000000000000000000000000000000000000000000000000001111111000000
8 = resultado: 0000000000000000000000000000000000000000000000000111111110000000
9 = resultado: 0000000000000000000000000000000000000000000000011111111100000000
10 = resultado: 0000000000000000000000000000000000000000000001111111111000000000
11 = resultado: 0000000000000000000000000000000000000000000111111111110000000000
12 = resultado: 0000000000000000000000000000000000000000011111111111100000000000
13 = resultado: 0000000000000000000000000000000000000001111111111111000000000000
14 = resultado: 0000000000000000000000000000000000000111111111111110000000000000
15 = resultado: 0000000000000000000000000000000000011111111111111100000000000000
16 = resultado: 0000000000000000000000000000000001111111111111111000000000000000
17 = resultado: 0000000000000000000000000000000111111111111111110000000000000000
18 = resultado: 0000000000000000000000000000011111111111111111100000000000000000
19 = resultado: 0000000000000000000000000001111111111111111111000000000000000000
20 = resultado: 0000000000000000000000000111111111111111111110000000000000000000
21 = resultado: 0000000000000000000000011111111111111111111100000000000000000000
22 = resultado: 0000000000000000000001111111111111111111111000000000000000000000
23 = resultado: 0000000000000000000111111111111111111111110000000000000000000000
24 = resultado: 0000000000000000011111111111111111111111100000000000000000000000
25 = resultado: 0000000000000001111111111111111111111111000000000000000000000000
26 = resultado: 0000000000000111111111111111111111111110000000000000000000000000
27 = resultado: 0000000000011111111111111111111111111100000000000000000000000000
28 = resultado: 0000000001111111111111111111111111111000000000000000000000000000
29 = resultado: 0000000111111111111111111111111111110000000000000000000000000000
30 = resultado: 0000011111111111111111111111111111100000000000000000000000000000
31 = resultado: 0101111111111111111111111111111111000000000000000000000000000000
32 = resultado: 0000000000000000000000000000000000000000000000000000000000000000


en el 31 aún y cuando son solo desplazamientos se salta un 1 en el penultimo bit y 32 el ultimo en lugar de desbordarse, se limpió (no pongo el código por razones del post)

Hazlo multiplicando, seguramente el compilador lo optimice a bitshifts.

cierto! igual no son operaciones tan pesadas

[NOB2014]

Considerando mi nivel de programación y atento a lo que me proponen me despido por unos 6 meses , espero que la pasen muy bien y un gran abrazo, cuando tenga el programa completado y funcionando regreso.-   

Saludos.
Daniel   

[engel lex]

Considerando mi nivel de programación y atento a lo que me proponen me despido por unos 6 meses , espero que la pasen muy bien y un gran abrazo, cuando tenga el programa completado y funcionando regreso.-   

Saludos.
Daniel   

jejeje no seas dramatico! tranquilo que pensandolo eso sale, como dice Shout puedes hacerlo con multiplicaciones... o tomando su palabra, puedes incluso hacerlo con la libreria "<cmath>" y usando pow como en estos ejemplos

[Blaster]

La consulta es, ¿sabe alguien otra manera de hacerlo?, mi computadora si bien es un poco vieja (2gb de ram) me parecería que tendría que mostrarlo al instante, pero no es así.-

Aquí tienes un código bastante interesante, que a mi parecer es bastante rápido :

Código (cpp) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

char bits[65536];

typedef unsigned long ulong;
ulong primes[7000], n_primes;

typedef struct
{
    ulong p, e;
} prime_factor;

void sieve(void)
{
    int i, j;
    memset(bits, 1, 65536);
    bits[0] = bits[1] = 0;
    for (i = 0; i < 256; i++)
        if (bits[i])
            for (j = i * i; j < 65536; j += i)
                bits[j] = 0;
    for (i = j = 0; i < 65536; i++)
        if (bits[i]) primes[j++] = i;

    n_primes = j;
}

int get_prime_factors(ulong n, prime_factor *lst)
{
    ulong i, e, p;
    int len = 0;

    for (i = 0; i < n_primes; i++)
    {
        p = primes[i];
        if (p * p > n) break;
        for (e = 0; !(n % p); n /= p, e++);
        if (e)
        {
            lst[len].p = p;
            lst[len++].e = e;
        }
    }
    return n == 1 ? len : (lst[len].p = n, lst[len].e = 1, ++len);
}

int ulong_cmp(const void *a, const void *b)
{
    return *(const ulong*)a < *(const ulong*)b ? -1 : *(const ulong*)a > *(const ulong*)b;
}

int get_factors(ulong n, ulong *lst)
{
    int n_f, len, len2, i, j, k, p;
    prime_factor f[100];

    n_f = get_prime_factors(n, f);

    len2 = len = lst[0] = 1;
    for (i = 0; i < n_f; i++, len2 = len)
        for (j = 0, p = f[i].p; j < f[i].e; j++, p *= f[i].p)
            for (k = 0; k < len2; k++)
                lst[len++] = lst[k] * p;

    qsort(lst, len, sizeof(ulong), ulong_cmp);
    return len;
}

int main(void)
{
    int j;
    ulong fac[10000], n, sum;

    sieve();

    for (n = 2; n < 33550337; n++)
    {
        j = get_factors(n, fac) - 1;
        for (sum = 0; j && sum <= n; sum += fac[--j]);
           if (sum == n)
              printf("%lu\n", n);
    }
    return 0;
}


Fuente : http://rosettacode.org/wiki/Factors_of_an_integer#Prime_factoring

Solo le hice una pequeña modificación en el main para adaptarlo a tu propósito

Un Saludo

[NOB2014]

Hola Blaster.
Muchas gracias por tú aporte, en realidad es mucho más rápido que el que yo postee, por lo menos los primeros cuatros aparecen al instante pero el quinto no me aparece nunca, de cualquier manera voy a intentar implementar lo de engel lex, me parece que de esa manera va a funcionar muy bien.-   

n = 2:   21 × (22 – 1) = 6
n = 3:   22 × (23 – 1) = 28
n = 5:   24 × (25 – 1) = 496
n = 7:   26 × (27 – 1) = 8128

Mil disculpas si se me pasó por alto agradecer a alguien y les pongo esta página que está relacionada y me causo mucha gracia.-

http://curiotecnology.blogspot.com.ar/2012/05/los-5-numeros-perfectos-java.html


Saludos.
Daniel