Numeros Primos
Pascal/Turbo Pascal
Publicado el 12 de Febrero del 2006 por Frank Rafael (19 códigos)
10.347 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
OBJETIVO: Optimizar lo mejor posible la función que determina si un número es primo.
Creado con TP 7.0
Comentarios sobre la versión: Versión 1 (1)
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