Which algoithum are you referring to? David
----- Original Message ----- From: <[EMAIL PROTECTED]> To: <[email protected]> Sent: Tuesday, August 08, 2006 3:00 PM Subject: Prime Digest, Vol 28, Issue 6 > Send Prime mailing list submissions to > [email protected] > > To subscribe or unsubscribe via the World Wide Web, visit > http://hogranch.com/mailman/listinfo/prime > or, via email, send a message with subject or body 'help' to > [EMAIL PROTECTED] > > You can reach the person managing the list at > [EMAIL PROTECTED] > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Prime digest..." > > > Today's Topics: > > 1. prime factoization algorithm (roger lindley) > 2. prime factoization algorithm (roger lindley) > 3. Re: prime factoization algorithm (Brian Beesley) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Mon, 7 Aug 2006 19:39:22 -0500 > From: "roger lindley" <[EMAIL PROTECTED]> > Subject: [Prime] prime factoization algorithm > To: <[email protected]> > Message-ID: <[EMAIL PROTECTED]> > Content-Type: text/plain; charset="iso-8859-1" > > I have discovered an extension to the Sieve of Eratosthenes that not only > finds the primes, but also finds the prime factorization of the composites > in canonical form. The algorithm requires no explicit multiplication or > division, only loops and increments, the same as the "Sieve". > > Is such an algorithm already known? I have never been able to find a > reference to such an algorithm. I realize that the algorithm probably > does not have any practical application. But I think such an algorithm > would be of interest to the study of the "Fundamental Theorem of > Arithmetic" since it is so simple, just as the "Sieve" is. > > I just want to know if it is something new, which I can't imagine it is. > But I cannot find a reference to it. > > Any reply would be appreciated. > > ---------- > > I have been a member of GIMPS since 1999 and have Prime95 running on 3 or > 4 computers most of the time, but no "joy" yet. > > - rlindley > > ------------------------------ > > Message: 2 > Date: Mon, 7 Aug 2006 21:09:44 -0500 > From: "roger lindley" <[EMAIL PROTECTED]> > Subject: [Prime] prime factoization algorithm > To: <[email protected]> > Message-ID: <[EMAIL PROTECTED]> > Content-Type: text/plain; charset="iso-8859-1" > > Sorry, I misspelled factorization in my subject line. Instead of > factoization I meant factorization. I guess spell check does not check > the subject line, but that is no excuse. I should have checked it myself. > > ------------------------------ > > Message: 3 > Date: Tue, 8 Aug 2006 07:38:40 +0000 > From: Brian Beesley <[EMAIL PROTECTED]> > Subject: Re: [Prime] prime factoization algorithm > To: The Great Internet Mersenne Prime Search list <[email protected]> > Message-ID: <[EMAIL PROTECTED]> > Content-Type: text/plain; charset="iso-8859-1" > > On Tuesday 08 August 2006 00:39, roger lindley wrote: >> I have discovered an extension to the Sieve of Eratosthenes that not only >> finds the primes, but also finds the prime factorization of the >> composites >> in canonical form. The algorithm requires no explicit multiplication or >> division, only loops and increments, the same as the "Sieve". > > Umm - attach a list of integers, initially empty, to each sieve element. > When > an element is "hit" during sieving, instead of just tagging it, add to the > list the value of the increment you're using at the time. When you're > finished, prime elements will still have an empty list, composite elements > will have a list of primitive factors. Not a complete factorisation as > powers > will not be shown. >> >> Is such an algorithm already known? I have never been able to find a >> reference to such an algorithm. > > I just thought of the above rather than searching for it, that doesn't > prove > it's already known or otherwise, but probably does indicate that it's > rather > obvious! > >> I realize that the algorithm probably does >> not have any practical application. > > Yes. For numbers small enough to be classified as prime/composite by > simple > sieving the factorisation is either known or can be found very quickly. > And > this extension uses a lot more memory - the basic sieve requires only one > bit > per element, this method requires one integer per element (to count > factors) > to start & increasingly more as sieving progresses (a pointer into the > sieve > for each factor found). > >> But I think such an algorithm would be >> of interest to the study of the "Fundamental Theorem of Arithmetic" >> since >> it is so simple, just as the "Sieve" is. >> >> I just want to know if it is something new, which I can't imagine it is. >> But I cannot find a reference to it. > > Why not tell us what it is - with a claim to copyright if this concerns > you? > But please don't start me on software patents.... > > Regards > Brian Beesley > > > ------------------------------ > > _______________________________________________ > Prime mailing list > [email protected] > http://hogranch.com/mailman/listinfo/prime > > > End of Prime Digest, Vol 28, Issue 6 > ************************************ > > > _______________________________________________ Prime mailing list [email protected] http://hogranch.com/mailman/listinfo/prime
