Las definiciones de semiprimo y k-casi primo nos permiten crear clases de equivalencia en los números naturales. Al conjunto de todos los k-casi primos se le representa por Pk. Así, P1 estará formado por los números primos, P2 por los semiprimos, P3 por los 3-casi primos, etc.
Conseguir esta clasificación con hoja de cálculo requiere partir de un algoritmo de factorización de números naturales (sólo consideraremos un nivel elemental) e incluirle un contador de factores primos.
La siguiente tabla se ha conseguido con un algoritmo de este tipo:
P1 P2 P3 P4 P5 P6
2 4 8 16 32 64
3 6 12 24 48 96
5 9 18 36 72 144
7 10 20 40 80 160
11 14 27 54 108 216
13 15 28 56 112 224
17 21 30 60 120 240
19 22 42 81 162 324
23 25 44 84 168 336
29 26 45 88 176 352
La primera columna está formada por primos, la segunda por semiprimos, la tercera por 3-casi primos, y así hasta k=6. Una curiosidad divertida es la de seguir la secuencia natural de números 1, 2, 3, 4, … en esta tabla e interpretar sus oscilaciones.
El núcleo del algoritmo es el de averiguar k, es decir, el número de factores primos de un número.
Copiamos a continuación las líneas fundamentales de este algoritmo:
Se supone que n es el número, f el factor primo que se va probando y m el contador que recogerá el número de factores:
f=1 (se comienza con factor 1)
while n>1 (esta condición controla el final del algoritmo)
f=f+1 (se prueba otro número)
while n/f=int(n/f) (se pregunta si ha encontrado un divisor)
m=m+1 (si es divisor, aumenta el contador)
n=n/f (se divide el número entre el divisor encontrado para acelerar la búsqueda)
wend wend
msgbox(m) (se comunica el resultado)
Es evidente que este algoritmo se ralentiza en cuanto n es un número de bastantes cifras, y de ahí la utilidad de los semiprimos en ciertas codificaciones.
No hay comentarios:
Publicar un comentario