El algoritmo más simple, para determinar si un número es primo o compuesto, es hacer una serie de divisiones sucesivas del número, con todos los números menores que él, si alguna división da como residuo 0 o es divisible con el número entonces es compuesto en caso contrario es primo.

Este algoritmo es muy bueno para determinar números primos muy pequeños como 13 o el 29, pero cuando necesitamos saber si un número como 593 es primo, entonces el algoritmo o pasos anteriormente explicados se convertirán en una tarea muy tediosa de realizar y obviamente llevará tiempo hacerlo. El siguiente algoritmo es el más conocido para hallar un número primo tan grande como el 549, pero para números mayores de 1000 se recomienda usar una computadora o una calculadora que permita determinar si un número es primo o no.

El algoritmo consiste en los siguientes pasos a seguir:

1. Primero verificar si es divisible con 2,3 y 5. Si es divisible entonces es compuesto.
2. Segundo hallar la raíz cuadrada del número, si la raíz es exacta entonces el número es compuesto.
3. Si la raíz es inexacta, entonces se prueba si es divisible con todos los números primos menores que la raíz obtenida, excepto 2, 3 y 5.
4. Si es divisible con algún número primo entonces es compuesto, en caso contrario es primo.

Ejemplo.

Verificar si 457 es un número primo.

1. Evidentemente 457 no es divisible con 2,3 y 5
2. La raíz cuadrada de 457 es 21, con residuo 16
   
   
   
   
3. Se verifica si es divisible con todos los números primos menores que 21.
   Los números primos menores que 21 son: 7,11,13,17,19
   con 7, no es divisible.
   con 11, no es divisible.
   con 13, no es divisible.
   con 17, no es divisible.
   con 19, no es divisible.
   Como no es divisible con 7,11,13,17 y 19 entonces 457 es un número primo.