Otra manera de obtener los números primos mayores o iguales que $2$ y menores que $1000$. Algoritmo de Eratóstenes

Obtención de los números primos mayores o iguales que $2$ y menores que $1000$ implementado el algoritmo de la criba de Eratóstenes, escribiendo el programa correspondiente en lenguaje Python:

def criba_eratostenes(n):
    # Inicializar una lista de booleanos de tamaño n+1
    # donde cada elemento se considera inicialmente primo
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False  # 0 y 1 no son primos

    p = 2
    while p * p <= n:
        # Si primes[p] es verdadero, entonces es primo
        if primes[p]:
            # Actualizamos todos los múltiplos de p como no primos
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1

    # Recopilamos todos los números primos en una lista
    prime_numbers = [num for num, is_prime in enumerate(primes) if is_prime]
    return prime_numbers

# Encontramos los números primos entre 2 y 1000
primes = criba_eratostenes(1000)

# Imprimimos los números primos encontrados
print("Números primos entre 2 y 1000:")
print(primes)

Ponemos en marcha el programa:
Resultado:
  >>> %Run cribadeeratostenes.py
Y se obtiene el resultado: Números primos entre 2 y 1000: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

$\diamond$

¿Cómo saber si un número (el que primero se nos ocurra) es primo? ¿Cómo encontrar los números primos menores que un cierto número (pongamos que 1000)?

Aquí tenéis un algoritmo básico y el código del programa correspondiente en lenguaje Python [1]

def es_primo(numero):
    if numero < 2:
        return False
    for i in range(2, int(numero ** 0.5) + 1):
        if numero % i == 0:
            return False
    return True

# Ejemplo de uso:
numero = int(input("Ingrese un número: "))
if es_primo(numero):
    print(numero, "es un número primo.")
else:
    print(numero, "no es un número primo.")

-oOo-

Y para encontrar los números primos mayores o iguales que $2$ y menores que $1000$, podéis escribir y hacer funcionar el siguiente programa en vuestro intérprete de Python (los hay que podéis utilizar en línea, sin instalar software de desarrollo en vuestro ordenador como, por ejemplo, éste [3]: https://www.tutorialspoint.com/online_python_compiler.php):

  def es_primo(numero):
    if numero < 2:
        return False
    #la búsqueda acaba en la raíz cuadrada del número introducido más una unidad
    for i in range(2, int(numero ** 0.5) + 1):
        if numero % i == 0:
            return False
    return True

primos = []
for num in range(2, 1001):
    if es_primo(num):
        primos.append(num)

print("Números primos hasta 1000:")
print(primos)
  

Al poner en marcha el programa, a cuyo archivo le he dado el nombre de numerosprimos.py, >>> %Run numerosprimos.py
Nota: el símbolo >>> indica el prompt de la cónsola de vuestro entorno de desarrollo (fuera de línea, he utilizado el IDE Thonny [2] (habiendo instalado préviamente Python [1]), que es software libre, y es de fácil uso)
Podéis comprobar que se obtiene (rápidamente, en pocos segundos) ...
Números primos hasta 1000: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
>>> $\diamond$

-oOo-

Utilidades:

  [1] El software básico para trabajar con Python: https://www.python.org/
  [2] Un entorno de trabajo: https://thonny.org/
  [3] Un compilador en línea: https://www.tutorialspoint.com/online_python_compiler.php

Hay infinitos números primos (Euclides, siglo III a.C.)

Euclides (ca. 325 a. C.,-ca. 265 a. C.) nos dejó una elegante demostración en la proposición número 20 del libro IX de sus Elementos [Hay más números primos que cualquier cantidad propuesta de números primos], que es un bonito ejemplo del uso de la técnica de demostración por contradicción.

Obviando los números primos negativos -que no se conocían en la antigüedad, y que sí incluyo aquí-, la demostración de Euclides es como sigue (empleando ahora el lenguaje moderno): Sean $p_1,p_2,\ldots$ números primos positivos y $\mathcal{P}=\{\pm p_1,\pm p_2,\ldots\}\subset \mathbb{Z}\setminus \{-1,0,1\}$ el conjunto de todos los números primos (positivos y negativos) -números enteros distintos de $0$, $1$ y $-1$ y que no son múltiplos del resto de números enteros-, donde $p_1\ge 2$ (y $-p_1\le -2$). Tomemos como hipótesis lo contrario de lo que queremos demostrar, esto es, partimos del supuesto de que hay un número finito de números primos, siendo el $p_n$ el máximo (y $-p_n$, el mínimo) de dicho conjunto supuestamene finito. A partir de aquí, vamos a ver como llegamos enseguida a una contradicción que nos permitará negar la hipótesis de partida, con lo cual habremos demostrado justo lo contrario de lo que reza ésta, es decir, que el número de números primos es infinto.

Consideremos ahora un número entero $\alpha:=p'_1\cdot p'_2 \cdot \ldots \cdot p'_n+1$, donde cada $p'_i$ ($i=1,\ldots,n$) puede ser igual a $p_i$ o bien a $-p_i$. Como el resto de la división de dicho número entre cualesquiera de los números primos $\{\pm p_1,\pm p_2\,\ldots,\pm p_n\}$ ha de ser igual a $1$, entonces, al ser el resto distinto de $0$, $\alpha$ no puede ser múltiplo de ninguno de los números primos $\pm p_1,\pm p_2 \ldots,\pm p_n$ del conjunto finito con el que hemos hecho la hipótesis de partida, luego $\alpha$ es un nuevo número primo, tal que $|\alpha| \ge p_n$, con lo que llegamos a una contradicción, y hemos terminado. $\square$
-oOo-
Referencias:
[1]  Euclides: Elementos, Libro IX, proposición número 20