You can just change
for (int d = 2; d <= n; d++) {
to
for (int d = 2; d * d <= n; d++) {
and add the remains in the end if the remains not equal to 1
which makes the worst case complexity down to O(N ** 1/2)
You can just change
for (int d = 2; d <= n; d++) {
to
for (int d = 2; d * d <= n; d++) {
and add the remains in the end if the remains not equal to 1
which makes the worst case complexity down to O(N ** 1/2)
@cygnus said in Simplified winner's solution:
@wang21 what is the O(logN) algorithm?
I also want to know
I think using itertools.combinations will sightly decrease the complexity but I cannot get the rest part of nums easily. Is there an easy way to do that?
U can easily prove this by using the Karnaugh map.