kr@asacsg.mh.nl (Koos Remigius) (05/01/91)
Hi, Thanks to all who replied to my question about a prime number generator. What follows is a summary (not all replies ): >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: Scott Lindhurst <lindhurs@math.wisc.edu> >> Message-Id: <9104050628.AA26525@schaefer.math.wisc.edu> >> To: kr@asacsg.mh.nl >> Subject: Re: Prime numbers, Help >> Newsgroups: comp.sys.mac.programmer >> In-Reply-To: <1991Apr4.164338.329@asacsg.mh.nl> >> Organization: Univ. of Wisconsin Dept. of Mathematics >> Status: RO >> >> In article <1991Apr4.164338.329@asacsg.mh.nl> you write: >> >Or any prime number generator routine is also welcome. >> >> I once wrote a program to compute the primes to 20,000,000 >> using the Sieve of Erastothenes. I'm not at my Mac >> now so I can't send it to you, but the algorithm is: >> Initialize an array [2..max] to false. >> For i:=2 to Max do >> if array[i] = false then {we know i is prime} >> Set all multiples of i to TRUE >> >> I'll be glad to tell you more about this, or send you my program. >> Just let me know. >> >> Scott >> lindhurs@math.wisc.edu >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: zben@ni.umd.edu (Ben Cranston) >> Message-Id: <9104051901.AA14348@ni.umd.edu> >> To: kr@asacsg.mh.nl >> Subject: prime numbers >> Status: RO >> >> yeesh! what you are asking for is difficult mathematically >> numbers of the form (p1*p2*p3 - 1) are prime when p1..p2.. etc are sequential >> primes but the problem is finding the next prime... >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: engber@anaxagoras.ils.nwu.edu (Mike Engber) >> Message-Id: <9104051520.AA05710@anaxagoras.ils.nwu.edu> >> To: kr@asacsg.mh.nl >> Subject: Re: Prime numbers, Help >> Newsgroups: comp.sys.mac.programmer >> In-Reply-To: <1991Apr4.164338.329@asacsg.mh.nl> >> Organization: The Institute for the Learning Sciences >> Cc: >> Status: RO >> >> I don`t have exactly what you asked for. But I did impliment >> a primality tester for testing very large (100-200 digits) >> numbers for primeness. The catch is it`s in CommonLisp. >> >> I used it to generate key for my implementation of RSA. >> >> Anyway I can send you the source if you want, but you >> aren`t going to easily port it to Pascal. >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: francis%zaphod@gargoyle.uchicago.edu >> Message-Id: <9104050847.AA25830@daisy.uchicago.edu> >> To: kr@asacsg.mh.nl (Koos Remigius) >> In-Reply-To: kr@asacsg.mh.nl's message of 4 Apr 91 16:43:38 GMT >> Subject: Prime numbers, Help >> Status: RO >> >> >> Let me know if you don't get anything in a day or two, and I'll see >> what I can dig up. >> >> As a mathematician, I can tell you that GetNextPrime would be very >> difficult to implement efficiently. The problem is that there is no >> good relation between the primes. You'd have to have a list of them, >> either generated on the fly or stored. >> >> Writing a generator is fairly easy (Sieve of Erasthones [sp?]). >> >> /============================================================================\ >> | Francis Stracke | My opinions are my own. I don't steal them.| >> | Department of Mathematics |=============================================| >> | University of Chicago | Earth: Love it or leave it. | >> | francis@zaphod.uchicago.edu | | >> \============================================================================/ >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> 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 >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: Erik.Sea@p1.f109.n221.z1.fidonet.org (Erik Sea) >> Subject: RE: Prime >> To: kr@asacsg.mh.nl >> X-Mailer: mailout v1.26 released >> Status: RO >> >> >> Koos, >> >> With respect to your article in comp.sys.mac.programmer: >> >> > Primenumber:=GetNextPrime(22654); >> > >> > The routine GetNextPrime should give me a prime number, as close as >> > possible, but larger then the passed number. >> > >> > Or any prime number generator routine is also welcome. >> >> I don't have an actual piece of code, but an algorythm doesn't sound horribly >> complex to me. >> >> 1) Given the number N, try T = N+1...whatever it takes >> >> 2) Try to factor T by attempting to divide it by every thing from 2 to sqrt(T) >> >> 3) If it survives 2), it is prime, if it fails at any point, you can go >> immediately to the next higher number up for T >> >> Now, that's the *obvious* approach. >> >> A number of refinements are possible. For example, in step 2, you only really >> need to try dividing by *prime* factors, 2,3,5,7,11,13,.... >> >> That is the most efficient method that I know of, and if you're only concerned >> with plain integers, you can easily build an array of prime numbers up to >> sqrt(32768) (2..181, I believe). >> >> If you want to be able to handle larger numbers, you'll need to use LongInts, >> obviously, but it isn't practical to build the massive divisor table that >> would be necessary then. So, use the same 2..181 table, and, from there, go >> up mathematically in your divisors, knowing that you can skip the even numbers >> and the numbers ending in 5 (as they are obviously not prime). That way, for >> you'll only need to check 2/5 of the remaining possible factors, which isn't >> quite as efficient as only checking prime factors, but it gets the job done. >> On second thought, you might want to expand the table a little bit, but as the >> sqrt of maxLongInt is 32768, you obviously don't want to go too high! >> >> --- >> >> I think that just about covers it; I don't think I've done anything like this >> since highschool, but it was a good refresher! I'm sure there is a more >> esthetically appealling "recursive" algorythm, but I doubt it's too efficient. >> Factoring things is probably the hardest thing one can do! >> >> Let me know if what I've said is not sufficient for your needs. >> >> Good Luck! >> >> +---------------------+---------------------------------------------------+ >> ! Erik Sea/TAGI ! CIS: 74170,111 GEnie: ERIK.SEA ! >> ! POB 24029 Westown ! Internet: Erik.Sea@p1.f109.n221.z1.fidonet.org ! >> ! London, ON N6H 1S0 ! Fidonet: 1:221/109.1 AppleLink: CDA0745 ! >> +---------------------+---------------------------------------------------+ >> >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: Gary Schoumaker <gschouma%feds53.prime.com@RELAY.CS.NET> >> Message-Id: <9104091505.AA14659@feds53.Prime.COM> >> To: kr%asacsg.mh.nl@RELAY.CS.NET >> Subject: Re: Prime numbers, Help >> Status: R >> >> kr@asacsg.mh.nl (Koos Remigius): >> > Hello, >> > >> > 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. >> > >> > Or any prime number generator routine is also welcome. >> >> >> Could you let me know what you find - I could use a >> prime number generator routine. >> >> Thanks, >> >> Gary Schoumaker >> Prime Computer , CV Division >> Bedford, MA 01730 >> >> >> I'll send this tou you. >> Koos. >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> From: Scott Lindhurst <lindhurs@math.WISC.EDU> >> Subject: Re: Prime number source code >> To: kr@mh.NL >> Message-Id: <9104112041.AA02283@slichter> >> X-Envelope-To: kr@mh.NL >> Status: R >> >> Koos, here is the program: >> >> >> program sieve (input, output); >> const >> Max = 10000; >> var >> sieve: packed array[1..Max] of boolean; >> i, j: longint; >> begin >> for i := 1 to Max do >> sieve[i] := false; >> sieve[1] := true; >> j := 1; >> repeat >> if not sieve[j] then >> begin >> { writeln(j : 1);} >> i := j + j; >> while i <= Max do >> begin >> sieve[i] := true; >> i := i + j; >> end; >> end; >> j := j + 1; >> until j > Max; >> end. >> >> At the end, sieve[i] will be false if and only if i is prime. >> The way it works is that you start knowing 2 is prime. So >> mark all multiples of 2 as true, meaning they are not prime. >> Then look for the next entry in sieve marked false; that is >> prime (it's 3). Then mark all multiples of 3 as being non-prime, >> and look for the next number that hasn't been excluded because it >> is a multiple of a previous prime. >> >> The method was known to the ancient Greeks, discovered by a man >> named Eratosthenes, in the 2nd or 3rd century B.C. I would be >> happy to try to explain the method better if you don't understand >> what I wrote above. >> >> Good Luck with your program! >> Scott >> >> Thanks Scott, >> I am using your routine now. >> Koos >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - >> Sender: usenet@ux1.cso.uiuc.edu (News) >> Organization: University of Illinois at Urbana >> Lines: 23 >> >> lippin@spam.berkeley.edu (The Apathist) writes: >> >> >Recently kr@asacsg.mh.nl (Koos Remigius) wrote: >> >> >>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. >> >> >This is one of those situations where you can think up a zillion >> >clever ways to solve the problem, but none of them can touch the brute >> >force approach: include a table of primes in your program. A table of >> >primes to 65536 is well under 10K, and can handily be included in a >> >resource. A binary search will quickly find you the next prime if >> >your input is two-byte integer. >> >> If you only need to determine the primality up to 65,536, just include >> a "bitmap" of 0 and 1 to show if each number is prime. >> At 1 bit per number, only 8192 bytes are >> required. Store only the odd numbers (remember to make 2 a special case) >> and the storage drops to 4096 bytes. >> -- >> Rolf Wilson Illinois State Geological Survey rolf@sparc1.isgs.uiuc.edu >> >> - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - That's all fox, thanks again for your help. Happy programming, Koos. -- Koos Remigius kr@mh.nl via internet backbones Asac Nederland B.V uucp: ..!{uunet,hp4nl}!mh.nl!kr Coenecoop 7, 2741 PG Waddinxveen, The Netherlands ---------------- "Still crazy after all these years" ----------------