Saber cuando un numero es o no primo

      • 54
      • mensajes
      • miembro desde
      • 14/08/08
    #21 Re: Saber cuando un numero es o no primo

    Los mejores algoritmos (en cuanto a tiempo) para decidir si un numero es primo o no son del orden de log^a (a constante).

    El algoritmo que escribiste tiene tiempo de ejecución constante, si realmente tu algoritmo funcionase, te habrían dado una Fields Medal, un Turing o algo así, y antes de publicarlo podrias haber roto la seguridad de cientos de cuentas.

    Por darte un ejemplo falla con 13^2


    Saludos

      • 73
      • mensajes
      • miembro desde
      • 07/06/07
    16/12/2009
    #22 Re: Saber cuando un numero es o no primo
    Código:
    #include <iostream>
    #include <math.h>
    
    using namespace std;
    
    int main() //Para determinar si un número es primo basta con recorrer con los divisores hasta su raíz cuadrada
    {
        int n,cont=0,num;
        cout << "Ingrese Numero: ";
        cin >> num;
        for(n=2;n<pow(num,0.5);n++){
            if((num%n)==0){
                cont++;
            }
        }
        if(cont==0){
            cout << "Es Primo" << endl;
        }else{
            cout << "No es Primo" << endl;
        }
    }
      • 2
      • mensajes
      • miembro desde
      • 24/08/10
    24/08/2010
    #23 Re: Saber cuando un numero es o no primo
    Elaborar una solución que imprima los N números primos
    INICIE
    LEA NUM
    SW= 0, N= 2, C= 0
    MIENTRAS N <= NUM/2 AND SW= 0, HAGA
    SI NUM MOD N= 0, ENTONCES
    SW= 1
    SI NO
    N= N+1
    FIN SI
    LEA NUM
    FIN MIENTRAS
    SI SW= 0, ENTONCES
    C= C+1
    IMPRIMA C
    FIN SI
    TERMINE
      • 1
      • mensajes
      • miembro desde
      • 14/02/11
    14/02/2011
    #24 Re: Saber cuando un numero es o no primo

    Hice esta respuesta. Está en lenguaje C. A mi me funciona de maravillas. Hice de la respuesta de Registrarse Inicia sesión . Aqui va:

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


    int main()
    {
    int C,X,cont,num;
    printf("ingrese un numero");
    scanf("%d",&num);
    cont=0;
    C = num;
    if(C <= 1){
    printf("El numero es primo");
    system ("pause");
    return 0;
    }
    while(C>0){
    X=0;
    X=num%C;
    if(X==0){
    cont++;
    }
    C = C -1;
    }
    if (cont>2){
    printf("El numero NO es primo");
    system ("pause");
    return 0;}
    if(cont<3){
    printf("El numero es primo");
    system ("pause");
    return 0;}
    }

    para los que quieren en algoritmo hice esto:

    var
    C,X,cont,num:numerico
    inicio
    escriba"Introduzca el numero"
    lea num
    cont=0
    C = num
    Si C <= 1 entonces
    escriba "El numero es primo"
    finsi
    haga mientras C>0
    X=num mod C
    Si X==0 entonces
    cont=cont+1
    finsi
    C = C -1
    fin mientras
    si cont>2 entonces
    escriba"El numero no es primo"
    fin si
    si cont<3 entonces
    escriba"El numero es primo"
    fisi
    fin

    Ahora les digo como hice.. Los numeros primos se pueden dividir entre uno mismo o entre el 1, lo cual convierte la cantidad de divisiones exactas a dos veces, entonces, si dividiendo por sus numeros anteriores hay mas de dos divisiones exactas no es primo.
    Espero que les sirva de alguna ayuda.

      • 8,828
      • mensajes
      • miembro desde
      • 27/11/07
    16/02/2011
    #25 Re: Saber cuando un numero es o no primo

    Una función mínima en C que retorna 0 si el número no es primo y 1 si es primo:

    int primo(int n)
    {
    int i;
    for (i = 2; i * i <= n; i++)
    if (n % i == 0)
    return 0;
    return 1;
    }

    Es realmente molesto ver que las soluciones propuestas no usan una función y se van en cosas irrelevantes al tema, tales como leer el número, mostrar "Primo", etc.

    a Heaven-Might le gusta esto.
      • 2
      • mensajes
      • miembro desde
      • 28/06/08
    14/05/2011
    #26 Re: Saber cuando un numero es o no primo

    y se puede comprobar? tendrias q hacer los pasos de induccion matematica para comprobarlo, y yo mientras tanto puedo comprobar q NO, por ej.: 119 no es divisible ni por 2, ni por 3, ni por 5, sin embargo es divisible por 7, ademas de 119 y 1 (NO es primo)

      • 1,097
      • mensajes
      • miembro desde
      • 27/02/11
    14/05/2011
    #27 Re: Saber cuando un numero es o no primo

    La función de "PRIMO" es aún más óptima de esta manera

    Código:
    int PRIMO(int N)
        {
            int DIVISOR , PRIMO = 1;
                  for( DIVISOR = 2; DIVISOR <= sqrt(N) && PRIMO ; DIVISOR++ )
                           if ( ! (N % DIVISOR) )
                                PRIMO = 0 ;
            return PRIMO;
        }
    Y se puede usar así.

    Código:
    #include <stdio.h>
    #include <math.h>
    
    int PRIMO(int N);
    
    void main(void)
    
        {
          int VALOR;
          scanf("%d",&VALOR);
          if(PRIMO(VALOR))
               printf("PRIMO");
          else
              printf("NO PRIMO");
          fflush(stdin);
    
          getchar();
       }
    
    int PRIMO(int N)
        {
            int DIVISOR , PRIMO = 1;
                  for( DIVISOR = 2; DIVISOR <= sqrt(N) && PRIMO ; DIVISOR++ )
                           if ( ! (N % DIVISOR) )
                                PRIMO = 0 ;
            return PRIMO;
        }
    De ésta manera el algoritmo al sacar la raíz cuadrara y verificar si es menor o igual al divisor y fijarse que si ya encontramos un divisor (PRIMO=0), se mantenga en el for.

    De esa manera si yo pongo "99", no recorre los 99 números si con saber que al dividirlo por 2 ya sé que no es primo.
      • 8,828
      • mensajes
      • miembro desde
      • 27/11/07
    17/05/2011
    #28 Re: Saber cuando un numero es o no primo

    Correcto, Heaven-might, pero yo dije mínima, no óptima. Quise mostrar la función más simple posible
    La tuya tampoco es óptima, porque por ejemplo a partir del divisor 2 podría saltear los divisores pares.
    Y notá que en mi función estoy haciendo lo mismo que en la tuya usando i * i <= n en reemplazo de usar raíz cuadrada.

      • 8,828
      • mensajes
      • miembro desde
      • 27/11/07
    17/05/2011
    #29 Re: Saber cuando un numero es o no primo
    Cita Escrito por frapeti Ver mensaje
    y se puede comprobar? tendrias q hacer los pasos de induccion matematica para comprobarlo, y yo mientras tanto puedo comprobar q NO, por ej.: 119 no es divisible ni por 2, ni por 3, ni por 5, sin embargo es divisible por 7, ademas de 119 y 1 (NO es primo)
    ¿A quién le estás contestando?
      • 97
      • mensajes
      • miembro desde
      • 16/12/06
    22/05/2013
    #30 Re: Saber cuando un numero es o no primo
    Cita Escrito por Masiosare Ver mensaje
    En una clase de matemáticas me enseñaron (y se puede comprobar) que un número es divisible entre 2, divisible entre 3, divisible entre 5, o primo.

    Con esta regla se puede sacar un algoritmo muy sencillo para esto (los guiones bajos son para hacer sangría nomás, es que no me pone los espacios al principio de la linea):

    Código:
    inicio
    leer n
    si (n % 2 <> 0) entonces
    _si (n % 3 <> 0) entonces
    __si (n % 5 <> 0) entonces
    ___escribir "'n' es número primo"
    __fin si
    _fin si
    fin si
    escribir "'n' no es número primo".
    fin

    y de hecho podrías ponerlo en una sola sentencia if en caso de que solamente quieras determinar si es primo o no. Por ejemplo en C/C++:

    Código:
    if ( (n%2) || (n%3) || (n%5) )
     cout<<"El número no es primo"
    else
     cout<<"El número no es primo";
    Hola! Y que pasa si n=2?
Primer 1234 Último
IR ARRIBA