Skip to main content
Se corrige posición de time y se cambia iteración para iniciar en 3 y no en 2
Origen Enlace
from threading import Thread
import time
import math

inicio = time.time()

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

test_number = int(input("Ingrese un valor numérico para testear si es primo o no: "))

inicio = time.time()
msg_primo = "primo"
msg_no_primo = "no primo"

# si el valor introducido es 2, es primo
if test_number == 2
  print(msg_primo)
  exit(0)

# si el valor introducido es par o menor que 2, entonces no es primo.
if test_number < 2 or test_number % 2 == 0:
  print(msg_no_primo)
  exit(0)

# podemos pedir la cantidad de hilos por consola
# number_of_threads = max(int(input("Ingrese el número de hilos: ")), 1)
number_of_threads = 4

# valor hasta el cual realizaremos divisiones
upper_limit = math.floor(math.sqrt(test_number))
print(f"upper_limit: {upper_limit}")

# dividimos las tareas
task_size = math.floor((upper_limit - 23) / number_of_threads)

# inicializamos las listas para almacenar las tareas y resultados
tasks = [None] * number_of_threads
result = [None] * number_of_threads

# asignamos las tareas a cada hilo y lo iniciamos
for i in range(0, number_of_threads):
  start = 23 + (i * task_size)
  end = start + task_size - 1 if i < number_of_threads - 1 else upper_limit
  tasks[i] = Thread(target=is_prime, args=(test_number, start, end, result, i))
  tasks[i].start()

# esperamos que cada hilo termine su trabajo antes de proseguir con el resultado
for i in range(len(tasks)):
  tasks[i].join()

# mostramos el mensaje adecuado
print(msg_no_primo if False in result else msg_primo)

fin = time.time()
print(f"concurrente: {fin-inicio}")
Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 23 hasta 7381573816
dividiendo87178291197 desdees 73816divisible hastaentre 1476293
dividiendo desde 14763073817 hasta 221443147630
87178291197dividiendo esdesde divisible147631 entrehasta 3221444
dividiendo desde 221444221445 hasta 295259
87178291197 es divisible entre 151269
no primo
concurrente: 110.270684242248535034451961517333984
Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 23 hasta 295259
87178291197 es divisible entre 3
no primo
concurrente: 70.3177218437194820004985332489013672

Claramente, usando 1 sólo Hilo hemos obtenido el resultado en menos tiempo. Esto es porque la función que realiza las operaciones de división ha sido optimizada para detener el bucle al momento de conseguir un divisor, y en este caso, el divisor es 3, es decir, hemos realizado sólo 1 iteración para encontrar un divisor.

from threading import Thread
import time
import math

inicio = time.time()

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

test_number = int(input("Ingrese un valor numérico para testear si es primo o no: "))

msg_primo = "primo"
msg_no_primo = "no primo"

# si el valor introducido es 2, es primo
if test_number == 2
  print(msg_primo)
  exit(0)

# si el valor introducido es par o menor que 2, entonces no es primo.
if test_number < 2 or test_number % 2 == 0:
  print(msg_no_primo)
  exit(0)

# podemos pedir la cantidad de hilos por consola
# number_of_threads = max(int(input("Ingrese el número de hilos: ")), 1)
number_of_threads = 4

# valor hasta el cual realizaremos divisiones
upper_limit = math.floor(math.sqrt(test_number))
print(f"upper_limit: {upper_limit}")

# dividimos las tareas
task_size = math.floor((upper_limit - 2) / number_of_threads)

# inicializamos las listas para almacenar las tareas y resultados
tasks = [None] * number_of_threads
result = [None] * number_of_threads

# asignamos las tareas a cada hilo y lo iniciamos
for i in range(0, number_of_threads):
  start = 2 + (i * task_size)
  end = start + task_size - 1 if i < number_of_threads - 1 else upper_limit
  tasks[i] = Thread(target=is_prime, args=(test_number, start, end, result, i))
  tasks[i].start()

# esperamos que cada hilo termine su trabajo antes de proseguir con el resultado
for i in range(len(tasks)):
  tasks[i].join()

# mostramos el mensaje adecuado
print(msg_no_primo if False in result else msg_primo)

fin = time.time()
print(f"concurrente: {fin-inicio}")
Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 2 hasta 73815
dividiendo desde 73816 hasta 147629
dividiendo desde 147630 hasta 221443
87178291197 es divisible entre 3
dividiendo desde 221444 hasta 295259
87178291197 es divisible entre 151269
no primo
concurrente: 11.270684242248535
Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 2 hasta 295259
87178291197 es divisible entre 3
no primo
concurrente: 7.317721843719482

Claramente, usando 1 sólo Hilo hemos obtenido el resultado en menos tiempo. Esto es porque la función que realiza las operaciones de división ha sido optimizada para detener el bucle al momento de conseguir un divisor, y en este caso, el divisor es 3, es decir hemos realizado sólo 1 iteración para encontrar un divisor.

from threading import Thread
import time
import math

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

test_number = int(input("Ingrese un valor numérico para testear si es primo o no: "))

inicio = time.time()
msg_primo = "primo"
msg_no_primo = "no primo"

# si el valor introducido es 2, es primo
if test_number == 2
  print(msg_primo)
  exit(0)

# si el valor introducido es par o menor que 2, entonces no es primo.
if test_number < 2 or test_number % 2 == 0:
  print(msg_no_primo)
  exit(0)

# podemos pedir la cantidad de hilos por consola
# number_of_threads = max(int(input("Ingrese el número de hilos: ")), 1)
number_of_threads = 4

# valor hasta el cual realizaremos divisiones
upper_limit = math.floor(math.sqrt(test_number))
print(f"upper_limit: {upper_limit}")

# dividimos las tareas
task_size = math.floor((upper_limit - 3) / number_of_threads)

# inicializamos las listas para almacenar las tareas y resultados
tasks = [None] * number_of_threads
result = [None] * number_of_threads

# asignamos las tareas a cada hilo y lo iniciamos
for i in range(0, number_of_threads):
  start = 3 + (i * task_size)
  end = start + task_size - 1 if i < number_of_threads - 1 else upper_limit
  tasks[i] = Thread(target=is_prime, args=(test_number, start, end, result, i))
  tasks[i].start()

# esperamos que cada hilo termine su trabajo antes de proseguir con el resultado
for i in range(len(tasks)):
  tasks[i].join()

# mostramos el mensaje adecuado
print(msg_no_primo if False in result else msg_primo)

fin = time.time()
print(f"concurrente: {fin-inicio}")
Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 3 hasta 73816
87178291197 es divisible entre 3
dividiendo desde 73817 hasta 147630
dividiendo desde 147631 hasta 221444
dividiendo desde 221445 hasta 295259
87178291197 es divisible entre 151269
no primo
concurrente: 0.034451961517333984
Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 3 hasta 295259
87178291197 es divisible entre 3
no primo
concurrente: 0.0004985332489013672

Claramente, usando 1 sólo Hilo hemos obtenido el resultado en menos tiempo. Esto es porque la función que realiza las operaciones de división ha sido optimizada para detener el bucle al momento de conseguir un divisor, y en este caso, el divisor es 3, es decir, hemos realizado sólo 1 iteración para encontrar un divisor.

Origen Enlace

Tal como planteo en mi comentario, una forma de lograr lo que te propones es dividir el proceso de división del valor que estás probando entre diferentes etapas, asignando a cada hilo una parte del proceso de división en la búsqueda de un factor primo para el número dado.

Algoritmo

Un algoritmo para determinar si un valor dado es un número primo o no viene dado por la división del mismo entre todos los valores primos menores a la raíz cuadrada número dado. Esto requiere conocer de antemano los valores primos anteriores. Por lo cual, lo que usualmente se hace, sin tener estos datos previos, es dividir el valor por todos los números naturales entre 2 y la raíz cuadrada del número dado.

Se hace hasta la raiz cuadrada porque no queremos encontrar todos los divisores, queremos hallar al menos uno. Si no encontramos ningún divisor desde 2 hasta la raíz cuadrada del número, no encontraremos ninguno por encima del valor de la raíz cuadrada.

Hilos

Ahora, la tarea de división es la que vamos a repartir entre diferentes hilos, dándole de ser posible, la misma cantidad de divisiones a procesar a cada hilo. Para ello podemos dividir la cantidad de números que hay entre 2 y la raiz cuadrada del número dado entre la cantidad de hilos. Esto nos dará la cantidad de números por los cuales ha de dividir cada hilo.

Por ejemplo, si queremos determinar si el valor 101 es primo o no, primero hallamos su raiz cuadrada, la cual es aproximadamente 10. Esto es, el entero más cercano por defecto a la raíz cuadrada real.

Entonces desde 3 hasta 10 hacemos la división entre 4 hilos, quedando las tareas asignadas de la siguiente forma:

  • Primer Hilo: divide 101 entre cada número en el rango [3, 5)
  • Segundo Hilo: divide 101 entre cada número en el rango [5, 7)
  • Tercer Hilo: divide 101 entre cada número en el rango [7, 9)
  • Cuarto Hilo: divide 101 entre cada número en el rango [9, 10] (nótese que el último hilo realiza una división en la que se incluye el último valor del rango)

Entonces, nuestra función que determina si un valor es Primo o no, debe recibir el valor dado, el inicio y fin del rango para realizar las divisiones. Por ejemplo, la siguiente función realiza un división del valor recibido entre todos los números del rango [start, end] (end incluído) y devuelve un valor booleano indicando si se ha encontrado un divisor del número en dicho rango:

def is_prime(n, start, end):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  return prime

Resultado

Ahora, dado que cada hilo llevará a cabo su tarea de forma independiente, necesitamos una forma de saber si alguno de ellos ha encontrado un divisor del número o no. Existen muchas formas de obtener el resultado, yo usaré una muy sencilla que se basa en añadir a una lista el resultado de cada Hilo. Luego una simple inspección de dicha lista nos dirá si el número analizado es Primo o no.

Por ejemplo, la siguiente función recibe 5 parámetros: n, start, end, result e index. Las primeras 3 ya las conocemos, pero las 2 adicionales simplemente son una referencia a la lista para almacenar el resultado y el índice en el que pondremos dicho resultado.

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

Es practimanete igual a la primera función vista, pero en vez de devolver el resultado, lo almacenamos en una lista.

Por último, armamos todo para que nuestros hilos se encarguen de calcular si un valor es Primo, donde cada Hilo recibe una parte de las divisiones que debe hacer.

El siguiente código debería funcionar en python 3.x:

from threading import Thread
import time
import math

inicio = time.time()

def is_prime(n, start, end, res, index):
  prime = True
  print(f"dividiendo desde {start} hasta {end}")
  for divisor in range(start, end + 1):
    if n % divisor == 0:
      print(f"{n} es divisible entre {divisor}")
      prime = False
      break
  res[index] = prime

test_number = int(input("Ingrese un valor numérico para testear si es primo o no: "))

msg_primo = "primo"
msg_no_primo = "no primo"

# si el valor introducido es 2, es primo
if test_number == 2
  print(msg_primo)
  exit(0)

# si el valor introducido es par o menor que 2, entonces no es primo.
if test_number < 2 or test_number % 2 == 0:
  print(msg_no_primo)
  exit(0)

# podemos pedir la cantidad de hilos por consola
# number_of_threads = max(int(input("Ingrese el número de hilos: ")), 1)
number_of_threads = 4

# valor hasta el cual realizaremos divisiones
upper_limit = math.floor(math.sqrt(test_number))
print(f"upper_limit: {upper_limit}")

# dividimos las tareas
task_size = math.floor((upper_limit - 2) / number_of_threads)

# inicializamos las listas para almacenar las tareas y resultados
tasks = [None] * number_of_threads
result = [None] * number_of_threads

# asignamos las tareas a cada hilo y lo iniciamos
for i in range(0, number_of_threads):
  start = 2 + (i * task_size)
  end = start + task_size - 1 if i < number_of_threads - 1 else upper_limit
  tasks[i] = Thread(target=is_prime, args=(test_number, start, end, result, i))
  tasks[i].start()

# esperamos que cada hilo termine su trabajo antes de proseguir con el resultado
for i in range(len(tasks)):
  tasks[i].join()

# mostramos el mensaje adecuado
print(msg_no_primo if False in result else msg_primo)

fin = time.time()
print(f"concurrente: {fin-inicio}")

Con esto habrás realizado la tarea usando Hilos, pero como muy bien te ha comentado @CandidMoe, esto no hará que tu tarea se ejecute más rápido, inlcuso puede pasar lo contrario.

Por ejemplo, si queremos averiguar si el siguiente número es Primo: 87178291197, usando los 4 hilos, tendremos el siguiente resultado (dependerá de la potencia del equipo en el que se ejecute):

Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 2 hasta 73815
dividiendo desde 73816 hasta 147629
dividiendo desde 147630 hasta 221443
87178291197 es divisible entre 3
dividiendo desde 221444 hasta 295259
87178291197 es divisible entre 151269
no primo
concurrente: 11.270684242248535

Se observa que los 4 hilos han realizado su trabajo y en 2 de ellos se ha obtenido un divisor, por lo tanto el número no es primo.

Pero si ejecutamos el mismo programa con sólo 1 Hilo, el resultado se puede ver parecido al siguiente:

Ingrese un valor numérico para testear si es primo o no: 87178291197
upper_limit: 295259
dividiendo desde 2 hasta 295259
87178291197 es divisible entre 3
no primo
concurrente: 7.317721843719482

Claramente, usando 1 sólo Hilo hemos obtenido el resultado en menos tiempo. Esto es porque la función que realiza las operaciones de división ha sido optimizada para detener el bucle al momento de conseguir un divisor, y en este caso, el divisor es 3, es decir hemos realizado sólo 1 iteración para encontrar un divisor.

En cambio al usar más de un Hilo, cada uno realiza el trabajo asignado, y aunque el primero ya ha obtenido el resultado en la primera iteración, los demás continuarán su trabajo, incrementándose el tiempo de ejecución.

Existen formas de evitar esto, pero eso estaría fuera del alcance de tu pregunta.

Espero que esto te ayude a resolver el problema.