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
