Primality by trial division: Difference between revisions

=={{header|newLISP}}==

Short-circuit evaluation ensures that the many Boolean expressions are calculated in the right order so as not to waste time.

<lang newlisp>; Here are some simpler functions to help us:

(define (divisible? larger-number smaller-number)

(zero? (% larger-number smaller-number)))

(define (int-root number)

(floor (sqrt number)))

(define (even-prime? number)

(= number 2))

; Trial division for odd numbers

(define (find-odd-factor? odd-number)

(catch

(for (possible-factor 3 (int-root odd-number) 2)

(if (divisible? odd-number possible-factor)

(throw true)))))

(define (odd-prime? number)

(and

(odd? number)

(or

(= number 3)

(and

(> number 3)

(not (find-odd-factor? number))))))

; Now for the final overall Boolean function.

(define (is-prime? possible-prime)

(or

(even-prime? possible-prime)

(odd-prime? possible-prime)))

; Let's use this to actually find some prime numbers.

(println (filter is-prime? (sequence 1 100)))

(exit)</lang>

{{Output}}

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)