0

Me piden mejorar este código teniendo en cuenta que:

  • El único numero primo que es par es el 2.
  • Un numero n no puede tener divisores mayores que n/2.
    public static boolean esPrimo(int numero){
        
        boolean esPrimo=true;
        for(int i=2;(i<numero)&&esPrimo;i++){
            if(numero%i==0){
                esPrimo=false;
            }
        }
        return esPrimo;

    }
    public static void main(String[] args) {
        Scanner tec = new Scanner(System.in);
        int numero=0;
        System.out.print("Introduce un numero entero: ");
        numero=tec.nextInt();
        for(int i=1;i<=numero;i++){
            if(esPrimo(i)){
                System.out.println(i);
            }
        }
        tec.close();
    }

¿Por que será más eficiente el programa teniendo en cuenta esas dos cosas? Entiendo que tiene una explicación matemática pero no consigo dar con ella.

1
  • 1
    1) No tienes que recorrer divisores sino sólo validar si es par y es mayor que 2. Te ahorras tiempo. 2) Es más barato validar divisores hasta n/2 y no seguir probando si otros números hacen división entera. Si lo piensas, tiene sentido. Si estás revisando a 33, no hay ningún entero mayor a 16 que puedas probar, que esté entre 1 y 2, y que divida a 33. Y así... siempre piensas en iteraciones que te vas a ahorrar.
    – Alfabravo
    Commented el 11 nov. 2022 a las 17:01

1 respuesta 1

1

Dado un número N, el bucle comprueba todos los números desde 2 hasta N-1.

  • Sabiendo que los pares mayores que dos no son primos, puedes ahorrarte la mitad de las comprobaciones (compruebas si N es par antes de entrar al bucle y luego compruebas usando

    for (int i=3, i< numero; i+=2) {...}
    
  • Sabiendo que el divisor más grande que puede tener un número N (que no sea él mismo) es N/2, puedes de nuevo reducir la búsqueda:

    int limite = (int)numero / 2;
    for (int i=3, i< limite; i+=2) {...}
    

Pero puedes ir más allá: Si un número no es primo, tiene dos divisores*, A y B distintos de 1 y de si mismo, porque

N / A = B

implica que

N / B = A

Por lo que si encuentras A, no necesitas comprobar B.

El asterisco que he puesto es porque hay dos posibilidades: A != B y A == B, en cuyo caso sólo tiene un divisor que coincide con el resultado de la división:

O uno es mayor que otro o los dos son el mismo (25 es 5 * 5, mientras que 15 es 3 * 5.

Por tanto encontrás uno antes que otro o encontrás que los dos son el mismo... por lo que en lugar de mirar hasta N/2 puedes mirar "sólo" hasta la raíz cuadrada de ese número. Es decir, si quieres comprobar si 9997 es primo, con mirar hasta 100 sería suficiente.

1
  • Gracias por la explicación, lo entendí perfectamente, y agradezco esa siguiente mejora, la tendré en cuenta.
    – beatkapo
    Commented el 11 nov. 2022 a las 18:21

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.