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

De Wikilibros, la colección de libros de texto de contenido libre.
Ir a la navegación Ir a la búsqueda

Ejemplo en C[editar]

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 con :

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

  • tal que n y m pertenecen a los naturales y p pertenece al conjunto de los números primos.
  • a partir de n=1 y m=7.
  • 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.
  • 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.