;***********************************************************************
;This program was made by David Vazquez Landa
;It may be copied, changed and redistributed
;
;Author: David Vázquez Landa
;Version: 1.1
;execution: (eratostenes N)
;Where N is a Natural number bigger than 0
;***********************************************************************
;Changelog
;version 1.1:
; + Added tests to the functions in order to check the parameters with
; which they're called.
; + Added a function to append "1" to the primes list
;-----------------------------------------------------------------------
;eratostenes finds the prime numbers in a given interval
;always between 0 and some natural number.
;The program is not perfect and can be very slow due to its
;recursive nature.
;-----------------------------------------------------------------------
; ----------------------------
;Make a list of value-pairs of the form (<value>,<boolean) with the
;"value" part ranging from 0 to n and the "boolean" part defined as #t
;for (true)
(define list-true
(lambda (n)
(if (not (number? n))
"Invalid Input"
(if (= n 2)
(list (list n #t))
(append
(list-true (- n 1))
(list (list n #t)))))))
; --------------------------
;This program receives a list of value-pairs of the form
;(<value>,<boolean>) and returns the first pair marked as true
;if it exists.
(define first-true
(lambda (n)
(if (not (list? n))
"Invalid Input"
(if (null? n)
; if the first value is true
'()
(if (cadr (car n))
(car n)
(first-true (cdr n)))))))
;(printf "Test first-true~n")
;(first-true '((0 #f) (1 #f) (2 #t)))
;(printf "Expected is: ((2 #t))~n")
; ----------------------------
;Erase the multiples of a value from a list
;This function looks for all the multiples of a given value
;in a value-pair list and returns the same list with the
;<boolean> part of the pair set to #f for the <value> part of
;each multiple found.
;Parameters:
; x -> the value to look for. Number
; n -> the value-pair list in where to look
(define mark-multiples
(lambda (x n)
(if (or (not (list? n))
(not (number? x)))
"invalid input"
(if (empty? n)
'()
(if (or (not (= (modulo (caar n) x)
0)) ;if it's not multiple...
(= (caar n) x)) ;if it's the same number...
(append (list (car n)) (mark-multiples x (cdr n)))
(append (list (list (caar n) #f))
(mark-multiples x (cdr n))))))))
;(first-true (mark-multiples 5 (list-true 10)))
; ------------------------
;The main function: eratostenes
;The number "1" is a special case. Therefore I can decide whether
;to append it to the list or not. Here, it is not included
(define eratostenes
(lambda (n)
(let walk ((l (list-true n)) (x (car (list-true n))))
(if (null? l) '()
(begin
(if (or (< n (sqr (car x)))
(null? (first-true l)))
l
(append (list (car l))
(walk (mark-multiples (car x) (cdr l))
(first-true (mark-multiples (car x) (cdr l)))))))))))
; ------------------------
;The same as eartostenes, it just appends "1" to the list of primes.
(define eratostenesOne
(lambda (L)
(if (null? L)
'()
(append (list '(1 #t))
(eratostenes
L)))))<p> </p><p>
; -------------------------- ; Print trues
; This program takes a list containing value-pairs of the
; form (<value>,<boolean>) and prints a list containing
; the values for those value-pairs which contain #t in
; the <boolean> part.
(define printTrues
(lambda (l)
(if (null? l)
'()
(if (cadar l)
(append (list (caar l))
(printTrues (cdr l)))
(printTrues
(cdr l))))))</p><p> </p><p>
; --------------------------
;Try the program :)
(printf "A simple test, find the prime numbers contained in 0 to 10: ~n")
(eratostenesOne 10)
(printf "Print the prime numbers (just numbers) contained in 0 to 100: ~n")
(printTrues (eratostenesOne 100))
(printf "Print the number of prime numbers contained in 0 to 100: ~n")
(length (printTrues(eratostenesOne 100)))</p>
