• Jueves 14 de Noviembre de 2024, 23:20

Autor Tema:  Numeros Primos.  (Leído 10217 veces)

JoRDi-18

  • Miembro activo
  • **
  • Mensajes: 40
    • Ver Perfil
Numeros Primos.
« en: Domingo 18 de Enero de 2004, 17:29 »
0
Hola:

Necesito un algoritmo que, dado un numero natural n, muestre por pantalla los n primeros números primos.

He intentado hacerlo pero me estoy volviendo loco y no tengo ni idea de cómo seguir. Alguien me puede ayudar? Pongo lo que tengo hecho, pero esque no me sirve... Ayudadme por favor!!

Código: Text
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. void Fprimos (int num, int vector[]);
  6.  
  7. int cont=1; int i=1;
  8.  
  9. int main (){
  10.    int n;  int num=1;
  11.    int vector[1000]={1};
  12.    
  13.    printf ("Muestra por pantalla de los n primeros numeros primos.");
  14.    printf ("\n\nIntroduce el numero n de numeros primos que mostrare: ");
  15.    scanf ("%d", &n);
  16.    while (cont <= n){
  17.       Fprimos (num, vector);
  18.       num++;
  19.    }
  20.    
  21.    printf ("\nLos %d primeros numeros primos son: ", n);
  22.    for (i=0; i<=cont; i++){
  23.       printf ("%d", vector[i]);
  24.    }
  25. }
  26.  
  27. void Fprimos (int num, int vector[]){
  28.    for (i=1; i <= cont; i++){
  29.       if (num%vector[i]!=0){
  30.          if (i==cont){
  31.             vector[cont]=num;
  32.             cont++;
  33.          }
  34.       }else{
  35.          if (i==cont) return;
  36.       }
  37.    }
  38. }  
  39.  
  40.  
  41.  
  42.  
[size=109]Pensamientos elevados deben tener un lenguaje elevado.[/size]
Llamamé Jordi. Cuando me llames así, sonríe.

GhostGirl

  • Nuevo Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re: Numeros Primos.
« Respuesta #1 en: Lunes 19 de Enero de 2004, 04:25 »
0
Hola!!!!. Un programilla que te imprime los n primeros números primos es:

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>

int main()
{
      int n, j, divisores, numero, total_primos;
      // Leemos el valor de n
      fprintf(stdout,"Valor de n = ");
      scanf("%d",&n);

      total_primos = 0;  // Controla el total de primos
      numero = 1;        // Controla los números a analizar

      // Ciclo para obtener los 'n' números primos
      while (total_primos < n)
      {
          divisores = 0;      // Cuenta el número de divisores

          // Para que un numero sea primo, no se deben encontrar divisores entre 2 y n-1
          for(j=2;j<numero;j++)
          {
               if ( (numero % j) == 0) divisores++;
          }

          // Controla el numero de divisores encontrados
          if (divisores == 0)
          {
               total_primos++;
               fprintf(stdout,"Primo Nro. %d es %d\n ",total_primos,numero);
          }
          // Pasa al siguiente numero
          numero++;
      }
      system("PAUSE");
      return 0;
}

La idea es considerar que un numero primo es aquel que es sólo divisible por 1 y por si mismo, es decir que no deben haber divisores dentro del rango [2, x-1] para todo x.

Espero que te sirva de algo

Saludos

--
Yasna Meza Hidalgo

shephiroth

  • Miembro activo
  • **
  • Mensajes: 30
    • Ver Perfil
Re: Numeros Primos.
« Respuesta #2 en: Lunes 19 de Enero de 2004, 21:32 »
0
buenas. Peazo codigos grandes que poneis. Aqui te pongo una funcion recursiva pequeñita que devuelve el proximo numero primo. Es decir, tu le pasas un numero (sobreentiende que es primo) y te muestra el siguiente.

int primoRecursivo(int num)
{
num++;
bool primo=true;
for (y=2;y*y<=num && primo;y++)
     if (num%y==0) primo=false;
if (primo)
     return num;
else
     return primoRecursivo(num);
}

Si ahora, lo que quieres es mostrar x numeros primos con un simple bucle

primo=1;
for (z=0;z<x;z++)
{
primo=primoRecursivo(primo);
printf("Numero primo numero "+(z+1)+"es "+primo+"\n");
}

como veis este codigo es mucho mas reducido. Eso si, hay q entender recursivas xDD

EDITADO: la primera condicional de la recursiva tiene q ser <=, sino los numeros cuadrados (4,9,16,25...) los daría como primos xDD

GhostGirl

  • Nuevo Miembro
  • *
  • Mensajes: 9
    • Ver Perfil
Re: Numeros Primos.
« Respuesta #3 en: Lunes 19 de Enero de 2004, 21:55 »
0
Hola, mira tal vez tengas razón con respecto al largo del código, pero mi experiencia me ha indicado que cuando una persona se está iniciando en el mundo de la programación NO PUEDES hablarle de recursividad de buenas a primeras. El tema de la recursividad es algo complejo para quienes ya tienen un conocimiento de programación, imagina si se trata de alguien que recien se inicia ........

Saludos

--
Yasna Meza Hidalgo

QliX=D!

  • Miembro MUY activo
  • ***
  • Mensajes: 214
    • Ver Perfil
Re: Numeros Primos.
« Respuesta #4 en: Martes 20 de Enero de 2004, 21:49 »
0
Cita de: "shephiroth"
buenas. Peazo codigos grandes que poneis. Aqui te pongo una funcion recursiva pequeñita que devuelve el proximo numero primo. Es decir, tu le pasas un numero (sobreentiende que es primo) y te muestra el siguiente.

int primoRecursivo(int num)
{
num++;
bool primo=true;
for (y=2;y*y<=num && primo;y++)
     if (num%y==0) primo=false;
if (primo)
     return num;
else
     return primoRecursivo(num);
}

Si ahora, lo que quieres es mostrar x numeros primos con un simple bucle

primo=1;
for (z=0;z<x;z++)
{
primo=primoRecursivo(primo);
printf("Numero primo numero "+(z+1)+"es "+primo+"\n");
}

como veis este codigo es mucho mas reducido. Eso si, hay q entender recursivas xDD

EDITADO: la primera condicional de la recursiva tiene q ser <=, sino los numeros cuadrados (4,9,16,25...) los daría como primos xDD
Hey mr...
Proba pidiendole a tu "funcion" el primo del numero 2000000 (dos millones)...
QliX=D! - From the top of Tsunami

shephiroth

  • Miembro activo
  • **
  • Mensajes: 30
    • Ver Perfil
Re: Numeros Primos.
« Respuesta #5 en: Miércoles 21 de Enero de 2004, 12:50 »
0
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!

  • Miembro MUY activo
  • ***
  • Mensajes: 214
    • Ver Perfil
Re: Numeros Primos.
« Respuesta #6 en: Miércoles 21 de Enero de 2004, 14:11 »
0
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).
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
QliX=D! - From the top of Tsunami

CiRRuS

  • Miembro MUY activo
  • ***
  • Mensajes: 218
    • Ver Perfil
    • http://zirrus.es
Re: Numeros Primos.
« Respuesta #7 en: Viernes 23 de Enero de 2004, 14:12 »
0
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
Core Dumped
zirrus.es