Ugh, that was terribly written, sorry. If you know it's prime and all you need to do is tell them that it's prime, that's O(1) and you don't need to read anything. If you know it's prime and you have to print the explicit factorization of the prime, then you have to read and print the prime, and it's Θ(log n). On Tue, Feb 20, 2018 at 10:16 AM, Mike Stay <metaweta@gmail.com> wrote:
If you know it's prime, you don't need to read the input. I suppose that if you have to echo back the prime you just read for its factorization, then it's Θ(log n).
On Tue, Feb 20, 2018 at 9:19 AM, Mike Speciner <ms@alum.mit.edu> wrote:
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
_______________________________________________ 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
-- Mike Stay - metaweta@gmail.com http://www.math.ucr.edu/~mike http://reperiendi.wordpress.com