Implementación de algoritmos de teoría de números/Números primos

Descripción formal

Un algoritmo que busca números primos dentro de un rango se basa en el principio de que todo número primo mayor que 3 se encuentra en el conjunto:

$\mathbb {P} _{>3}\subset \left\{6\cdot n\pm 1\right\}\qquad n\in \mathbb {N}$

es decir, pertenece como subconjunto al conjunto de todos los números naturales no divisibles por 2 y 3. Para generar un número primo de la forma $6\cdot n\pm 1$, solo basta recorrer (e ir dividiendo) por todos los números primos que se generan en las iteraciones anteriores del algoritmo, ahorrándose tiempo en la búsqueda. Si el resto de la división es distinto de cero en toda la fase de iteración, ese número será primo, en cambio si el resto es 0 en alguna fase de la iteración, el número es compuesto y se descarta.

Optimizaciones

Extensión de la expresión de números no divisibles por $p_{i}$ con $p_{i},p_{j}\in \mathbb {P} ;n\in \mathbb {N}$:

$6\cdot n\pm \left\{1\right\}$

$30\cdot n\pm \left\{1,7,11,13\right\}$

$\vdots$

$p_{i}\#\cdot n\pm \left\{1,\ p_{j}\quad :p_{i}<p_{j}<{\frac {p_{i}\#}{2}}\right\}$

Implementación en distintos lenguajes de programación

En C

Este es un ejemplo de un programa que obtiene los primeros 1000 números primos de menor a mayor en lenguaje C, compilado con Visual Studio 2022:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define TRUE   1
#define FALSE  0

#define MAX_PRIMOS 1000

int main(int argc, char* argv[]) 
{
    unsigned long c, t, n, detect1, detect_1;
    unsigned long f[65536] = { 0 };

    n = 1; 
	t = 3;
	
    f[0] = 2;
    f[1] = 3;
    f[2] = 5;

	printf("%u, %u, ", f[0], f[1]);

	for (n = 1; n <= MAX_PRIMOS; n++) 
	{
		detect_1 = FALSE;
		detect1  = FALSE;

		for (c = 2; f[c] <= (unsigned)sqrt(6 * n + 1); c++)
		{
			if (((6 * n - 1) % f[c]) == 0)
				detect_1 = TRUE;

			if (((6 * n + 1) % f[c]) == 0)
				detect1 = TRUE;

			if (detect_1 && detect1)
				break;
		}

		if (!detect_1)
		{
			printf("%u, ", (6*n - 1));
			f[t++] = 6 * n - 1;
		}

		if (!detect1)
		{
			printf("%u, ", (6 * n + 1));
			f[t++] = 6 * n + 1;
		}
    }

	printf("\n");
	system("PAUSE");

    return 0;
}