Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: An Interesting Way To Introduce Prime Numbers
Posted:
Dec 28, 2012 10:14 PM


On Fri, Dec 28, 2012 at 10:35 AM, Ken Abbott <abbottsystems@gmail.com> wrote: > http://www.mathmath.com/2012/12/makingprimenumbers.html
Yes, well described.
In practice it's not always easy to determine which prime factors make N, so one successively tries those on file.
Like when you asked about 15, 2 doesn't work so we know to try 3, but sometimes it's not obvious with which odd prime to start, so one plows through the ones on file in succession, up to sqrt(N), at which point one should have found one if there is one. If not, add to the stash and proceed.
Put another way, factoring is a nontrivial problem and once the integers get big enough, we run out of memory and/or time given present capacity.
Which is not to denigrate your algorithm. The algorithms giving us primes of many thousands of digits tend to shoot for "probable primes" which means very very unlikely to be composite. Composites sneak through the filters.
Like remember the Carmichael numbers: they pass all the Fermat tests suggesting they're prime, but they're not:
http://crypto.stanford.edu/pbc/notes/numbertheory/carmichael.xhtml http://crypto.stanford.edu/pbc/notes/numbertheory/millerrabin.xhtml
Your method has often been implemented and is well respected. It requires a growing stash of primes on file.
Kirby



