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