Задача почему-то не открылась, поэтому решаю задачу по вашему условию.
Раз таблица N*M, то максимум элементов в столбце = 20 (т.к. 1<=M<=20).
Вообще можно динамически раскладывать число на множители (не обязательно простые), затем просто сравнивать их количество и остаточные коэффициенты.
В принципе, можно грамотно написать длинную арифметику по основанию 109, которая будет быстро работать.