Programación General > C/C++
Numeros Primos.
shephiroth:
2000000....vamos a ver, habla de enteros, por eso hice la funcion con int. Si le pongo float problema solucionado. Solo tienes que cambiar la declaracion de la cursiva de
int primoRecursivo(int num)
a
float primoRecursivo(float num)
porque si te diste cuenta primo no lo inicielice ni a int ni a double ni a float.
De todos modos si creeis que recursiva es demasiado, aqui os pongo la funcion sin recursividad:
float primoNoRecursivo(float num)
{
bool primo=true;
bool division;
float y;
for (num++;primo;num++)
{
division=true;
for (y=2;y*y<=num && division;y++)
if (num%y==0) division=false;
if (division) primo=false;
}
return num;
}
Vaya, casi mas pequeña que la recursiva.
Creeis vosotros que "alguien que empieza" entiende mejor esto que la recursiva?? Sinceramente, yo creo que este codigo es más rebuscado y menos claro. Mas preciso, más rápido, mas "economico" debido a no ser recursiva y todo lo que querais, pero weno.
En esta si puse float, no me vayan a salir con las mismas (y si me sales con las mismas con el tope de float, hazlo con un vector de numeros (cada posicion un solo digito) a ver si asi te gusta mas, que ahi no tienes limite pq el vector lo puedes hacer cuan largo quieras).
QliX=D!:
--- Cita de: "shephiroth" --- 2000000....vamos a ver, habla de enteros, por eso hice la funcion con int. Si le pongo float problema solucionado. Solo tienes que cambiar la declaracion de la cursiva de
int primoRecursivo(int num)
a
float primoRecursivo(float num)
porque si te diste cuenta primo no lo inicielice ni a int ni a double ni a float.
De todos modos si creeis que recursiva es demasiado, aqui os pongo la funcion sin recursividad:
float primoNoRecursivo(float num)
{
bool primo=true;
bool division;
float y;
for (num++;primo;num++)
{
division=true;
for (y=2;y*y<=num && division;y++)
if (num%y==0) division=false;
if (division) primo=false;
}
return num;
}
Vaya, casi mas pequeña que la recursiva.
Creeis vosotros que "alguien que empieza" entiende mejor esto que la recursiva?? Sinceramente, yo creo que este codigo es más rebuscado y menos claro. Mas preciso, más rápido, mas "economico" debido a no ser recursiva y todo lo que querais, pero weno.
En esta si puse float, no me vayan a salir con las mismas (y si me sales con las mismas con el tope de float, hazlo con un vector de numeros (cada posicion un solo digito) a ver si asi te gusta mas, que ahi no tienes limite pq el vector lo puedes hacer cuan largo quieras).
--- Fin de la cita ---
En 32 bits int = float asi qeu eso es lo de menos.
Pasa que la Recursiva con numeros grandes da un bonito: "STACK OVERFLOW" por eso lo decia.
slds
CiRRuS:
Antes que nada, un saludo a todos, este es mi primer mensaje en el foro, y espero que no el último ;).
Para comprobar la primalidad de un número, aparte de ponerte a dividir como decís, existen una serie de tests de primalidad, usados principalmente en criptografía para comprobar la validez de las claves y tal.
Uno de ellos es el Test de Miller-Rabin:
Test de primalidad de Miller-Rabin para n >= 3 impar
1.- q = n - 1, t= 0, mientras que q sea par poner q = q / 2 y t = t + 1.
Poner c = 10
2.- Elegir a aleatorio con 1 < a < n. Poner e = 0, b = a^q (n).
Si b es 1 ir al paso 4
3.- Mientras que b no es congruente +-1 (n) y e <= t - 2 poner b = b^2 (n)
y e = e + 1. Si b no es congruente con -1 (n) decir que es compuesto
y terminar el algoritmo
4.- Poner c = c - 1. Si c > 0 ir al paso 2, si no, decir que n es
probablemente primo. */
También esta el método de factorización de Rho, pero el resultado es menos satisfactorio. Estos test calculan la primalidad estadísticamente, es decir, el número es "probablemente" primo. En el caso de Miller-Rabin no recuerdo cual era la fórmula, pero era bastante preciso, de hecho se usa a menudo para implementaciones "domésticas" del algoritmo de encriptación RSA y validación de claves.
Espero haberte ayudado, di tienes problemas con la implementación no tienes más que decirlo.
Nos vemos
Navegación
[*] Página Anterior
Ir a la versión completa