Implementación de algoritmos de teoría de números/Números primos
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.