20 Feb
2018
20 Feb
'18
9:19 a.m.
And what about reading the input? On 20-Feb-18 10:10, Mike Stay wrote: > Yeah, it's O(log n), not Θ(log n). > > On Mon, Feb 19, 2018 at 5:50 PM, <rcs@xmission.com> wrote: >> One bit of output is enough for the prime case. >> >> -------- >> Quoting Cris Moore <moore@santafe.edu>: >>> heh. >>> >>>> On Feb 19, 2018, at 3:39 PM, Mike Speciner <ms@alum.mit.edu> wrote: >>>> >>>> Even if you know it's a prime, it's still log n. You have to output the >>>> factorization. >>>> >>>> --ms >>>> >>>> On 19-Feb-18 17:05, Cris Moore wrote: >>>>>> On Feb 19, 2018, at 2:50 PM, Hilarie Orman <ho@alum.mit.edu> wrote: >>>>>> >>>>>> Factoring a prime is O(1). >>>>> If you already know it?s a prime :-) >>>>> - Cris >>>>> _______________________________________________ >>>>> math-fun mailing list >>>>> math-fun@mailman.xmission.com >>>>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>>> >>>> >>>> _______________________________________________ >>>> math-fun mailing list >>>> math-fun@mailman.xmission.com >>>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>> >>> >>> _______________________________________________ >>> math-fun mailing list >>> math-fun@mailman.xmission.com >>> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >>> >> >> >> _______________________________________________ >> math-fun mailing list >> math-fun@mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > >