# Ordering of multiplication table

this is my first post and I hope its succinct and relevant enough to post here.

I'm working on finding the largest number in a multiplication table (n by n) that satisfies a certain property. In finding the largest number, I realize that you can just sort the elements in the table, or get a bit smarter and do something like a saddle back search, checking each element for your property in order.

However, I was wondering if there was a way to sort the elements in a multiplication table in constant time, as with a pen and a pencil it seems that there is some sort of pattern.

Thanks!

-
1) What are the things being multiplied in your multiplication table? 2) How can you expect to do anything in constant time when the output has (presumably) $n^2$ items? – Robert Israel Jun 7 '11 at 3:03
Sorry, I should have been clearer. I meant Integers from (1..n) and constant as in constant in the size of the output. – Ratzes Jun 7 '11 at 3:20
It depends on the condition. Can you be more specific? – Yuval Filmus Jun 7 '11 at 3:24
This is linear time, constant time is when it is independent of the input size (asymptotically, that is). Please be sure to correct your question, if this is indeed what you meant. – Asaf Karagila Jun 7 '11 at 5:32

By "constant", I guess you mean "linear".

Let $A$ be an array of integers indexed by the integers 1 to $n^2$, initialized to 0.

for i from 1 to n
for j from 1 to n
A[i*j]:= A[i*j] + 1

for i from 1 to n^2
for j from 1 to A[i]
output i

-
Haha. Of course this is linear in $n^2$, the number of entries in the table. Perhaps the OP meant linear in the number m of distinct numbers in the table, in which case this is about O(m log m) (right? haven't thought carefully), still about as good as one can do. (Well, one could sieve out the primes in $[n+1, n^2]$, which would be slightly better—O(m log log m) arithmetic operations—but hardly worth it for the range of n where O(n) is acceptable.) – ShreevatsaR Jun 7 '11 at 6:16