Código de Pascal/Turbo Pascal - Numeros Primos

Numeros Primosgráfica de visualizaciones


Pascal/Turbo Pascal

estrellaestrellaestrellaestrellaestrella(1)
Publicado el 12 de Febrero del 2006 por Frank Rafael
8.704 visualizaciones desde el 12 de Febrero del 2006. Una media de 21 por semana
Una unit(primo.pas) con tres funciones para determinar si un número es primo. También otras dos units, allprime.pas con todos los números primos desde 2 hasta 46337 y time.pas para saber el tiempo de ejecución de un programa. Y dos programas auxiliares.
OBJETIVO: Optimizar lo mejor posible la función que determina si un número es primo.
Creado con TP 7.0

Versión 1
estrellaestrellaestrellaestrellaestrella(1)

Publicado el 12 de Febrero del 2006gráfica de visualizaciones de la versión: Versión 1
8.705 visualizaciones desde el 12 de Febrero del 2006. Una media de 21 por semana
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

Si alguno de los archivos de descarga no funciona, comentanos aquí el error.




Comentarios sobre la versión: Versión 1 (1)

Frank Rafael
27 de Febrero del 2006
estrellaestrellaestrellaestrellaestrella
Hola Programadores
Ya encontré un nuevo algoritmo que es más rápido que los que están en la unit primo, este es el resultado de usar el
Teorema:
========
Para todo número primo p > 3, se tiene que p=6k+1 ó p=6k-1

Demostración:
============
Todos los entero pueden expresarse exactamente de un de las 6 posibles formas:

6k, 6k+1, 6k+2, 6k+3, 6k-2, ó 6k-1

6k es divisible por 6, por lo que no es primo

6k+2 es par, por lo que no es primo

6k+3=3(2k+1) es divisible por 3, por lo que no es primo

6k-2 es par por lo que no es primo

Por tanto, los números primos tienen que expresarse de la forma 6k+1 ó 6k-1.

Note que no todos los números de esa forma son necesariamente primos.

Implementación (seudocódigo):
=========================
PRIME (x) // x > 3

1 if x mod 6 <> 1 and x mod 6 <> 5

2 then return FALSE

3 r = SQRT(x)

4 i = 1

5 while 6*i-1 <= r do

6 if x mod (6*i-1) = 0

7 then return FALSE

8 if x mod (6*i+1) = 0

9 then return FALSE

10 i = i + 1

11 return TRUE

Notas:
=====
Tomado de:
Algoritmos
Nociones elementales en la teoría de los números

Tema por:
Ronny López Trujillo
Selección Nacional de Cuba
XIV IOI Yong-In Korea 2002

Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios

http://lwp-l.com/s1319