## goldbach.hs

```  1 {- The authors of this work have released all rights to it and placed it
2 in the public domain under the Creative Commons CC0 1.0 waiver
3 (http://creativecommons.org/publicdomain/zero/1.0/).
4
5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12
14 -}
15
16 module Main (goldbach, main) where
17
18 import Prelude
19 import System.Environment
20 import System.IO (hFlush, stdout)
21 import Primes (primes)             -- Updated 10/19/09, Added module (see below)
22
23 {- The Goldbach Conjecture: An Implementation
24    James Brannan (irregularexpression@gmail.com)
25 -}
26
27
28 -- For convenience
29 type Pair = (Integer, Integer)
30
31 {- showPList: Prints a list of Pairs and formats them as a
32               set into columns between braces. -}
33 showPList :: [Pair] -> IO ()
34 showPList [] = putStr "{ }\n"
35 showPList plist = do
36     putStr "{ "
37     fmt 1 plist
38     putStr " }\n"  where
39         showPair (x, y) = "(" ++ show x ++ "+" ++ show y ++ ")"
40         fmt n (y:ys) = do
41             putStr (showPair y)
42             -- Every 4 elements, start a new column.
43             if n `mod` 4 == 0 then
44                 if ys == [] then return () else putStr "\n  "
45              else putStr "   "
46             fmt (n+1) ys
47         fmt _ [] = return ()
48
49
50 {- findsum: Finds a sum x by zipping a list (of primes) less than
51             x with itself (excluding repeats) and checking for
52             pairs that add up to x. I remove a lot of the garbage
53             by throwing away values
54             of z greater than y (to remove [x,y] == [y,x]). -}
55 findsum :: Integer -> [Integer] -> [Pair]
56 findsum x plist = [(y,z) | y <- plist, z <- plist, y+z == x, y<=z]
57
58
59 {- goldbach: Takes a positive even integer x and exhaustively checks
60              pairs of primes less than that integer that add up to
61              precisely x. Note we chop off half the list -- each
62              pair has a non-unique equivalent => (a,b) = (b,a) -}
63 goldbach :: Integer -> [Pair]
64 goldbach x | odd x || x < 3 = error "Must be a positive even integer greater than 2"
65            | otherwise = findsum x plist where
66                 -- Find list of primes smaller than x.
67                 plist = takeWhile (< x) primes
68
69
70 {- main: Driver interface for the defined functions. On first run,
71          an introduction message will be displayed, otherwise only
72          the prompt will be shown. -}
73 main :: IO ()
74 main = do
75     args <- getArgs
76     let args_num = [(read x::Integer) | x <- args]
77     case args of
78         [] -> helper True                 -- No arguments, run interactive
79         _  -> mapM_ showvalue args_num    -- Arguments given, run through
80
81     where
82     -- I *hate* nested paren's (too much lisp...) Use \$!
83     showvalue x = do putStr \$ resultMsg x \$ length l
84                      showPList l
85         where l = goldbach x
86
87     helper b = do
88         intro b    -- Show intro message depending on b
89         {- I have to import some IO functions here
90            because by default the output is buffered
91            and won't print until an \n is found, meaning
92            user input can't be on the same line as the
93            prompt. Without flushing the output first,
94            the program executes out of order (when compiled).
95         -}
96         putStr "[Number or 0] -> "
97         hFlush stdout
98         x <- readLn :: IO Integer -- Get input and calculate or exit
99         exec x
100
101     -- Intro message to be shown when the program is first run
102     intro True = putStr ("The Goldbach Conjecture states that any positive, " ++
103                          "even integer (>2) can be expressed as the sum of " ++
104                          "two prime numbers. This application is an " ++
105                          "algorithmic solver for the Goldbach Conjecture. " ++
106                          "Begin by entering values, and the appropriate sets " ++
107                          "of prime numbers will be returned. You may quit at " ++
108                          "any time by typing the number 0.\n\n")
109     intro False = return ()
110
111     resultMsg int res = "\nGoldbach(" ++ show int ++ ") = " ++ show res ++ " unique sets:\n"
112
113     -- Allow user to quit by typing 0
114     exec 0 = putStr "\tQuitting...\n"
115     exec y = do showvalue y
116              putStr "\n"
117              helper False -- Call without intro msg until user quits.
118
119
120 -- James Brannan (irregularexpression@gmail.com) 9/18/09
121
122
123
```

hijacker
hijacker
hijacker
hijacker

## primes.hs

``` 1 {- The authors of this work have released all rights to it and placed it
2 in the public domain under the Creative Commons CC0 1.0 waiver
3 (http://creativecommons.org/publicdomain/zero/1.0/).
4
5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12
14 -}
15
16 module Primes (primes) where
17
18 primes :: [Integer]
19 primes = 1:2:3:primes'
20   where
21 	{- Throw away first value (always 1), capture prime, and candidates
22 	   (using that fact that all *candidate* primes but 2 and 3 are of
23 	   the form [6k+1] and [6k+5] for any integer k (but not all) -}
24     1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
25 	-- Create list of primes by adding the found prime p to the list of
26 	-- candidates after they have been filtered for primes
27     primes' = p : filter isPrime candidates
28 	-- Finds if n is prime by testing all elements p where (p^2) is not
29 	-- greater than n from the list of generated primes
30     isPrime n = all (not . divides n) \$ takeWhile (\p -> p*p <= n) primes'
31 	-- Divides is true if the remainder between n and p is 0
32     divides n p = n `mod` p == 0
33
34
```

hijacker
hijacker
hijacker
hijacker