Task

Write a boolean function that tells whether a given integer is prime.



Remember that   1   and all non-positive numbers are not prime.

Use trial division.

Even numbers greater than   2   may be eliminated right away.

A loop from   3   to   √ n    will suffice,   but other loops are allowed.



Related tasks

   count in factors
   prime decomposition
   AKS test for primes
   factors of an integer
   Sieve of Eratosthenes
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes
   sequence of primes by Trial Division


; 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)