Dear all:
I am teaching myself about lisp language. I want to write a recursive
function called next-prime, which will return the next prime number for a
positive integer input from user, for example:
>(next-prime 4)
>5
>(next-prime 9)
>11
I have thought the program very long time, and couldn't found the solution.
May somebody tell me what the step sould I do. Any feedback is great!
Thanks very much.
In article <··························@hntp1.ntu.edu.tw>, "CSSuen"
<········@cc.ntu.edu.tw> wrote:
> Dear all:
> I am teaching myself about lisp language. I want to write a recursive
> function called next-prime, which will return the next prime number for a
> positive integer input from user, for example:
>
> >(next-prime 4)
> >5
>
> >(next-prime 9)
> >11
>
> I have thought the program very long time, and couldn't found the solution.
> May somebody tell me what the step sould I do. Any feedback is great!
> Thanks very much.
You may want to read "Structure and Interpretation of Computer
Programs" by Abelson/Sussman. It will give you some ideas
how to do that.
--
http://www.lavielle.com/~joswig/
From: marisal
Subject: Re: Ask about some questions.
Date:
Message-ID: <33495275.171@wrq.com>
CSSuen wrote:
>
> Dear all:
> I am teaching myself about lisp language. I want to write a recursive
> function called next-prime, which will return the next prime number for a
> positive integer input from user, for example:
>
> >(next-prime 4)
> >5
>
> >(next-prime 9)
> >11
>
> I have thought the program very long time, and couldn't found the solution.
> May somebody tell me what the step sould I do. Any feedback is great!
> Thanks very much.
How about the following pseudo-Lisp program?:
(defun next-prime (n)
(let ((n2 (if (evenp n) (1+ n) (+ n 2))))
(do j: from 3 to (sqrt n2) step 2
; loop for all odd integers from 3 to square root of n2
(when (integerp (/ n2 j) ; If j divides n2 evenly, then n2 is
not a prime
(return (next-prime (+ n 2))) ; so try the next odd number.
n2 )) ; If you exit the loop via this point, it means that n2 is
the prime
; you were searching, so return it.
I don't do your homework completely: you have to finish polishing it up
yourself.
Regards.
In article <············@wrq.com>, marisal <·······@wrq.com> wrote:
> CSSuen wrote:
> > Dear all:
> > I am teaching myself about lisp language. I want to write a recursive
> > function called next-prime, which will return the next prime number for a
> > positive integer input from user,
I'll give you a big hint: do a web search on 'pseudo-prime', 'Jacobi symbol',
etc. Then you can speed up your program by quickly rejecting non-pseudoprimes
before laboriously checking for primality.
The source code for PARI/GP is available on the web, and it implements such
a next-prime function, although it doesn't _prove_ that the 'prime' it finds
is really prime.