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

Ejemplo en C

Este es un ejemplo de un programa que obtiene números primos de menor a mayor en lenguaje C, compilado con Borland C++ Compiler version 5.5:

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int main(int argc,char *argv[],long f[],long g[]){
    char a; long c, t, n, ban;
    f[1] = g[1] = 5; n = 1; t = 0;
    printf("desea ingresar un numero primo? S/N\n");
    a = getch();
    a = toupper(a);
    if (a != 'S')
        exit(0);
    else
        printf("2\n");
    printf("desea ingresar un numero primo? S/N\n");
    a = getch();
    a = toupper(a);
    if (a != 'S')
        exit(0);
    else
        printf("3\n");
    for (a = 'S'; a == 'S'; ){
        ban=0;
        for (c = 1; ((f[c] <= (int)sqrt(6 * n - 1)) && (ban == 0));c++)
            if (((6 * n - 1) % f[c]) == 0)
                ban = 1;
        if (ban == 0){
            t++;
            g[t] = f[t] = 6 * n - 1;
            printf("desea ingresar un numero primo? S/N\n");
            a = getch();
            a = toupper(a);
            if(a != 'S')
                exit(0);
            else
                printf("%d\n",g[t]);
        }
        ban = 0;
        for (c = 1; ((f[c] <= (int)sqrt(6 * n + 1)) && (ban == 0)); c++)
            if (((6 * n + 1) % g[c]) == 0)
                ban = 1;
        if (ban == 0) {
            t++;
            g[t] = 6 * n + 1;
            printf("desea ingresar un numero primo? S/N\n");
            a = getch();
            a = toupper(a);
            if (a != 'S')
                exit(0);
            else
                printf("%d\n", g[t]);
        }
        n++; 
    }
    return 0;
}

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\}$

Propiedades algebraicas y aritméticas para extender el algoritmo y reducir aún más el tiempo de búsqueda:

• $6\cdot n-1=(6\cdot m-1)\cdot p$ tal que n y m pertenecen a los naturales y p pertenece al conjunto de los números primos.
• $30\cdot n+11\subseteq 6\cdot m-1$ a partir de n=1 y m=7.
• $(6\cdot n-1)^{r}=(6\cdot m-1)^{t}\cdot p$ tal que n y m pertenecen a los naturales y p pertenece al conjunto de los números primos; con r menor o igual a t tal que r y t pertenecen a los naturales.
• $(30\cdot n+11)^{r}\subseteq (6\cdot m-1)^{t}$ a partir de n=1 y m=7; con r menor o igual a t tal que r y t pertenecen a los naturales.
• Esta expresiones de potencias se pueden emplear en la expresión generalizada mencionada anteriormente.