Editorial for Lyndon's Golf Contest 1 P7 - Fun Factoring
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
83 bytes
Since can be as large as
, an
solution is insufficient. We can optimize it to
by observing that for every factor
of
such that
, there exists a corresponding factor
. An example implementation is given below:
n=int(input())
i=1
while i*i<=n:
if n%i<1:
print(i)
if i*i-n:print(n//i)
i+=1
64 bytes
In our -byte solution, an
if
statement is used to ensure that no duplicates are printed. Note also that print
is repeated twice. We can simplify the logic by instead storing a set of {i,n//i}
, and outputting the set with each number on its own line, which can be done with the sep
argument. This yields a -byte solution:
n=int(input())
i=1
while i*i<=n:
if n%i<1:print(*{i,n//i},sep='\n')
i+=1
We can further shorten this to bytes by making use of Python's short-circuiting operators. With
or
, we can cause print
to execute only when n%i
is falsy, which then allows us to move everything onto one line:
n=int(input())
i=1
while i*i<=n:n%i or print(*{i,n//i},sep='\n');i+=1
There is still more to optimize here. In particular, another -byte save is possible by outputting via
map
:
n=int(input())
i=1
while i*i<=n:n%i<1in map(print,{i,n//i});i+=1
The mechanics are left as an exercise to the reader (Hint: look up "chained comparison").
54 bytes
Recall back to the naive solution of iterating from to
to check if it is a divisor. A natural question is, can we optimize this method by pruning specific values that don't need to be checked? Yes in fact, we can!
For the sake of example, take . Obviously, we know that
divides
once, and
divides
twice. But what about all the numbers in between? It's obvious that none of the numbers in the range
need to be checked, since
divided by any of these numbers would result in a value greater than
but less than
, which cannot be a whole number. The same argument can be applied starting from
. We know that
divides
twice, and
divides
thrice, but since every number in the range
divides
by a fractional amount between
and
, those values can be pruned. These observations prompt the following strategy:
Initialize a variable , representing the current divisor to check for. We would like to skip all "unnecessary" values, which can formally be defined as all values
, such that
. Therefore, the next "useful" value is the largest
such that
, which we can calculate to be
. Implementing this algorithm leads us to the
-byte solution:
n=i=int(input())
while i:n%i or print(i);i=n//(n//i+1)
Now, let's try to prove that it has a time complexity of . Notice that the number of iterations is equivalent to asking for the number of distinct values of
, for
.
If , then there can obviously be at most
distinct values of
. If
, then it implies that
, which also can take on at most
values. Therefore, the total complexity is
. For reference, the exact number of iterations for any given
is
.
Comments