simple proof that you can't get better than O(n^2) is that you need to produce an n x n matrix with O(n^2) distinct values, so you need at least O(n^2) just to print the result.
However, yes, there are big differences based on the encoding. Nobody would accept using unary input encoding to artificially inflate the size of the input. It's also why the time-compelixity of prime-testing is sometimes confusing.