1votos

primos perfectos en Haskell

por josejuan hace 4 meses

Sin usar ninguna propiedad global, pueden obtenerse los infinitos primos perfectos con coste lineal. Esta implementación para obtenerlos hasta 1.000.000.000 toma unos 0.6 segundos (hasta 100.000 ni idea). Puede paralelizarse fácilmente.

Crear una función que determine si un numero es un primo perfecto o no. El termino primo-prefecto lo invente yo, así que si lo buscan por internet, no lo encontraran, por lo cual, lean la explicación.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
ps z xs =[p|(s,p)←xs,isPrime s,isPrime p]⧺ps(q3+q7)[(s+d,p+q)|(d,q)←[(2,q2),(3,q3),(5,q5),(7,q7)],(s,p)←xs]  
  where {q2=z+z;q3=q2+z;q5=q3+q2;q7=q5+q2}  
 
{-  
 
----------- 
Hasta 100000 
Primos perfectos: 89 
CPU time: 0:00.00, Mem km: 3744 
----------- 
Hasta 1000000 
Primos perfectos: 222 
CPU time: 0:00.00, Mem km: 4336 
----------- 
Hasta 10000000 
Primos perfectos: 718 
CPU time: 0:00.02, Mem km: 5012 
----------- 
Hasta 100000000 
Primos perfectos: 2498 
CPU time: 0:00.08, Mem km: 11276 
----------- 
Hasta 1000000000 
Primos perfectos: 9058 
CPU time: 0:00.59, Mem km: 29752 
  
 
-} 
3 comentarios
0votos

Escrito por josejuan hace 4 meses

Paralelizando con 6 cores (AMD Phenom II X6 1045T) le toma 45 segundos obtener los 100.000 primeros primos perfectos (no hasta 100.000), revisando hasta el número 100.000.000.000
[josejuan@centella centella]$ time -f "CPU time: %E, Mem kb: %M" ../perfectprime 100000000000 +RTS -N6
107304
CPU time: 0:44.97, Mem kb: 324832

(NOTA: se han ignorado en el conteo algunos primeros primos de la primera ronda como el 2, 5, ...)

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.