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
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com