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


(lib 'sequences)
 
;; Try divisors iff n = 2k + 1
(define (is-prime? p)
	(cond
	[(< p 2) #f]
	[(zero? (modulo p 2)) (= p 2)]
	[else 
	(for/and ((d [3 5 .. (1+ (sqrt p))] ))  (!zero? (modulo p d)))]))
 
(filter is-prime? (range 1 100))
    → (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)
 
;; Improve performance , try divisors iff  n = 6k+1 or n = 6k+5
(define (is-prime? p)
	(cond
	[(< p 2) #f]
	[(zero? (modulo p 2)) (= p 2)]
	[(zero? (modulo p 3)) (= p 3)]
	[(zero? (modulo p 5)) (= p 5)]
	[else  ;; step 6 : try divisors 6n+1 or 6n+5
		(for ((d [7 13 .. (1+ (sqrt p))] ))  
			#:break (zero? (modulo p d)) => #f
			#:break (zero? (modulo p (+ d 4))) => #f
			#t )]))
 
(filter is-prime? (range 1 100))
    → (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)