kr@asacsg.mh.nl (Koos Remigius) (04/05/91)
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.
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.
Or any prime number generator routine is also welcome.
Cheers,
Koos Remigius
--
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" ----------------lim@iris.ucdavis.edu (Lloyd Lim) (04/09/91)
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
lippin@spam.berkeley.edu (The Apathist) (04/11/91)
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're looking in the four-byte range, a full table of primes would be cumbersome, but the two-byte table gives you one of the world's fastest primality tests: try dividing your target by each member of the table in turn. Using this test, it's a fairly quick task to search odd numbers for the next prime. If you really want arbitrary (or even much longer) integers as input, then it's time to investigate more sophisticated methods. --Tom Lippincott lippin@math.berkeley.edu "Oh, I could tell you why the ocean's near the shore..." --The Scarecrow
rolf@sparc1 (Rolf Wilson) (04/11/91)
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
francis@zaphod.uchicago.edu (04/14/91)
In article <1991Apr11.145247.16673@ux1.cso.uiuc.edu> rolf@sparc1 (Rolf Wilson) writes: 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. I knew a guy once (you out there, Steve?) who did this with his Apple II, using an entire floppy (as in, *all* of it--every single bit of the 140K). Said his drive was running nonstop for a day and a night. Just a tidbit from the randomizer that serves as my memory... -- /============================================================================\ | Francis Stracke | My opinions are my own. I don't steal them.| | Department of Mathematics |=============================================| | University of Chicago | Until you stalk and overrun, | | francis@zaphod.uchicago.edu | you can't devour anyone. -- Hobbes | \============================================================================/
mrx@dhw68k.cts.com (Mark Murphy) (04/17/91)
In article <1991Apr11.145247.16673@ux1.cso.uiuc.edu> rolf@sparc1 (Rolf Wilson) writes: >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. >>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. >-- Then scan the table 4 bytes a time starting from the desired position. This should speed things up. -- +-----------------------------------+----------------------------------------+ | Real Life: Mark F. Murphy | What kinda beer do you like? | | The Net: mrx@dhw68k.cts.com | Heineken!? Intercourse that doo-doo!! | | The Desktop BBS: 714-491-1003 | Pabst Blue Ribbon!!! |
zben@ni.umd.edu (Ben Cranston) (04/17/91)
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 ... As stated by others, a fairly small table can hold a bitmap representation of prime numbers. For example, a table of 1K bytes can represent all prime numbers up to 16383. I seem to remember a theorum that if p1, p2, etc are sequential prime numbers starting at 2 then numbers of the form p1 * p2 * p3 ... - 1 are prime, the proof concerns the fact that if p1 or p2 or any of the pn are a factor of the big number then there is a second unique factorization, and since prime factorizations are unique it must be prime. Or something. Or maybe it was + rather than - -- any mathematicians out there? Anyway, if you use the table to get the p1, p2, etc you could generate some incredibly big primes. The main failure is that they will not be particularly dense, in fact, the ones at the end of the list will be about 16,000 times each other. I don't know *how close* the original requirement was.
neeri@iis.ethz.ch (Matthias Ulrich Neeracher) (04/18/91)
In article <1991Apr17.164107.28457@ni.umd.edu>, zben@ni.umd.edu (Ben Cranston) writes: >I seem to remember a theorum that if p1, p2, etc are sequential prime numbers >starting at 2 then numbers of the form > > p1 * p2 * p3 ... - 1 > >are prime, the proof concerns the fact that if p1 or p2 or any of the pn are >a factor of the big number then there is a second unique factorization, and >since prime factorizations are unique it must be prime. Or something. Or >maybe it was + rather than - -- any mathematicians out there? 2*3*5*7-1 = 209 = 11*19 2*3*5*7*11*13+1 = 30031 = 59*509 All the theoreme you mentioned (Euclid, I think) proves is that a number of the form p1 * p2 * p3 ... * pn - 1 isn't divisible by any of the pi for i=1...n. Matthias -- Matthias Neeracher neeri@iis.ethz.ch "These days, though, you have to be pretty technical before you can even aspire to crudeness." -- William Gibson, _Johnny Mnemonic_
fry@zariski.harvard.edu (David Fry) (04/18/91)
In article <1991Apr17.164107.28457@ni.umd.edu> zben@ni.umd.edu (Ben Cranston) writes: >I seem to remember a theorum that if p1, p2, etc are sequential prime numbers >starting at 2 then numbers of the form > > p1 * p2 * p3 ... - 1 > >are prime, the proof concerns the fact that if p1 or p2 or any of the pn are >a factor of the big number then there is a second unique factorization, and >since prime factorizations are unique it must be prime. Not quite. What you're thinking of is that if p1, p2, p3,...pn are sequentially numbered primes (with p1 = 2, p2 = 3, etc.), then p1 * p2 * p3 * ... * pn +/- 1 is either prime OR is divisible by a prime greater than pn. This is the basis of Euclid's proof of the infinitude of primes. David Fry fry@math.harvard.EDU Department of Mathematics fry@huma1.bitnet Harvard University ...!harvard!huma1!fry Cambridge, MA 02138
nlewispn@cc.curtin.edu.au (Peter N Lewis) (04/19/91)
In article <1991Apr17.164107.28457@ni.umd.edu>, zben@ni.umd.edu (Ben Cranston) writes: > > I seem to remember a theorum that if p1, p2, etc are sequential prime numbers > starting at 2 then numbers of the form > > p1 * p2 * p3 ... - 1 > > are prime, the proof concerns the fact that if p1 or p2 or any of the pn are > a factor of the big number then there is a second unique factorization, and > since prime factorizations are unique it must be prime. Or something. Or > maybe it was + rather than - -- any mathematicians out there? > Ummm, well except for the fact the 2*3*5*7-1=209=11*19.... Actually, 2*3*5*...*pn-1 does not have a factor of 2,3,5,...,pn in it. BUT it can have a factor of pn+1,pn+2,...,sqrt(2*3*5*...*pn-1). +'s wont work either since 2+3-1=4, 2+3+5-1=9, 2+3+5+7-1=16 (see a trend here?) 2+3+5+7+11-1=27, 2+3+5+7+11+13-1=40 (ooops, there goes that nice trend). > Anyway, if you use the table to get the p1, p2, etc you could generate some > incredibly big primes. The main failure is that they will not be particularly > dense, in fact, the ones at the end of the list will be about 16,000 times > each other. I don't know *how close* the original requirement was. It isnt that easy :-(. There are lots of fancy algorithms for finding really huge primes, but they mostly take huge amounts of processing time as well. I don't know much about them so if you are interested go to a maths library and look them up. Have fun, Peter. PS: Now what on earth does all this have to do with mac programming? :-) -- Disclaimer:Curtin & I have an agreement:Neither of us listen to either of us. *-------+---------+---------+---------+---------+---------+---------+-------* Internet: Lewis_P@cc.curtin.edu.au I Peter Lewis Bitnet: Lewis_P%cc.curtin.edu.au@cunyvm.bitnet I NCRPDA, Curtin University UUCP: uunet!munnari.oz!cc.curtin.edu.au!Lewis_P I GPO Box U1987 PSImail: psi%050529452300070::Lewis_P I Perth, WA, 6001, AUSTRALIA Has anyone ever found someone who used a Mac and then Changed To a PC?