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

Dado un entero positivo N, la tarea es escribir un programa en Python para verificar si el número es primo o no.
Definición: Un número primo es un número natural mayor que 1 que no tiene más divisores positivos que 1 y él mismo. Los primeros números primos son {2, 3, 5, 7, 11, ….}.

Ejemplos: 

Entrada:  n = 11
Salida: verdadero

Entrada:  n = 15
Salida: falso

Entrada:  n = 1
Salida: falso

La idea para resolver este problema es iterar a través de todos los números desde 2 hasta (N/2) usando un bucle for y para cada número verificar si divide a N. Si encontramos algún número que divide, devolvemos falso. Si no encontramos ningún número entre 2 y N/2 que divida a N, significa que N es primo y devolveremos True.

A continuación se muestra el programa de Python para comprobar si un número es primo: 

# Python program to check if
# given number is prime or not
  
num = 11
  
# If given number is greater than 1
if num > 1:
  
    # Iterate from 2 to n / 2
    for i in range(2, int(num/2)+1):
  
        # If num is divisible by any number between
        # 2 and n / 2, it is not prime
        if (num % i) == 0:
            print(num, "is not a prime number")
            break
    else:
        print(num, "is a prime number")
  
else:
    print(num, "is not a prime number")

11 is a prime number

Método optimizado 
Podemos hacer las siguientes optimizaciones: 

En lugar de verificar hasta n, podemos verificar hasta √n porque un factor mayor de n debe ser un múltiplo de un factor menor que ya se haya verificado.

Ahora veamos el código para el primer método de optimización (es decir, verificar hasta √n)

from math import sqrt
# n is the number to be check whether it is prime or not
n = 1
  
# no lets check from 2 to sqrt(n)
# if we found any facto then we can print as not a prime number
  
# this flag maintains status whether the n is prime or not
prime_flag = 0
  
if(n > 1):
    for i in range(2, int(sqrt(n)) + 1):
        if (n % i == 0):
            prime_flag = 1
            break
    if (prime_flag == 0):
        print("true")
    else:
        print("false")
else:
    print("false")

false

El algoritmo se puede mejorar aún más observando que todos los números primos son de la forma 6k ± 1, con la excepción de 2 y 3. Esto se debe a que todos los números enteros se pueden expresar como (6k + i) para algún número entero k y para i = – 1, 0, 1, 2, 3 o 4; 2 divide (6k + 0), (6k + 2), (6k + 4); y 3 divide (6k + 3). Entonces, un método más eficiente es probar si n es divisible por 2 o 3, luego verificar todos los números de la forma 6k ± 1. (Fuente: wikipedia )