« back

Finding Prime Factors Using Clojure

07 Nov 2012

In another quest to find the solution to a Project Euler problem, (problem 3) I find myself coming head to head with finding prime factors.

Let's do this!

The first test...

 1  
 2     (it "should find the prime factor of nothing"
 3           (should= [] (prime-factors 0)))
 4           
 5     ;and the error
 6     Unable to resolve symbol: prime-factors in this context,
 7     
 8     ;so we create the method and have it return nothing
 9     (defn prime-factors [n]
10     	[] )
11     	
12     	;and then the test is passing.
13     

The next test...

1  
2     (it "should find the prime factor of 1"
3         (should= [] (prime-factors 1)))
4         
5     ; and that passes
6     

Next...

 1  
 2     (it "should find the prime factor of 2"
 3         (should= [2] (prime-factors 2)))
 4         
 5     ; and the error
 6     Expected: <[2]>
 7               got: <[]> (using =)
 8               
 9     ;so we change our method
10     (defn prime-factors [n]
11     	[2] )
12     

That passes but now our first two tests fail so let's get those working too...

1  
2     (defn prime-factors [n]
3     	(cond (< n 2) []
4     		  :else [2] ))
5     		  
6     ;and that will do it
7     

Next...

 1     ;the next test
 2     (it	"should find the prime factor of 3"
 3 		(should= [3] (prime-factors 3)))
 4 			
 5     (defn prime-factors [n]
 6     	(cond (< n 2) []
 7     		  :else [n] ))
 8     		  
 9     ;and that will do it
10     

 1  
 2     ;and now for four
 3     (it	"should find the prime factor of 4"
 4 		(should= [2 2] (prime-factors 4)))
 5 		
 6 	;and our error
 7 	Expected: <[2 2]>
 8               got: <[4]> (using =)
 9               
10     ;so we change our code to this
11     (defn prime-factors [n]
12     	(cond (< n 2) []
13     		  (= n 2) [2]
14     		  (zero? (rem n 2))
15     			(cons 2 [(/ n 2)])
16       		  :else [n] ))
17     

The next three tests, for 5,6 and 7 both pass.

 1  
 2     (it	"should find the prime factor of 5"
 3 		(should= [5] (prime-factors 5)))
 4 		
 5 	(it	"should find the prime factor of 6"
 6     	(should= [2 3] (prime-factors 6)))
 7     	
 8     (it	"should find the prime factor of 7"
 9     	(should= [7] (prime-factors 7)))
10 	

Then we move on to 8...

 1  
 2     (it	"should find the prime factor of 8"
 3 		(should= [2 2 2] (prime-factors 8)))
 4 		
 5 	;and the test fails
 6 	Expected: <[2 2 2]>
 7               got: <(2 4)> (using =)
 8               
 9     ;so we need to change our code again
10     (defn prime-factors [n]
11     	(cond (< n 2) []
12     		  (zero? (rem n 2))
13     			(cons 2 (prime-factors(/ n 2)))
14       		  :else [n] ))
15     

Now we move on to 9... and this is where things get really interesting...

The problem here is that 9 is not less than 2 and it is not divisible by 2, but it is divisible by 3, which is a prime number. We need to be able to create a variable to replace the number 2, let's call it candidate, and we need to be able increment the number represented as that variable. We will have to be able to pass both the number that we are trying to find the prime for and candidate into the function. We want to do that still with initially only needing to pass the number we are trying to find the prime factors for, so we can create a new function that will take the number that we are trying to find the prime for and then we can delegate the work to another function.

 1  
 2     (it	"should find the prime factor of 9"
 3 		(should= [3 3] (prime-factors 9)))
 4 		
 5 	;and the test fails
 6 	Expected: <[3 3]>
 7               got: <[9]> (using =)
 8               
 9     ;so we change our code again
10     (defn factors [n candidate]
11     	(cond (< n candidate) []
12     		  (zero? (rem n candidate))
13     			(cons candidate (factors(/ n candidate) candidate))
14       		  :else (factors n (+ 1 candidate))))
15 
16     (defn prime-factors [n]
17     	(factors n 2))
18     

And that's it, you can now find the set of prime numbers for any number.

BONUS: Say you want to find the largest number in the set of factors, a la project euler problem 3, you could do this...

1     (it "should be able to find the largest prime number for 6"
2 		(should= "3" (max-factor 6)))
3 		
4 	;and the test fails.  We do not yet have the function.
5 	;so we create this...
6 	
7 	(defn max-factor [n]
8     	(pr-str(reduce max (prime-factors n))))
9 	

Then everything passes.

BIG EXHALE.

comments powered by Disqus