Página 1 de 2 12 ÚltimoÚltimo
Resultados 1 al 10 de 19

Tema: Algoritmo eficiente hallar numeros primos

  1. #1

    Predeterminado Algoritmo eficiente hallar numeros primos

    Hola compañeros, me decidido a registrarme por fin, aunque os llevo siguiendo desde hace algun tiempo.

    A ver si me podéis echar una mano.

    El tema es que necesito un algoritmo lo mas eficiente posible, para hallar numeros primos.

    Tengo q hacer un programa en C en el cual meto un intervalo (por ejemplo, desde 30 hasta 10000) y el programa debe decirme el nº de numeros primos que hay en ese intervalo.

    He mirado por diversos buscadores y no encuentro nada del todo eficiente.... y he encontrado en la wikipedia algo, pero no consigo implementarlo correctamente.

    Hasta ahora lo que tengo hecho es que:

    Voy comprobando si es primo nº por nº del intervalo, y si es primo incremento un contador llamado "contadorprimos".
    - Cuando voy a comprobar, si el nº es par, directamente no lo compruebo, ya que no es primo (a excepcion del 2)
    - Como la comprobacion voy haciendola con numero a comprobar mod i, si tngo que ver por ejemplo si es primo, solo hago la division hasta la raiz cuadrada del nº a comprobar.


    No se si me he explicado bien, espero que me echeis una mano, ya que necesito que sea rapido el programa.

    No pido el programa implementado en C (si pudiera ser pues mejor, ya que asi empleo el tiempo en otra parte que debo realizar), con que me deis informacion sobre alguna pagina, o el algoritmo en pseudocodigo me vale.

    Un saludo y gracias!

  2. #2

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Hombre, no dispongo aqui de los apuntes matematicos necesarios para responderte, pero vamos, existen multitud de algoritmos deterministas de test de primalidad que para los conocimientos matematicos que requieren tal vez no merezca la pena ni ponerse a implementarlos, eso depedera de ti. Para algoritmos clasicos deterministas de complejidad no polinomial es posible que la mejora que pueda ofrecer un algoritmo frente a otro para numeros pequeños como los que tu empleas ni se note.

    Recientemente parece ser que se ha mostrado que realmente el problema de la primalidad de un numero esta en P, es decir, es un problema que puede resolverse en tiempo polinomial (algoritmo AKS)

    Pero si lo que tu buscas es rapidez simplemente, probablemente puedan interesarte mas los algoritmos probabilistas de test de primalidad, que tambien existen unos cuantos.

    Intentare comentarte algo mas al respecto en cuanto pueda.

    Un saludo.

  3. #3

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Gracias Jerk, estare atento a este post a ver si sacamos algo entre todos.


    Estoy tratando de implementar en C este programa en Pascal:

    http://numerosprimos.5u.com/codigo.htm


    Y mi codigo es este:


    #include <stdio.h>
    #include <sys/time.h>
    #include <math.h>

    float x,k;
    int v,z,f,h,rango1,rango2;
    int num_primos;


    /***********************FUNCION BUCLE*********************/


    bucle()
    {
    int j=0;
    int i=1;
    while ((j!=1) && (i!=z))
    {
    i++;
    j=floor(x/(1-2*i)+(i+1/2)/(2*i-1))-floor(x/(1-2*i)+1/2);
    }
    if (j==0)
    num_primos++;

    }




    /************************************************** ****************************/
    /******************** PROGRAMA PRINCIPAL ********************************/
    /************************************************** ****************************/

    main(int argc, char *argv[])
    {

    k=0;
    num_primos=0;
    rango1=atoi(argv[1]);
    rango2=atoi(argv[2]);
    f=floor((rango1+1)/2);
    h=floor((rango2+1)/2);

    printf("Valor de f = %d y el valor de h es de : %d",f,h);

    for (v=f;v<h;v++)
    {
    k=2*v-1;
    x=(k+1)/2;
    if (((ceil((sqrt(k)+1)/2))-((sqrt(k)+1)/2))<0.5)
    z=ceil((sqrt(k)+1)/2);
    else
    z=floor((sqrt(k)+1)/2);


    //codigo de arriba en sustitucion del round to
    //z=roundto(((sqrt(k)+1)/2),0);


    bucle();
    }



    printf("\tNumero de primos desde %d hasta %d es igual a: %d\n ",rango1,rango2,num_primos);

    }


    Y no soy capaz de encontrar el fallo.... Si podriais echarme una mano....

    (la forma de ejecucion es primos rango1 rango2)

  4. #4
    Master Avatar de Ricardo (alfa)
    Ubicación
    Argentina
    Edad
    30
    Mensajes
    1,849

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Hola, mira yo creo que realizando un algoritmo que realice esto... tienes el problema solucionado

    "Un número p es primo si y solo si el factorial (p − 1)! + 1 es divisible por p. "

    Otra manera de hacerlo es, inicias a contar a partir del 7 (ya sabiendo que 2,3,5,7) son primos, vas sumando de 2 en dos empezando por el 7,y dividiendo por los primos anteriores, si este no da entero con ningun numero primo anterior, pues ya sabes que es primo.

    Saludos, esta ultima teoria se me ocurrio recien, habria que comprobarlo para ver si no me equivoco,llevo dias sin dormir

  5. #5

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Emm... pensaba que necesitabas ayuda sobre algoritmica de numeros primos, no que tuvieses un error en tu codigo.

    Yo miraria en otros lugares de internet en busca de algoritmos. Este que has puesto es bastante malo. Duelen los ojos al ver el codigo de lo malo que es.

    Por otra parte, no se entiende muy bien que algoritmo quieren implementar ya que en la pagina principal hablan de una supuesta formula que segun el tio ese dice cuando un numero es primo o no.

    Para empezar, se ven en el codigo cosas como esta :

    k:=2*v-1;
    x:=(k+1)/2;

    Resulta que al final x es igual a v puesto que x = ((2*v - 1)+1)/2 por lo que queda x = v. No tiene sentido esto. Como no tienen sentido muchas otras cosas de esa implementacion porque al final el algoritmo es el de siempre.

    Luego, para saber si un numero es divide a otro hace una peazo funcion con un monton de divisiones , truncates, etc.. !!cuando la cosa es tan sencilla como calcular "x mod i" que no es mas que hacer una division y tomar el resto!!

    Buscate otra implementacion de este algoritmo, porque te vas a liar.. Por ejemplo :

    Código:
    Defint A-Z 'Todas las     variables son enteras
        Function EsPrimo( N )
             Resultado = -1 'Si llega a ser     primo devuelve -1
             For i = 2 To Sqr( N )'Raiz     cuadrada de n
                  If     N / i = Int ( N / i ) Then
                       Resultado     = 0 'No, no es primo y devuelve 0
                       Exit     For 'Sale del For...Next
                  End     If
             Next i
             EsPrimo = Resultado
        End Function
    Un saludo.

  6. #6

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Ricardo, el algoritmo que propones es interesante, pero no seria demasiado lento al tener que realizar tantas multplicaciones en un factorial??? Imagina cuando tocase comprobar un nº de 6 cifras.....



    Jerk el algoritmo que has puesto ya lo tngo implementado e incluso con alguna mejorilla, pero es que busco uno eficiente y rapido, que es lo que me interesa.
    Y sobre lo que has dicho del codigo que he puesto pues tienes razon, no me habia fijado yo en eso jeje, es que lo encontre en la pagina esa y ponia q era bastante eficiente.



    Gracias de nuevo a los 2!




    EDITADO:

    Por cierto, en C no existe una funcion similar a Round en Pascal verdad???
    Es decir redondeo al entero mas cercano, para no usar el floor y el ceil asi:

    if (((ceil((sqrt(k)+1)/2))-((sqrt(k)+1)/2))<0.5)
    z=ceil((sqrt(k)+1)/2);
    else
    z=floor((sqrt(k)+1)/2);
    Última edición por MARTIN_LAW; 11/12/2006 a las 15:38

  7. #7

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Código PHP:
    #include <stdio.h>
    void primos (int n1)
    {
        
    int aux,i,j;
        for (
    i=1;i<=n1;i++)
            {
            
    /* Estudiamos si el numero 'i' es primo o no. Para ello contabilizamos sus divisores.*/

            
    aux=0;
            for (
    j=1;j<=i;j++)
            {
                if (
    i%j==0)
                    
    aux++;
            }
            
    /* Todo numero es divisible entre 1 y entre si mismo; por tanto, si el numero total de divisores
            Es igual a 2, el numero es primo. */
            
    if (aux==2)
                
    printf("%d\n",i);
        }
    }

    int main()
    {
        
    int n1;


        do
        {

            
    printf("Introduce un numero mayor que cero: ");
            
    scanf("%d",&n1);
        }while(
    n1<1);
        
    printf("Los numeros primos entre 1 y %d son:\n",n1);
        
    primos(n1);

        return 
    0;

    Aqui tienes algo muy parecido, si cambias lo del 1 por otra variable ya lo tienes.

  8. #8

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Gracias Spyder pero eso ya lo tengo, busco algo eficiente, rapido, esa version que me pones es la mas basica.....


    Gracias de todos modos por la ayuda, que se agradece, esta tarde buscando he encontrado algunas cosillas a ver si me pongo a ello y os comento.

  9. #9

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    el matlab creo que es el que usar de los mejores algoritmos para sacar primos.
    Del gran mar he llegado a la tierra media, y esta sera mi morada y la de mis descendientes hasta el fin del mundo.

  10. #10

    Predeterminado Re: Algoritmo eficiente hallar numeros primos

    Cita Iniciado por Cardoomx Ver mensaje
    el matlab creo que es el que usar de los mejores algoritmos para sacar primos.

    Hola compañero Cardoomx, y como podría ver dichos algoritmos????

    Es que no poseo matlab....

    Un saludo

Página 1 de 2 12 ÚltimoÚltimo

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •