[seqfan] Re: Sieving method for composite numbers described / used in A146071
Max Alekseyev
maxale at gmail.com
Fri Oct 31 20:59:18 CET 2008
Unfortunately, Mathworld's article forgot to mention the most
important property of sieving which is efficiency. The whole idea
behind sieving is replacing computationally expensive operations (such
as integer factorization) with cheap ones (such as enumerating
multiple of an integer).
As Maximilian already pointed out, your procedure is very ineffective
as it requires factorization of integers. In fact, it no better then
simply checking if every number in the interval for primality.
Regards,
Max
On Fri, Oct 31, 2008 at 12:42 PM, Alexander Povolotsky
<apovolot at gmail.com> wrote:
> http://mathworld.wolfram.com/Sieve.html
>
> says:
> =====================================================================================
> Sieve
> A process of successively crossing out members of a list according to
> a set of rules such that only some remain.
> =====================================================================================
> So if I would apply the set of rules described by me in A146071 to the
> entire list of natural numbers (which includes both primes and
> composite numbers): 1,2,3,4,5,6,7,8, ...
> then primes will remain, but composites will be replaced by primes.
>
> So my method (when applied to the entire list of natural numbers and
> that what I meant) IS a sieve (per mathworld definition).
>
> Regards,
> Alexander R. Povolotsky
>
> On Fri, Oct 31, 2008 at 3:13 PM, Max Alekseyev <maxale at gmail.com> wrote:
>>
>> Alexander,
>>
>> You are misusing the term sieving as your sequence has nothing to do
>> with sieving.
>> See http://en.wikipedia.org/wiki/Sieve_theory for the correct meaning
>> of sieving in mathematics.
>>
>> Regards,
>> Max
>>
>> On Fri, Oct 31, 2008 at 10:00 AM, Alexander Povolotsky
>> <apovolot at gmail.com> wrote:
>> > Hi,
>> >
>> > Would the sieving method for composite numbers, with which I came up in
>> > A146071,
>> > produce ALL prime numbers (so far I don't see 13 there ... ;-) ) ?
>> > If NOT - then could one define / predict what prime numbers will be not
>> > generated by below described sieving method for composite numbers ?
>> >
>> > Was this sieving method described / used before ?
>> >
>> > Thanks,
>> > Best Regards,
>> > Alexander R. Povolotsky
>> >
>> > _______________________________________________
>> >
>> > Seqfan Mailing list - http://list.seqfan.eu/
>> >
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list