Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!csus.edu!ucdavis!iris!lim
From: lim@iris.ucdavis.edu (Lloyd Lim)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Prime numbers, Help
Message-ID: <8742@ucdavis.ucdavis.edu>
Date: 8 Apr 91 23:50:44 GMT
References: <1991Apr4.164338.329@asacsg.mh.nl>
Sender: usenet@ucdavis.ucdavis.edu
Reply-To: lim@iris.ucdavis.edu (Lloyd Lim)
Organization: U.C. Davis - Department of Electrical Engineering and Computer Science
Lines: 65

In article <1991Apr4.164338.329@asacsg.mh.nl> kr@asacsg.mh.nl (Koos Remigius) writes:
>Is there someone out there who has a little routine, in LightSpeed Pascal, that
>gives me the first prime number larger then the number given to the routine.
>
>Example:
>
>I call the routine as follows:
>
>	Primenumber:=GetNextPrime(22654);
>
>The routine GetNextPrime should give me a prime number, as close as 
>possible, but larger then the passed number.

Oh BTW, does anyone have any code to solve the Traveling Salesman problem?
:-)   Sorry, no offense, just couldn't resist.

Seriously, the only way to do such a thing is to test successive (odd) numbers
to see if they are prime.  In general, the Miller-Rabin probablistic
primality test is the best to use but if the domain is just shorts or longs
then you can use simpler methods.

Here's a really simple routine.  I like it because it doesn't use any extra
space.  You can do better with more work or if you use extra space.  I'm
sure others can post more complicated routines.

/*
   Prime returns whether the given number is a prime number.  This algorithm
   simply checks if the number is divisible by any numbers in the sequence 2, 3,
   5, 7, 11, 13, 17, ... up to the square root of the number.  After the first
   three terms, the sequence is obtained by alternately adding 2 and 4.
*/

Boolean Prime(n)

unsigned long  n;

{
   Boolean        isPrime;
   unsigned long  divisor, root;
   
   isPrime = FALSE;
   if (n > 1) {
      if (n == 2 || n == 3 || n == 5) {
         isPrime = TRUE;
      } else if (n % 2 && n % 3 && n % 5) {
         isPrime = TRUE;
         divisor = 5;
         root = sqrt(n);
         while (isPrime && divisor <= root) {
            divisor += 2;
            if (isPrime = (n % divisor != 0)) {
               divisor += 4;
               isPrime = (n % divisor != 0);
            }
         }
      }
   }
   return(isPrime);
}

+++
Lloyd Lim     Internet: lim@iris.eecs.ucdavis.edu
              America Online: LimUnltd
              Compuserve: 72647,660
              US Mail: 215 Lysle Leach Hall, U.C. Davis, Davis, CA 95616