## Wednesday, August 24, 2005

### Is This Number Prime? : Two ( Response )

i thought i would include this;
principly so i don't loose it...!!!
--------
Please take a look at this... On my Blog...
http://transamoebae.blogspot.com/2005/08/is-this-number-prime.html

") ; //-->

D Herring
Aug 25, 6:59 pm
show options
Newsgroups: comp.sys.hp48
From: D Herring ...@at.uiuc.dot.edu> - Find messages by this author
Date: Fri, 26 Aug 2005 04:59:40 GMT
Local: Thurs, Aug 25 2005 6:59 pm
Subject: Re: Is This a New Idea... ( Prime Sieve )

TranslucentAmoebae wrote: > Please take a look at this... > On my Blog... > http://transamoebae.blogspot.com/2005/08/is-this-number-prime.html

Not new, although your approach is somewhat different. Unfortunately, converting numbers between bases is a fairly expensive operation in itself; there are more efficient methods of identifying primes.
Modern prime-detection routines don't directly search for divisors, they just test conditions that most composite numbers will fail. Pass 10 different tests that 99% of composite numbers will fail, and you are probably prime.
Here are some pages you might like to read about prime theory:
http://mathworld.wolfram.com/SieveofEratosthenes.html http://mathworld.wolfram.com/PrimalityTest.html http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html
If you want to generate your own exhaustive list of primes (say all primes less than 100000), the sieve of Eratosthenes gets rather inefficient. A slightly faster method is to generate an offset table...
If you take the first two primes (2,3), they will mask out numbers in a periodic pattern of length 6. So, starting with 5 (the largest prime < 3="6)," 2="7,+4=" 2="13,+4=" 5="15)," 10="20" 6="1/2"> less than half of the integers are prime 3 primes: 10/30=1/3 -> less than a third ...
Some prime lists:

http://www.rsok.com/~jrm/printprimes.html
http://primes.utm.edu/primes/home.php
http://www.mersenne.org/
Enjoy primes, but beware! They can become an obsession. (As can palindromes; especially trying to predict how many iterations of the "reverse and add" routine are required to convert any integer into a palindrome).
:) Daniel