Foro de elhacker.net

Hola a todos.

#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   

*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.

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
(http://upload.wikimedia.org/math/0/9/b/09b430032441a41d53299656e04741bd.png)
donde "n" es un numero primo... esa es tu solucion
ej:

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

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.

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?

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)

cierto! :P igual no son operaciones tan pesadas

Considerando mi nivel de programación y atento a lo que me proponen me despido por unos 6 meses :rolleyes: :huh: ;D, 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 (http://www.cplusplus.com/reference/cmath/pow/)

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

#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 (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

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.-   


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   

Hola, buen día.-
engel lex realmente una genialidad lo tuyo, me allano mucho el camino y gracias a todos los que propusieron algo parecido y al resto.-

#include <stdio.h>
#include <math.h> 
 
 
void primo(void);
void perfecto(int num);
 
int main(void){
 
 	primo();	
 
	printf("\n\n");
	return 0;
}
 
void primo(void){
	int num,j, a=0;
	for(num=0; num<=13; num++){
		for(j=1; j<=num; j++){
			if(num%j==0){
				a++;
			}
		}
		if(a==2){
			perfecto(num);
		}
		a=0;
	}	
}
 
void perfecto(int num){
	int auxUno=0, auxDos=0;
	char perfecto[100];
	auxUno = pow(2,num-1);	
	auxDos = pow(2,num)-1;
	sprintf(perfecto,"%d", auxUno * auxDos);
 
	printf("\n %s ", perfecto);
}

      (http://i61.tinypic.com/121cs3r.jpg)

Lo que me traen son 2 consultas:
La primera es, porque el error del quinto número perfecto, según estas 2 páginas el quinto  debería ser 33 550 336 y a mí me sale en el sexto lugar.- 
http://es.wikipedia.org/wiki/N%C3%BAmero_perfecto
http://curiotecnology.blogspot.com.ar/2012/05/los-5-numeros-perfectos-java.html
La segunda, ¿se puede poner los dos resultado (auxUno y auxDos) en un arreglo de char y multiplicarlos para alojarlo en la variable perfecto?, esto me surge porque el séptimo número perfecto no cabe en una variable del tipo int.-
Espero haberme explicado lo suficiente.-

Saludos.
Daniel   

el quito numero es algo que no había leido, la forma da los perfectos cuando n es primo... y diferente de 11, aparentemente 11 es el unico primo no perfecto... disculpas por lo haber visto eso D:

este es mi código usando desplazamiento de bits solo por muestra como sería según yo  ;)

comentado y usando iostream porque me da pereza el printf  ;D

no uso el metodo 2 pero funciona

#include <stdio.h>
 
long unsigned int numero_perfecto_metodo1(int primo);
long unsigned int numero_perfecto_metodo2(int primo);
bool es_primo(int numero);
 
int main(void){
	unsigned long int perfecto;//para 64 bits completos de precision
	int actual; 	
	for(actual = 2; actual <=31; actual++){ //recorre primos del 2 al 27
		if(actual==11)actual = 13; //descarto el error del 11
		if(es_primo(actual)){ //si el numero actual es primo
			perfecto = numero_perfecto_metodo1(actual); //evaluo
			printf("%d = resultado:\t %lu \n",actual,perfecto);
		}
	}
	return 0;
}
long unsigned int numero_perfecto_metodo1(int primo){
	unsigned long int resultado;
	resultado = 1<<(primo-1);
	resultado *= (1<<primo)-1;//a*=b es lo mismo que a= a*b
	return resultado;
}
long unsigned int numero_perfecto_metodo2(int primo){
	unsigned long int resultado;
	resultado = (unsigned long int)((1<<primo)-1)<<(primo-1);//necesita casting (?)
	return resultado;
}
bool es_primo(int numero){
	if(numero == 2) return true; //2 es primo
	if(numero % 2 == 0) return false; //ningun multiplo de 2 es primo
	int prueba;	
	for(prueba = 3;prueba*prueba < numero; prueba+=2){ //solo hasta la raiz
		if(numero%prueba==0) return false; //si tiene multiplo no es primo
	}	
	return true; //entonces si es primo
}

ese metodo de primos está bien documentado aquí en el foro, un numero para saber primo solo hay que investigar hasta su raiz, más allá todo se repite, al excluir los 2 al final el tiempo de calculo se baja desde "n" ciclos hasta "raiz(n) /2" ciclos ej, el 1.000.001 baja de ser 1.000.001 ciclos hasta 500...

para ser sincero se que el metodo 2 necesita casting de tipo, pero no estoy seguro por que...

Hola.
Con el siguiente programita queda demostrado que el 11 primo no es un número perfecto.-

#include <stdio.h>
 
int main(void){
	int a = 33550336, i, res=0;
	printf("\n\n");
	for(i=1; i<100000000; i++){
		if(a%i == 0){
			res += i; 
			if(a == res){
				printf("%10d \n ========== \n%10d", i, res);
				break;
			}
			else{
				printf("%10d\n", i);
			}
		}
	}
 
	printf("\n\n");
	return 0;
}

En el caso del programa tuyo lamentablemente no lo voy a poder correr porque desconozco totalmente C++, me gustaría saber cuál es el perfecto más grande que logras, pero bueno…

Saludos.
Daniel   

ya, puedes copiar de mi ultimo post, modificadas 3 lineas del codigo para hacerlo 100% c  ;D

en

printf("%d = resultado:\t %lu \n",actual,perfecto);

\t es una tabulacion para un espaciador "justificado"
%lu es para imprimir un long unsigned int (%u es unsigned int, %l es long int y se mezclan en uno)

Hola.
Por suerte no puedo ver el movimiento de tus manos ni el gesto de tú cara al leerme nuevamente, tenele un poco de paciencia al “abuelo” Daniel.- ;D ;D ;D
Me podría decir como corregir los siguiente errores, según tengo leído true y false no existen en c.-

(http://i62.tinypic.com/28vab8p.png)

Saludos.
Daniel   

oh... sorry! :P ya voy a arreglarlo, casi no trabajo en c y olvido que no tiene booleanos  :-X

#include <stdio.h>
#define true 1
#define false 0
long unsigned int numero_perfecto_metodo1(int primo);
long unsigned int numero_perfecto_metodo2(int primo);
int es_primo(int numero);
 
int main(void){
	unsigned long int perfecto;//para 64 bits completos de precision
	int actual; 	
	for(actual = 2; actual <=31; actual++){ //recorre primos del 2 al 27
		if(actual==11)actual = 13; //descarto el error del 11
		if(es_primo(actual)){ //si el numero actual es primo
			perfecto = numero_perfecto_metodo1(actual); //evaluo
			printf("%d = resultado:\t %lu \n",actual,perfecto);
		}
	}
	return 0;
}
long unsigned int numero_perfecto_metodo1(int primo){
	unsigned long int resultado;
	resultado = 1<<(primo-1);
	resultado *= (1<<primo)-1;//a*=b es lo mismo que a= a*b
	return resultado;
}
long unsigned int numero_perfecto_metodo2(int primo){
	unsigned long int resultado;
	resultado = (unsigned long int)((1<<primo)-1)<<(primo-1);//necesita casting (?)
	return resultado;
}
int es_primo(int numero){
	if(numero == 2) return true; //2 es primo
	if(numero % 2 == 0) return false; //ningun multiplo de 2 es primo
	int prueba;	
	for(prueba = 3;prueba*prueba < numero; prueba+=2){ //solo hasta la raiz
		if(numero%prueba==0) return false; //si tiene multiplo no es primo
	}	
	return true; //entonces si es primo
}

cambié bool por int y definí true y false

Para generar los cinco números perfectos conocidos (6, 28, 496, 8128, 33550336) con la formula de  Euclides es necesario trabajar con los primos de mersenne (2, 3, 5, 7, 13)  aquí un ejemplo :

#include <math.h>
#include <stdio.h>
#include <limits.h>
 
typedef enum { FALSE = 0, TRUE = 1 } BOOL;
 
BOOL is_prime( int p )
{
    if( p == 2 ) return TRUE;
    else if( p <= 1 || p % 2 == 0 ) return FALSE;
    else
    {
        BOOL prime = TRUE;
        const int to = sqrt(p);
        int i;
        for(i = 3; i <= to; i+=2)
            if (!(prime = p % i))break;
        return prime;
    }
}
 
BOOL is_mersenne_prime( int p )
{
    if( p == 2 )
        return TRUE;
    else
    {
        unsigned m_p = ( 1U << p ) - 1;
        unsigned s = 4;
        int i;
        for (i = 3; i <= p; i++)
            s = (s * s - 2) % m_p;
        return s == 0;
    }
}
 
int main(void)
{
    int p;
 
    for( p = 2; p <= 13; p += 1 )
        if( is_prime(p) && is_mersenne_prime(p) )
           numero_perfecto(p);
           /*printf("%d ", p);*/
    printf("\n");
 
    return 0;
}
 

Un Saludo

Blaster seguro que solo con los primos de mersenne?

es decir...son los numeros tal que

(http://upload.wikimedia.org/math/d/e/9/de90513728abb241a608aaa1ac5c457f.png)

entonces la secuencia da

no están el 2, 5, 13, 17,23... sin embargo son tomados en la secuencia de los perfectos... así que creo que la teoría es incorrecta

Con el algoritmo que propuse por supuesto se obtienen esa secuencia de primos menos el 23 el cual no forma parte de la secuencia de números perfectos en ves debes incluir el tres. Estoy utilizando la prueba de Lucas-Lehmer :

http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer (http://es.wikipedia.org/wiki/Test_de_Lucas-Lehmer)

Para descartar todos los primos no valido, por otra parte en la función es_primo en tu código tienes un pequeño error la condición del for debe quedar así

prueba*prueba <= numero

Debido a esto validaba el nueve como un primo

Hola.
Estoy de acuerdo y con esa modificación los primos están correctos pero los perfectos me parece que no.-
 
(http://i62.tinypic.com/2s9spic.png)

Saludos.
Daniel   

Usa unsigned long long, para números más grandes.

El problema con el código del compañero es que de igual manera procesa los primos no validos (23, 29) y también mencionar el desbordamiento de enteros producido, he aquí un ejemplo que calcula los ocho números perfectos :

#include <math.h>
#include <stdio.h>
#include <limits.h>
 
typedef enum { FALSE = 0, TRUE = 1 } BOOL;
 
BOOL is_prime( int p )
{
    if( p == 2 ) return TRUE;
    else if( p <= 1 || p % 2 == 0 ) return FALSE;
    else
    {
        BOOL prime = TRUE;
        const int to = sqrt(p);
        int i;
        for(i = 3; i <= to; i+=2)
            if (!(prime = p % i))
                break;
        return prime;
    }
}
 
BOOL is_mersenne_prime( int p )
{
    if( p == 2 )
        return TRUE;
    else
    {
        long long unsigned m_p = ( 1U << p ) - 1;
        long long unsigned s = 4;
        int i;
        for (i = 3; i <= p; i++)
        {
            s = (s * s - 2) % m_p;
        }
        return s == 0;
    }
}
 
int main(int argc, char **argv)
{
    const int upb = log2l(ULLONG_MAX)/2;
    int p;
 
    for( p = 2; p <= upb; p++ )
    {
        if( is_prime(p) && is_mersenne_prime(p) )
            printf(" %llu\n", (long long unsigned)(1U << (p - 1)) * ((1U << p) - 1));
    }
    printf("\n");
 
    return 0;
}
 

Puedes comprobarlo aquí :

http://www.vaxasoftware.com/doc_edu/mat/numperfe_esp.pdf

Un saludo

El problema es que solo presentas la salida del programa, sin el código fuente no es posible conocer la causa del error (imagino tiene que ver con tu otra duda).

El segundo metodo es:

long unsigned int numero_perfecto_metodo2(int primo)
{
   unsigned long int resultado;
   resultado = (unsigned long int) ((1 << primo) - 1) << (primo - 1);
   return resultado;
}

El cual se puede abreviar a:

long unsigned int numero_perfecto_metodo2(int primo)
{
   return ((1 << primo) - 1) << (primo - 1);
}

El problema ahí es la primera literal 1, esta es de tipo signed int y puede, dependiendo del desplazamiento, generar un numero negativo. Para solucionarlo lo mas fácil es indicar que el tipo de ella es unsigned long mediante sufijos: 1UL.

Un saludo