Editorial for Lyndon's Golf Contest 1 P7 - Fun Factoring


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Dingledooper

83 bytes

Since n can be as large as 10^9, an \mathcal{O}(n) solution is insufficient. We can optimize it to \mathcal{O}(\sqrt{n}) by observing that for every factor x of n such that x \le \sqrt{n}, there exists a corresponding factor \frac{n}{x}. 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 83-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 74-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 69 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 5-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 1 to n 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 n = 48. Obviously, we know that 48 divides n once, and 24 divides n twice. But what about all the numbers in between? It's obvious that none of the numbers in the range [25, 47] need to be checked, since n divided by any of these numbers would result in a value greater than 1 but less than 2, which cannot be a whole number. The same argument can be applied starting from 24. We know that 24 divides n twice, and 16 divides n thrice, but since every number in the range [17, 23] divides n by a fractional amount between 2 and 3, those values can be pruned. These observations prompt the following strategy:

Initialize a variable x = n, representing the current divisor to check for. We would like to skip all "unnecessary" values, which can formally be defined as all values y < x, such that \lfloor \frac{n}{x} \rfloor = \lfloor \frac{n}{y} \rfloor. Therefore, the next "useful" value is the largest y such that \lfloor \frac{n}{y} \rfloor \ge \lfloor \frac{n}{x} \rfloor + 1, which we can calculate to be y = \lfloor \frac{n}{\lfloor \frac{n}{x} \rfloor + 1} \rfloor. Implementing this algorithm leads us to the 54-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 \mathcal{O}(\sqrt{n}). Notice that the number of iterations is equivalent to asking for the number of distinct values of \lfloor \frac{n}{i} \rfloor, for 1 \le i \le n.

If i \le \sqrt{n}, then there can obviously be at most \sqrt{n} distinct values of \lfloor \frac{n}{i} \rfloor. If i > \sqrt{n}, then it implies that \lfloor \frac{n}{i} \rfloor < \sqrt{n}, which also can take on at most \sqrt{n} values. Therefore, the total complexity is \mathcal{O}(\sqrt{n} + \sqrt{n}) = \mathcal{O}(\sqrt{n}). For reference, the exact number of iterations for any given n is \lceil 2 \times \sqrt{n+1} \rceil - 2.


Comments

There are no comments at the moment.