Transforming the code to use recursion

I would probably do this iteratively:

``````#lang racket

(define max-number 100)

(define (iterative-sieve)
; for/fold carries state along with it, in this case 'primes'.  The initial value is (in this case),
; the null list and the return value of each iteration becomes the state for the next iteration.
(for/fold ([primes '()])
([test-number (in-range max-number 2 -1)])
; Note  the in-range.  We're iterating backwards from max-number to 2 with a step size of -1.
; This is because we're building our list with `cons`, which pushes onto the head of
; the list and therefore generates it in LIFO order.
(define root (sqrt test-number))
(cond [(integer? root)  primes] ; if test-number is a square then it's not prime
[else
(define factor-found?
(for/or ([potential-divisor (in-inclusive-range 2 (floor root))])
; for/or iterates and stops as soon as it finds an item
; that returns true.  If it never finds a true element
; then for/or produces #f
(zero? (remainder test-number potential-divisor))))

(if factor-found?
primes ; continue the for/fold without changing list of primes
(cons test-number primes))])))  ; remember this prime, continue for/fold
``````

EDIT: Oh, look, @simonls already said to do it this way and pointed out the possibility of homework. Doh. Well, I didn't give a recursive solution so I'll leave it.

2 Likes

Actually I am not so sure about the homework part, but doing things yourself to learn better remains.
However I am not a teacher and an autodidact myself, so I probably would have liked seeing this solution, to absorb it, so I am not sure what is "best", especially if I don't have any sense of the experience level of the person.

I like that you added the 2 algorithm optimizations (inverted range, square root upper bound).
Another one I like, because it is easy to do, is adding 2 to the list of primes from the start, iterating by steps of -2 and starting from 3.

I don't know how this sort of unrolling is called (forgot where I read about it) but you can do it with more and more initial numbers, it just gets more complicated cycling between different deltas, in theory it should allow you to skip considering a percentage of the numbers, but the number skipped are diminishing with increasing wheel sizes.

I actually found it Wheel factorization - Wikipedia.

3 Likes

Recursion requires you to completely change how you approach a problem. Let's say we want the list of prime numbers from 2 to 20. We can start with producing the list of all numbers between 2 and 20:

``````(define (numbers from to)
(if (> from to)
empty
(cons from (numbers (+ from 1) to))))
(numbers 2 20) ; => '(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
``````

`numbers` is a recursive function definition which implements the simple observation that the list of numbers from 2 to 20 is the same as 2 followed by the list of numbers from 3 to 20, and so on. We also have a terminating condition: the list of numbers from 21 to 20 is the empty list.

You'll notice that every prime number from 2 to 20 is in that list, so, in a sense, we're done -- the original requirements did not say that the list must contain only the prime numbers.

The actual problem is that the list contains too many elements, and we need to remove some of them. For example, 2 is a prime number, but every multiple of 2 is not and can be removed, the same can be done for 3 and so on. In general we can write another recursive function to drop every multiple of a number from a list:

``````(define (drop start step l)
(if (null? l)
empty
(let ([head (first l)]
[tail (rest l)])
(cond ((< head start)
(cons head (drop start step tail)))
(drop (+ start step) step l))
(drop (+ start step) step tail))))))
(drop 4 2 (numbers 2 20)) ; => '(2 3 5 7 9 11 13 15 17 19)
``````

If we drop every multiple of the first number we see in a list, and do that recursively only the prime numbers will remain:

``````(define (primes l)
(if (null? l)
empty
(let ([head (first l)]
[tail (rest l)])
(primes (numbers 2 20)) ; => '(2 3 5 7 11 13 17 19)
``````

You'll notice that the program above does not actually calculate any prime number, it just removes all non-primes from the list. For more details on this algorithm, you can check out: Sieve of Eratosthenes - Wikipedia

Ok, the next part is going to be more subtle: what if you wanted every prime number that there is? There is an infinite number of them, of course, but this is not an issue if we use recursion.

We can use the exact same strategy, except we'll use `streams` instead of lists. First, here is `numbers` changed to produce all the numbers starting from a certain number.

``````(define (numbers from)
(stream-cons from (numbers (+ from 1))))
(numbers 2) ; => #<stream>
``````

Note that the `numbers` is still recursive, but there is no longer any terminating condition. The list of numbers from 2 is simply 2 plus the list of numbers from 3 and so on, forever. 'When you try to print it, Racket, prudently, prints out just "#", but you can take some numbers out, here are the first 20 numbers from that list:

``````(stream->list (stream-take (numbers 2) 20))
'(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21)
``````

We can re-write `drop` to drop multiples of numbers from infinite streams, producing an infinite stream of numbers. All we need to do is remove the terminating condition for the recursion and use `stream-cons` instead of `cons` and `stream-first`, `stream-rest` instead of `first` and `rest`:

``````(define (drop start step l)
(let ([head (stream-first l)]
[tail (stream-rest l)])
(cond ((< head start)
(stream-cons head (drop start step tail)))
(drop (+ start step) step l))
(drop (+ start step) step tail)))))
(stream->list (stream-take (drop 4 2 (numbers 2)) 20))
'(2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39)
``````

And we can rewrite `primes` the same way:

``````(define (primes l)
(let ([head (stream-first l)]
[tail (stream-rest l)])
(stream->list (stream-take (primes (numbers 2)) 20))
'(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)
``````

So, basically, the value returned by `(primes (numbers 2))` is the list of all the prime numbers that exist. It is an infinite list, but Racket can handle it just fine. You can take as many primes from that list as you want, but taking all of them will take an infinite amount of time....

Alex.

5 Likes

Obligatory: this is not the sieve of eratosthenes. https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

2 Likes

Thank you all very much for the replies. Appreciate it.
I don't know how much it can be trustworthy coming from me but this is not a homework assignment and just a simple problem a work colleague and I try to implement in different programming languages to see what we like best. Racket is one of those languages I am more interested in and the idea of not changing a variable's state through reassigning is very interesting.

3 Likes

Since your primary interest is learning how to avoid reassignment, let's use a simpler example than counting primes. Here is a function very much like yours, that counts even numbers instead of primes.

; Original version using the "for" form and set! to modify the count as we go

``````(define (count-evens lst)
(define count 0)
(for ([num lst])
(cond
[(even? num) (set! count (add1 count))]))
count)
``````

Test it to make sure it works:

``````> (count-evens '(0 1 2 3 4))
3
``````

Now, to make clear what is happening, let's rewrite by replacing the "for" with a recursive helper function so that we can see exactly how the loop works.

``````; Version replacing "for" with a recursive helper, still using set! to keep track of the count
(define (count-evens lst)
(define count 0)
(define (count-evens-helper lst)
(cond
[(null? lst) count]
[(even? (first lst)) (begin
(set! count (add1 count))
(count-evens-helper (rest lst)))]
[else (count-evens-helper (rest lst))]))
(count-evens-helper lst))
``````

To get rid of the assignment, we can add an extra argument to the helper function. Instead of modifying the count variable with set!, we pass the new value as the extra argument. This extra argument is called an "accumulator" because it accumulates the total as you proceed through the computation.

``````; Add an accumulator to the helper function to keep tracker of the count
(define (count-evens lst)
(define (count-evens-helper lst count)
(cond
[(null? lst) count]
[(even? (first lst)) (count-evens-helper (rest lst) (add1 count))]
[else (count-evens-helper (rest lst) count)]))
(count-evens-helper lst 0))
``````

Once you understand how the accumulator style works, we can take advantage of one of Racket's iteration forms. "for/fold" is variant of the "for" form that supports accumulators.

``````; Replace the helper + accumulator with the "for/fold" form
(define (count-evens lst)
(for/fold ([count 0])
([num lst])
(cond
[(even? num) (add1 count)]
[else count])))
``````

I hope this helps you see how this kind of pattern works. After you are comfortable with it, you can modify your prime counter to work in a similar way.

4 Likes

Check Part II of "How to Design Programs".

``````https://htdp.org/2022-8-7/Book/part_two.html
``````

Since you already know how to use use lists, I think you can skip to chapter 9,
but skim chapter 8 first.

1 Like

Ahh this is the paper where I first read about the number wheel.

I liked this paper a lot and its elegance in a functional language like haskell (maybe could be replicated with #lang lazy?).

However my naive explicit stream based implementation wasn't as pretty and used quite a bit more memory, than simpler iterative variants using some upper bound and manipulating bitvectors. (However it was more a fun afternoon experiment...)
It seemed like those iterative variants are often good in a practical setting because of caches and memory use (less memory, using contiguous arrays, resulting in less cache misses, tighter loops) which is why I also like these approaches.

I think the topic of having this algorithm be compiled down to efficient lowlevel code that doesn't use that much memory is another topic.
(Maybe racket would require me to do more of the work there in choosing other lowlevel primitives, compared to haskell which maybe does more automatic optimizations? I really don't know but if anyone knows would be interesting...)

I also wonder about using things like SIMD for the iterative approach and contrasting those with algorithms which theoretically have better complexity, but can be difficult to implement without a smart functional compiler that figures out how to use the hardware to its limit (or closer towards that). At some n the better algorithm wins, but from my limited experience it seems like sometimes the constant factors get underestimated too much. Like the better algorithm using too much memory, causing cache misses, becoming slower than the naive one, or simply having good memory layout / access patterns. Ideally functional languages would do that automatically, but it seems to me like functional languages could improve in that area, that said I just might not know about functional languages that do these lowlevel things automatically.

I guess the sham project is a step in that direction, but here I am more wondering about things the language could do automatically.

1 Like

If you say it's not homework then I believe you. I think it's cool you're doing it, and I hope this thread has been helpful.

3 Likes

I only had a brief look at the paper and I am not familiar with Haskell, but my program does not seem to implement the first Haskell program from that paper, but the later ones, which they describe as the "real sieve", however I cannot be sure of that, as I don't know Haskell.

I would appreciate if someone who is familiar with it would explain what changes they would make to my program to make it the "real sieve". I wrote that code without referencing any paper, but I was familiar with the sieve algorithm...

Also, the claim about running slow seems wrong. They claim that the Haskell code takes several seconds to find the first 19 primes, on my implementation it takes about 0.5 seconds to find the first 1000 primes and about 38 seconds to find the first 10000.

The code does use memory that is proportional with the number of primes found, and for finding large primes, a different approach would be required.

``````(time (begin (stream->list (stream-take (primes (numbers 2)) 100)) (void)))
cpu time: 0 real time: 3 gc time: 0
> (time (begin (stream->list (stream-take (primes (numbers 2)) 1000)) (void)))
cpu time: 359 real time: 361 gc time: 0
> (time (begin (stream->list (stream-take (primes (numbers 2)) 10000)) (void)))
cpu time: 37625 real time: 38405 gc time: 5953
``````

Alex.

It looks to me like @benknoble's post refers to the original question post?
Which uses trial division.

Where your solution looks like a Sieve of Eratosthenes to me.
Well one difference seems to be that the algorithm described in the paper at "2 What the Sieve Is and Is Not" just starts dropping elements starting from p² where your implementation starts from 2p, but it also calls it a "pleasing but minor optimization".
I think using `(* head head)` instead of `(+ head head)` in `primes` should work?

Discourse shows that the post arrived via email, maybe that is why the website doesn't indicate a clear reply target/comment for the post and just lists it as an entry in this topic?

1 Like

I admit I only skimmed your implementation; I suspect yours is closer
to or exactly the sieve.

1 Like

I think that an iterative approach is better suited to this particular problem. I wrote the following optimized code to generate all primes < up-bound:

``````;; up-bound is non-inclusive
(define (run-sieve up-bound)
(define bstring (make-bytes up-bound 1))

;; mark even numbers after 2 so we can skip all even numbers in the for loop below
(for ([i (in-range 4 up-bound 2)])
(unsafe-bytes-set! bstring i 0))

(for ([i (in-range 3 (sqrt up-bound) 2)])
(when (unsafe-fx= (unsafe-bytes-ref bstring i)
1)
(for ([multiple (in-range (* i i) up-bound (* i 2))])
(unsafe-bytes-set! bstring multiple 0))))

bstring)

;; get a list of prime numbers from the byte string generated by run-sieve
(define (primes bstring)
;; skip index 0 and even indexes since we know even numbers are not prime
(for/list ([i (in-range 1 (bytes-length bstring) 2)]
[val (in-bytes bstring 1 #f 2)]
#:when (equal? val 1))
i))
``````

I wouldn't recommend using unsafe operations like this in most code, but this code is fairly performant:

``````(time (length (primes (run-sieve 100000))))
cpu time: 1 real time: 1 gc time: 0
9592
``````

This is calculating the first 9592 primes in about 1ms, and that includes the O(n) length operation. Using a byte string for the representation saves a lot of memory allocation(and time).

1 Like

I like this a lot, because it uses low level operations and runs fast.

It has a bug `(primes (run-sieve 10)` returns `'(1 3 5 7)`.
The first loop in `run-sieve` is unnecessary because the values it sets are never read anywhere (even numbers).

Here is the modified version:

``````#lang racket

(require racket/unsafe/ops)

;; up-bound is non-inclusive
(define (run-sieve up-bound)
(define bstring (make-bytes up-bound 1))

(for ([i (in-range 3 (sqrt up-bound) 2)])
(when (unsafe-fx= (unsafe-bytes-ref bstring i)
1)
(for ([multiple (in-range (* i i) up-bound (* i 2))])
(unsafe-bytes-set! bstring multiple 0))))

bstring)

;; get a list of prime numbers from the byte string generated by run-sieve
(define (primes bstring)
(define len (bytes-length bstring))
;; skip everything before 3 and even indexes since we know most even numbers are not prime
(define (odd-primes)
(for/list ([i (in-range 3 len 2)]
[val (in-bytes bstring 3 #f 2)]
#:when (equal? val 1))
i))

(if (> len 2) ;; bytes includes 0 1 2 and is 0 indexed
(cons 2 (odd-primes))
'()))

(module+ test
(require rackunit)
(check-equal? (primes (run-sieve 2))   '()  "expected no primes below exclusive upper bound 2")
(check-equal? (primes (run-sieve 3))   '(2) "expected only the prime 2 below exclusive upper bound 3")
(check-equal? (primes (run-sieve 10))  '(2 3 5 7))
(check-equal? (primes (run-sieve 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)))

(module+ main
(time (length (primes (run-sieve 100000)))))
``````

FWIW the blog Programming Praxis has a lot of articles on prime numbers.
Solutions are in Scheme.

2 Likes

Thanks for the fix in the `primes` function! I was looking at the total number of primes and never noticed.

I wouldn't remove the first `for` in `run-sieve` because that is the real sieve. `primes` was intended as a convenience function to just count the primes. But to be consistent with that I should remove 0 and 1 as primes in the byte string as well. Here's my updated version:

``````;; up-bound is non-inclusive
(define (run-sieve up-bound)
(define bstring (make-bytes up-bound 1))

(unsafe-bytes-set! bstring 0 0)
(unsafe-bytes-set! bstring 1 0)

;; mark even numbers after 2 so we can skip all even numbers in the for loop below
(for ([i (in-range 4 up-bound 2)])
(unsafe-bytes-set! bstring i 0))

(for ([i (in-range 3 (sqrt up-bound) 2)])
(when (unsafe-fx= (unsafe-bytes-ref bstring i)
1)
(for ([multiple (in-range (* i i) up-bound (* i 2))])
(unsafe-bytes-set! bstring multiple 0))))

bstring)

;; get a list of prime numbers from the byte string generated by run-sieve
(define (primes bstring)
(cons 2
;; skip index 0 and even indexes since we know even numbers are not prime
(for/list ([i (in-range 3 (bytes-length bstring) 2)]
[val (in-bytes bstring 3 #f 2)]
#:when (equal? val 1))
i)))
``````
1 Like

I figured that it was something like that.

However considering that there is only 1 even prime, only storing odd primes seems like a very cheap memory saving technique with array based implementations (that still preserves relatively simple iteration and array access). Everyone possibly has a different favorite implementation with different tradeoffs. Here is my modified version (if I were to continue these prime implementation experiments I would probably create a new topic, but currently I intend this to be where I stop):

markdown from source comments

With modifications:

• only storing info for odd-prime candidates
• saving half the memory, in theory this might cause it to run slightly slower,
but maybe not if increased memory density has a positive effect on reducing cache misses.
• instead of repeated bytes-ref iterates bstring in parallel
• adding rudimentary test cases
• adding a verify submodule using a `prime?` predicate for verification
• adding a main submodule to run different commands from terminal

possible further work(I may never do):

• compare the memory needs and runtime of different implementations and graph those
• compare with implementations in other languages
• add some bounds checking so that the unsafe operations don't fail silently when their limit is exceeded
• segmented sieve (add a lower bound for wanted primes)
1. this would use two arrays one for the odd primes under the square root
2. another one for the odd candidates between lower and upper bound
3. use 1. to cross off all false candidates within the range lower-upper in array 2.
• add make-bits, bits-ref, bits-set! and in-bits
• compare bytes with fxvector for the underlying array has one advantages over the other?
• could crossing off on bitvectors use 128/256/512 bit wide SIMD instructions with bitpatterns as "stencils"?
• is there some way to use SIMD instructions in racket? sham? ffi? hacking the chez layer?
• switching between different implementations based on lower and upper bound
• depending on whether the arrays fit in memory etc.
• how do other projects deal with extremely large numbers? when do they use what algorithms etc.

All of these are things that might already be done way better, in other implementations.
The things I noted as possible work, are things that could be interesting as little projects,
when you are in the mood to explore some things. This is mostly for fun.

Here is a c++ project that has a lot of optimizations:
GitHub - kimwalisch/primesieve: 🚀 Fast prime number generator

Some descriptions of how it works:
primesieve/ALGORITHMS.md at master · kimwalisch/primesieve · GitHub

``````#lang racket

(provide primes)

(require racket/unsafe/ops)

;; code based on:
;; https://racket.discourse.group/t/transforming-the-code-to-use-recursion/1236/15
;; https://racket.discourse.group/t/transforming-the-code-to-use-recursion/1236/18

;; With modifications:
;; - only storing info for odd-prime candidates
;;   - saving half the memory, in theory this might cause it to run slightly slower,
;;     but maybe not if increased memory density has a positive effect on reducing cache misses.
;; - instead of repeated bytes-ref iterates bstring in parallel
;; - adding rudimentary test cases
;; - adding a verify submodule using a `prime?` predicate for verification
;; - adding a main submodule to run different commands from terminal

;; possible further work(I may never do):
;; - compare the memory needs and runtime of different implementations and graph those
;; - compare with implementations in other languages
;; - add some bounds checking so that the unsafe operations don't fail silently when their limit is exceeded
;; - segmented sieve (add a lower bound for wanted primes)
;;   1. this would use two arrays one for the odd primes under the square root
;;   2. another one for the odd candidates between lower and upper bound
;;   3. use 1. to cross off all false candidates within the range lower-upper in array 2.
;; - add make-bits, bits-ref, bits-set! and in-bits
;;   - compare bytes with fxvector for the underlying array has one advantages over the other?
;;   - could crossing off on bitvectors use 128/256/512 bit wide SIMD instructions with bitpatterns as "stencils"?
;;     - is there some way to use SIMD instructions in racket? sham? ffi? hacking the chez layer?
;; - switching between different implementations based on lower and upper bound
;;   - depending on whether the arrays fit in memory etc.
;;   - how do other projects deal with extremely large numbers? when do they use what algorithms etc.
;;
;; All of these are things that might already be done way better, in other implementations.
;; The things I noted as possible work, are things that could be interesting as little projects,
;; when you are in the mood to explore some things. This is mostly for fun.
;;
;; Here is a c++ project that has a lot of optimizations:
;; https://github.com/kimwalisch/primesieve
;;
;; Some descriptions of how it works:
;; https://github.com/kimwalisch/primesieve/blob/master/doc/ALGORITHMS.md

;; up-bound is non-inclusive
(define (primes up-bound)
(define bytes   (max 0 (inexact->exact (ceiling (/ (- up-bound 3) 2)))))
(define bstring (make-bytes bytes 1)) ;; contains odd prime candidates

(for ([i  (in-range 3 (sqrt up-bound) 2)]
[p? (in-bytes bstring 0 #f 1)]
#:when (unsafe-fx= 1 p?)
[multiple (in-range (unsafe-fx* i i) up-bound (unsafe-fxlshift i 1))])
(define multiple-index (unsafe-fxquotient (unsafe-fx- multiple 3) 2))
(unsafe-bytes-set! bstring multiple-index 0))

(define (odd-primes)
(for/list ([i (in-range 3 up-bound 2)]
[val (in-bytes bstring 0 #f 1)]
#:when (unsafe-fx= val 1))
i))

(if (> up-bound 2)
(cons 2 (odd-primes))
'()))

(module+ test
(require rackunit)
(check-equal? (primes 2)   '() "expected no primes below exclusive upper bound 2")
(check-equal? (primes 3)   '(2) "expected only the prime 2 below exclusive upper bound 3")
(check-equal? (primes 4)   '(2 3))
(check-equal? (primes 6)   '(2 3 5))
(check-equal? (primes 10)  '(2 3 5 7))
(check-equal? (primes 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)))

(module+ verify
(require math/number-theory)
(provide verify)

(define (verify upper-bound)
(displayln "generate lst:")
(define lst (time (primes upper-bound)))

(displayln "validate:")
(define valid?
(time (for/and ([p (in-list lst)])
(prime? p))))

(if valid?
(displayln "all valid")
(error 'verify-fail "not all numbers returned are primes"))))

(module+ main
(require (submod ".." verify))
(define default-upper "100")
;; just a silly experiment using match for custom commandline parsing, normally you would use "command-line" or a similar library
(define help
(~a "usage:\n"
"  no args:           use default command time\n"
"  help, --help, -h:  prints this help\n"
"\n"
"  command [upper-bound=" default-upper "]:\n"
"    time    time the execution of calculating primes up to upper-bound\n"
"    verify  verifies the primes up to upper-bound\n"
"    print   prints the primes up to upper-bound"))

(let cl ([args (current-command-line-arguments)])
(match args
[(vector (or "help" "--help" "-h")) (displayln help)]
[(vector "time" upper-bound)   (define ub (string->number upper-bound)) (time (void (primes ub)))]
[(vector "verify" upper-bound) (define ub (string->number upper-bound)) (verify ub)]
[(vector "print" upper-bound)  (define ub (string->number upper-bound)) (for ([p (in-list (primes ub))]) (displayln p))]
[(vector command) (cl (vector command default-upper))]
[(vector) (cl #("time"))]
[_ (displayln "arguments didn't match, please use:") (cl #("help"))])))

``````

My two cents: a purely functional sieve.

``````#lang racket

; The sieve is a binary integer with an infinite number of heading zeros.
; A zero bit indicates that the correspònding number still is in the sieve.
; A number is removed from the sieve by setting the corresponding bit in the sieve to 1.

(define (sieve bound)
(define bound-sqrt (integer-sqrt bound))
; new-sieve takes a sieve and erases all multiples of n up to the bound.
; (or rather the square root of the bound)
(define (new-sieve n old-sieve)
(cond
((> n bound-sqrt) old-sieve)
((zero? (bitwise-and old-sieve (arithmetic-shift 1 n)))
(define (erase k sieve)
(cond
((>= k bound) (new-sieve (add1 n) sieve))
(else (erase (+ k n) (bitwise-ior sieve (arithmetic-shift 1 k))))))
(erase (sqr n) old-sieve))
(else (new-sieve (add1 n) old-sieve))))
; Make sieve for numbers up to bound.
; Start with sieve #b11 indicatinbg that 0 and 1 are not prime numbers.
; Start with n=2, for we don't want to erase all multiples of 1.
(new-sieve 2 #b11))

; Can be speeded up by letting the bits of the sieve correspond to odd numers only.
; Another way of speeding up is to run allong numbers N=(3 7 9 11) and N+10k.

(require math/number-theory)

; Check the sieve.

(let* ((bound 100000) (sieve (time (sieve bound))))
(for/fold
((list-of-primes '())
(bit 1)
#:result (reverse list-of-primes))
((i (in-range bound)))
(values
(if (zero? (bitwise-and sieve bit))
(if (equal? (prime-divisors i) (list i))
(cons i list-of-primes)
(error 'primes "not a prime: ~d" i))
list-of-primes)
(arithmetic-shift bit 1))))
``````

Jos

Finding the first few hundred thousand primes is a trivial problem as many of the answers here show. If you are looking for a challenge with prime numbers try one of these:

• write a program that finds the N-th prime number, where N is supplied by the user when invoking the procedure. For example `(nth-prime 5)` would return 11 since 11 is the fifth prime (assuming primes start at 2). The user will test this function by passing values greater than 10000000 (ten million) to `nth-prime`.
• write a program that finds the first prime number (not a pseudo prime number) after a value X, where X is supplied by the user when invoking the procedure. For example `(first-prime-after 5)` would return 7, since 7 is the first prime greater than 5. The user will test this function by passing values greater than 18446744073709551616 to `first-prime-after` (i.e values larger than 64 bits).

Enjoy,
Alex.

1 Like

Natural number primes do start at 2.
The elements of a ring are classified as

``````* zero
* units (those elements with multiplicative inverses)
* primes (which can be factored into multiple factors only if all but one factor is a unit)
* composites
``````

So the natural number 1 is a unit, not a prime. 2 is a prime.
In the integers, 1 and -1 are units, and -2 is a prime.
In the reals, every real numner except 0 is a unit.

-- hendrik