Count in factors: Difference between revisions

Content added Content deleted

Inline

@@ Line 575: / Line 575: @@
 Using <code>factorize</code> function from the [[Prime_decomposition#Haskell|prime decomposition]] task,
-<lang haskell>*Main> :m +Data.List
+<lang haskell>import Data.List (intercalate)
-*Main Data.List> print "1" >> mapM_ (print . intercalate " * " . map show . factorize) [2..]
+showFactors n = show n ++ " = " ++ (intercalate " * " . map show . factorize) n</lang>
-"1"
+Output:<small>
-"2"
+<lang haskell>*Main> print 1 >> mapM_ (putStrLn . showFactors) [2..]
-"3"
-"2 * 2"
+= 2
-"5"
-"2 * 3"
+= 3
+= 2 * 2
-"7"
+= 5
-"2 * 2 * 2"
-"3 * 3"
+= 2 * 3
-"2 * 5"
+= 7
+= 2 * 2 * 2
-"11"
-"2 * 2 * 3"
+= 3 * 3
+= 2 * 5
+= 11
+= 2 * 2 * 3
+= 13
+. . .
+*Main> mapM_ (putStrLn . showFactors) [2144..]
+= 2 * 2 * 2 * 2 * 2 * 67
+= 3 * 5 * 11 * 13
+= 2 * 29 * 37
+= 19 * 113
+= 2 * 2 * 3 * 179
+= 7 * 307
+= 2 * 5 * 5 * 43
+= 3 * 3 * 239
+= 2 * 2 * 2 * 269
+= 2153
+= 2 * 3 * 359
+= 5 * 431
 . . .
-*Main Data.List> mapM_ (print . intercalate " * " . map show . factorize) [2144..]
+*Main> mapM_ (putStrLn . showFactors ) [1231231232155..]
+1231231232155 = 5 * 246246246431
-"2 * 2 * 2 * 2 * 2 * 67"
-"3 * 5 * 11 * 13"
+1231231232156 = 2 * 2 * 37 * 113 * 73620619
+1231231232157 = 3 * 11287 * 36361337
-"2 * 29 * 37"
+1231231232158 = 2 * 2039 * 4643 * 65027
-"19 * 113"
+1231231232159 = 1231231232159
-"2 * 2 * 3 * 179"
+1231231232160 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 5 * 61 * 71 * 197419
-"7 * 307"
+1231231232161 = 7 * 175890176023
-"2 * 5 * 5 * 43"
+1231231232162 = 2 * 19 * 32400821899
-"3 * 3 * 239"
+1231231232163 = 3 * 410410410721
-"2 * 2 * 2 * 269"
+1231231232164 = 2 * 2 * 307807808041
-"2153"
+1231231232165 = 5 * 11 * 29 * 47 * 16424081
-"2 * 3 * 359"
-. . .</lang>
+. . .</lang></small>
 The real solution seems to have to be some sort of a segmented offset sieve of Eratosthenes, storing factors in array's cells instead of just marks. That way the speed of production might not be diminishing as much.