Código de Pascal/Turbo Pascal - Numeros Primos

sin imagen de perfil

Numeros Primosgráfica de visualizaciones


Pascal/Turbo Pascal

estrellaestrellaestrellaestrellaestrella(1)
Publicado el 12 de Febrero del 2006 por Frank Rafael
9.326 visualizaciones desde el 12 de Febrero del 2006
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
9.327 visualizaciones desde el 12 de Febrero del 2006
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

  • Archivos para descargar

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




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

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
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s1319