Java Programa para comprobar si un número es primo con un ejemplo

¿Qué es un número primo?

Un número primo es un número natural mayor que 1 que solo es divisible por 1 o por sí mismo. Por ejemplo, 11 solo es divisible por 1 o por sí mismo. Otros números primos son 2, 3, 5, 7, 11, 13, 17, y la secuencia continúa indefinidamente.

Un número mayor que 1 que no es primo se llama número compuesto, porque se puede formar a partir de factores más pequeños. El valor 9 es compuesto porque es divisible exactamente por 3, y el 15 es compuesto porque es divisible exactamente por 3 y por 5.

Nota: 0 y 1 no son números primos. 2 es el único número primo par, y los valores negativos nunca se consideran primos.

Cómo comprobar si un número es primo en Java

La estrategia de verificación consiste en una sencilla prueba de divisibilidad. Se toma el valor candidato, se divide sucesivamente entre cada entero menor y se examina el resto que devuelve el operador módulo. Un resto de cero demuestra que existe un divisor, lo que descarta inmediatamente el número.

Lógica del programa:

• Necesitamos dividir un número dado, por ejemplo 17, entre los valores del 2 al 17 y comprobar el resto. Si el resto es 0, el número no es primo.
• Ningún número es divisible por más de la mitad de sí mismo. Entonces necesitamos loops a través de sólo numberToCheck/2. Si la entrada es 17, la mitad es 8.5 y el bucle iterará a través de los valores del 2 al 8.
• Si numberToCheck es completamente divisible por otro número, el indicador isPrime se establece en false y se sale del bucle.

Dos Java Las características sustentan todo el algoritmo. El operador módulo % devuelve el resto de una división entera y el break La instrucción detiene el bucle tan pronto como se conoce la respuesta, por lo que no se ejecutan iteraciones innecesarias.

Java Programa para comprobar si un número es primo o no.

El programa que se muestra a continuación asigna el valor 17 a la variable numberToCheck e imprime cada paso de la división, para que puedas seguir el razonamiento línea por línea. El código es editable, así que cambia el valor y ejecútalo de nuevo con un número compuesto como 21 para ver el resultado opuesto.

public class PrimenumberToCheckCheck {

 public static void main(String[] args) {
  int remainder;
  boolean isPrime=true;
  int numberToCheck=17; // Enter the number you want to check for prime

  //Loop to check whether the number is divisible by any number other than 1 and itself
  for(int i=2;i<=numberToCheck/2;i++)
  {
   //number is divided by i
            remainder=numberToCheck%i;
            System.out.println(numberToCheck+" Divided by "+ i + " gives a remainder "+remainder);

       //if remainder is 0 then the number is not prime and we break the loop. Else continue the loop
     if(remainder==0)
     {
        isPrime=false;
        break;
     }
  }
  // Check value true or false, if isPrime is true then the number is prime otherwise not prime
  if(isPrime)
     System.out.println(numberToCheck + " is a Prime number");
  else
     System.out.println(numberToCheck + " is not a Prime number");
    }
  }

Rendimiento esperado:

17 Divided by 2 gives a remainder 1
17 Divided by 3 gives a remainder 2
17 Divided by 4 gives a remainder 1
17 Divided by 5 gives a remainder 2
17 Divided by 6 gives a remainder 5
17 Divided by 7 gives a remainder 3
17 Divided by 8 gives a remainder 1
17 is a Prime number

El bucle se detiene en 8 porque 17 dividido entre 2 es igual a 8 en aritmética de enteros. Como ningún resto fue cero, el indicador isPrime mantiene su valor inicial de verdadero y la condición final imprime el resultado positivo.

Verificación optimizada de números primos mediante el método de la raíz cuadrada.

Dividir hasta la mitad del número es correcto, pero ineficiente. Si un número n tiene un divisor mayor que su raíz cuadrada, el codivisor correspondiente debe ser menor que la raíz cuadrada, por lo que ya se habría encontrado. Por lo tanto, comprobar hasta √n produce el mismo resultado con muchas menos iteraciones.

public class PrimeCheckOptimized {

    public static boolean isPrime(int n) {
        // 0, 1 and negative values are never prime
        if (n <= 1) {
            return false;
        }
        // 2 is the only even prime number
        if (n == 2) {
            return true;
        }
        if (n % 2 == 0) {
            return false;
        }
        // test only odd divisors up to the square root
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] samples = {1, 2, 9, 17, 97};
        for (int value : samples) {
            System.out.println(value + " is prime: " + isPrime(value));
        }
    }
}

Salida:

1 is prime: false
2 is prime: true
9 is prime: false
17 is prime: true
97 is prime: true

La condición i * i <= n Evita una llamada a Math.sqrt de punto flotante, y el paso de 2 omite todos los divisores pares. Para un valor como 1,000,003, el bucle básico realiza aproximadamente 500,000 iteraciones, mientras que esta versión realiza menos de 500.

Comprobar si un número primo ha sido introducido por el usuario.

La entrada de datos codificada es conveniente para demostraciones, pero los ejercicios reales suelen requerir la entrada de datos mediante teclado. La clase Scanner lee un número entero de la consola y lo pasa al mismo método isPrime.

import java.util.Scanner;

public class PrimeCheckUserInput {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int number = sc.nextInt();

        boolean isPrime = number > 1;
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                break;
            }
        }

        System.out.println(number + (isPrime ? " is a Prime number" : " is not a Prime number"));
        sc.close();
    }
}

Ejecución de ejemplo:

Enter a number: 29
29 is a Prime number

Errores comunes al escribir un programa de números primos

La mayoría de los errores de envío se deben a valores límite, no al bucle principal. La siguiente lista incluye los errores más frecuentes en el código para principiantes.

1. Comenzando el bucle en 1: Todo número entero es divisible por 1, por lo que el indicador se establece en falso inmediatamente y el programa informa que ningún número es primo.
2. Considerando 1 como primo: El valor 1 tiene solo un divisor, por lo que no cumple con la definición de dos divisores y debe devolver falso.
3. Omitiendo la instrucción break: El programa sigue devolviendo la respuesta correcta, pero continúa iterando después de que se conoce el veredicto, lo que hace perder tiempo con entradas grandes.
4. El uso de i <= n como el límite: El número siempre se divide a sí mismo, por lo que el bucle debe detenerse antes de llegar a n.
5. Comparado con = en lugar de ==: Un solo signo de igual asigna un valor en lugar de comprobarlo, lo que produce un error de compilación en la condición if.

Comparación de métodos de verificación de números primos

Elija el método que mejor se adapte al tamaño de la entrada y a si se debe probar un solo valor o un rango completo.

Cuando se debe clasificar un rango completo en lugar de un solo valor, el tamiz es mucho más eficiente. Nuestro programa complementario para encontrar Prima Numbers de 1 a 100 demuestra ese patrón. Para ejercicios relacionados basados ​​en bucles, revise el Serie de Fibonacci en Java, Java programa de palíndromos, y Bubble Ordenar algoritmo en JavaLos principiantes que necesiten un repaso sobre cómo declarar la bandera y el contador deberían leer sobre Java las variables en general Java tutoriales.

Preguntas Frecuentes