Here's a slight reworking of the factor function. I think it is prettier
and my in the spirit of Racket/Scheme.
; function to create a list of prime factors of a number
; invoke as (factor n)
(define (factor n)
(let loop-factors ([facts '()] [x n] [start 2] [end 1000]
[candidate-primes (primes-from-to 2 1000)])
(if (and (eq? candidate-primes empty) (>= end (integer-sqrt x)))
(if (= 1 x) facts (append facts (list x)))
(begin
(if (eq? candidate-primes empty)
(begin
; attempt to pull in more primes in an efficient manner
(set! start end)
(set! end (* 2 end))
(if (or (> end (integer-sqrt x)) (> (* 1.25 end)
(integer-sqrt x))) (set! end (integer-sqrt x)) #f)
(set! candidate-primes (primes-from-to start end))
(loop-factors facts x start end candidate-primes))
(let ([candidate (first candidate-primes)])
(if (= 0 (remainder x candidate))
(begin
(set! facts (append facts (list candidate)))
(loop-factors facts (quotient x candidate) start end
candidate-primes))
(loop-factors facts x start end (rest
candidate-primes)))))))))
On Sat, Feb 18, 2012 at 6:41 PM, Joe Gilray <jgil...@gmail.com> wrote:
> Stephen, Gary, et al,
>
> Thanks for the suggestions. Below is the code I've been playing with
> today. I'd love any and all suggestions. I've been coding in Racket for
> about a week so I'm sure there is a lot a grist for the mill below!
>
> -Joe
>
> ; function that returns a list of all integers between the two arguments
> inclusive
> (define (interval-list m n)
> (if (> m n)
> '()
> (cons m (interval-list (+ 1 m) n))))
>
> ; sieve of erostosthenes
> (define (sieve lst)
> (define (remove-multiples n lst)
> (if (null? lst) '()
> (if (= (modulo (car lst) n) 0)
> (remove-multiples n (cdr lst))
> (cons (car lst)
> (remove-multiples n (cdr lst))))))
> (if (null? lst) '() (cons (car lst) (sieve (remove-multiples (car lst)
> (cdr lst))))))
>
> ; wrapper function for sieve, saves a list of primes for future calls
> (define primes-from-to
> (let ([lastend 0] [storedlst '()])
> (lambda (start end)
> (cond [(<= lastend start) (set! storedlst (sieve (append storedlst
> (interval-list start end))))]
> [(< lastend end) (primes-from-to lastend end)])
>
> ; storedlst now has all the primes needed
> (if (< lastend end) (set! lastend end) #f)
> (filter (lambda (v) (and (<= start v) (<= v end))) storedlst))))
>
> ; function to create a list of prime factors of a number
> ; invoke as (factor n)
> (define (factor n)
> (let loop-factors ([facts '()] [x n] [start 2] [end 1000]
> [candidate-primes (primes-from-to 2 1000)])
> (if (and (eq? candidate-primes empty) (>= end (integer-sqrt x)))
> (if (= 1 x) facts (append facts (list x)))
> (begin
> (if (eq? candidate-primes empty)
> (begin
> ; attempt to pull in more primes in an efficient manner
> (set! start end)
> (set! end (* 2 end))
> (if (or (> end (integer-sqrt x)) (> (* 1.25 end)
> (integer-sqrt x))) (set! end (integer-sqrt x)) #f)
> (set! candidate-primes (primes-from-to start end))) #f)
> (if (eq? candidate-primes empty)
> (if (= 1 x) facts (append facts (list x)))
> (let ([candidate (first candidate-primes)])
> (if (= 0 (remainder x candidate))
> (begin
> (set! facts (append facts (list candidate)))
> (loop-factors facts (quotient x candidate) start end
> candidate-primes))
> (loop-factors facts x start end (rest
> candidate-primes)))))))))
>
>
>
> On Sat, Feb 18, 2012 at 6:02 PM, Stephen Bloch <bl...@adelphi.edu> wrote:
>
>>
>> On Feb 18, 2012, at 2:42 PM, Gary Baumgartner wrote:
>>
>> >> (filter (lambda (v) (if (and (>= v start) (<= v end)) #t #f))
>> >> storedlst)
>> >> )))
>> > [...]
>> >
>> > Consider just (lambda (v) (and (>= v start) (<= v end))) --- no 'if'.
>>
>> I see a lot of my students doing this -- in whatever language -- because
>> they think of Booleans as a way to decide which of two things to DO, rather
>> than as legitimate values in their own right. In fact, the whole world of
>> expressions is a bit of a foreign country -- a sort of "adjunct" to the
>> more-legitimate world of statements.
>>
>> if (blah == true) {
>> return true;
>> }
>> else {
>> return false;
>> }
>>
>> For those of us forced to teach in Java, CheckStyle has two modules,
>> SimplifyBooleanExpression and SimplifyBooleanReturn, that catch things like
>> this.
>>
>>
>> Stephen Bloch
>> sbl...@adelphi.edu
>>
>>
>> ____________________
>> Racket Users list:
>> http://lists.racket-lang.org/users
>>
>
>
____________________
Racket Users list:
http://lists.racket-lang.org/users
