Is there an easy way to find ints i,j,k satisfying i*j=k^2?

[SlurrerOfSpeech]

Long-story short, as part of a larger problem I'm trying to solve, I need all i,j>=0 such that i*j=k² for all k in [1, ..., n]. What I'm doing currently is iterating through [1², 2², ..., n²] and for each value m I'm using

        public static IEnumerable<Tuple<int, int>> Multipliers(ulong m)
        {
            ulong i = 1;
            ulong lastVal = m / 2;
            for(; i <= lastVal; i++)
            {
                if(m % i == 0)
                {
                    lastVal = m / i;
                    if(lastVal <= limit)
                    {
                        yield return Tuple.Create((int)i, (int)lastVal);
                    }
                }
            }
        }

to find the i,j pairs. But I think there may be some trick for finding them faster. Here are some I've printed out but I can't see the pattern.

1->[(1,1)]
4->[(4,1),(2,2)]
9->[(9,1),(3,3)]
16->[(16,1),(8,2),(4,4)]
25->[(25,1),(5,5)]
36->[(36,1),(18,2),(12,3),(9,4),(6,6)]
49->[(49,1),(7,7)]
64->[(64,1),(32,2),(16,4),(8,8)]
81->[(81,1),(27,3),(9,9)]
100->[(100,1),(50,2),(25,4),(20,5),(10,10)]
121->[(121,1),(11,11)]
144->[(144,1),(72,2),(48,3),(36,4),(24,6),(18,8),(16,9),(12,12)]
169->[(169,1),(13,13)]
196->[(196,1),(98,2),(49,4),(28,7),(14,14)]
225->[(225,1),(75,3),(45,5),(25,9),(15,15)]
256->[(256,1),(128,2),(64,4),(32,8),(16,16)]
289->[(289,1),(17,17)]
324->[(324,1),(162,2),(108,3),(81,4),(54,6),(36,9),(27,12),(18,18)]
361->[(361,1),(19,19)]
400->[(400,1),(200,2),(100,4),(80,5),(50,8),(40,10),(25,16),(20,20)]
441->[(441,1),(147,3),(63,7),(49,9),(21,21)]
484->[(484,1),(242,2),(121,4),(44,11),(22,22)]
529->[(529,1),(23,23)]
576->[(576,1),(288,2),(192,3),(144,4),(96,6),(72,8),(64,9),(48,12),(36,16),(32,18),(24,24)]
625->[(625,1),(125,5),(25,25)]
676->[(676,1),(338,2),(169,4),(52,13),(26,26)]
729->[(729,1),(243,3),(81,9),(27,27)]
784->[(784,1),(392,2),(196,4),(112,7),(98,8),(56,14),(49,16),(28,28)]
841->[(841,1),(29,29)]
900->[(900,1),(450,2),(300,3),(225,4),(180,5),(150,6),(100,9),(90,10),(75,12),(60,15),(50,18),(45,20),(36,25),(30,30)]
961->[(961,1),(31,31)]
1024->[(1024,1),(512,2),(256,4),(128,8),(64,16),(32,32)]
1089->[(1089,1),(363,3),(121,9),(99,11),(33,33)]
1156->[(1156,1),(578,2),(289,4),(68,17),(34,34)]
1225->[(1225,1),(245,5),(175,7),(49,25),(35,35)]
1296->[(1296,1),(648,2),(432,3),(324,4),(216,6),(162,8),(144,9),(108,12),(81,16),(72,18),(54,24),(48,27),(36,36)]
1369->[(1369,1),(37,37)]
1444->[(1444,1),(722,2),(361,4),(76,19),(38,38)]
1521->[(1521,1),(507,3),(169,9),(117,13),(39,39)]
1600->[(1600,1),(800,2),(400,4),(320,5),(200,8),(160,10),(100,16),(80,20),(64,25),(50,32),(40,40)]
1681->[(1681,1),(41,41)]
1764->[(1764,1),(882,2),(588,3),(441,4),(294,6),(252,7),(196,9),(147,12),(126,14),(98,18),(84,21),(63,28),(49,36),(42,42)]
1849->[(1849,1),(43,43)]
1936->[(1936,1),(968,2),(484,4),(242,8),(176,11),(121,16),(88,22),(44,44)]
2025->[(2025,1),(675,3),(405,5),(225,9),(135,15),(81,25),(75,27),(45,45)]
2116->[(2116,1),(1058,2),(529,4),(92,23),(46,46)]
2209->[(2209,1),(47,47)]
2304->[(2304,1),(1152,2),(768,3),(576,4),(384,6),(288,8),(256,9),(192,12),(144,16),(128,18),(96,24),(72,32),(64,36),(48,48)]
2401->[(2401,1),(343,7),(49,49)]
2500->[(2500,1),(1250,2),(625,4),(500,5),(250,10),(125,20),(100,25),(50,50)]
2601->[(2601,1),(867,3),(289,9),(153,17),(51,51)]
2704->[(2704,1),(1352,2),(676,4),(338,8),(208,13),(169,16),(104,26),(52,52)]
2809->[(2809,1),(53,53)]
2916->[(2916,1),(1458,2),(972,3),(729,4),(486,6),(324,9),(243,12),(162,18),(108,27),(81,36),(54,54)]
3025->[(3025,1),(605,5),(275,11),(121,25),(55,55)]
3136->[(3136,1),(1568,2),(784,4),(448,7),(392,8),(224,14),(196,16),(112,28),(98,32),(64,49),(56,56)]
3249->[(3249,1),(1083,3),(361,9),(171,19),(57,57)]
3364->[(3364,1),(1682,2),(841,4),(116,29),(58,58)]
3481->[(3481,1),(59,59)]
3600->[(3600,1),(1800,2),(1200,3),(900,4),(720,5),(600,6),(450,8),(400,9),(360,10),(300,12),(240,15),(225,16),(200,18),(180,20),(150,24),(144,25),(120,30),(100,36),(90,40),(80,45),(75,48),(72,50),(60,60)]
3721->[(3721,1),(61,61)]
3844->[(3844,1),(1922,2),(961,4),(124,31),(62,62)]
3969->[(3969,1),(1323,3),(567,7),(441,9),(189,21),(147,27),(81,49),(63,63)]
4096->[(4096,1),(2048,2),(1024,4),(512,8),(256,16),(128,32),(64,64)]
4225->[(4225,1),(845,5),(325,13),(169,25),(65,65)]
4356->[(4356,1),(2178,2),(1452,3),(1089,4),(726,6),(484,9),(396,11),(363,12),(242,18),(198,22),(132,33),(121,36),(99,44),(66,66)]
4489->[(4489,1),(67,67)]
4624->[(4624,1),(2312,2),(1156,4),(578,8),(289,16),(272,17),(136,34),(68,68)]
4761->[(4761,1),(1587,3),(529,9),(207,23),(69,69)]
4900->[(4900,1),(2450,2),(1225,4),(980,5),(700,7),(490,10),(350,14),(245,20),(196,25),(175,28),(140,35),(100,49),(98,50),(70,70)]
5041->[(5041,1),(71,71)]
5184->[(5184,1),(2592,2),(1728,3),(1296,4),(864,6),(648,8),(576,9),(432,12),(324,16),(288,18),(216,24),(192,27),(162,32),(144,36),(108,48),(96,54),(81,64),(72,72)]
5329->[(5329,1),(73,73)]
5476->[(5476,1),(2738,2),(1369,4),(148,37),(74,74)]
5625->[(5625,1),(1875,3),(1125,5),(625,9),(375,15),(225,25),(125,45),(75,75)]
5776->[(5776,1),(2888,2),(1444,4),(722,8),(361,16),(304,19),(152,38),(76,76)]
5929->[(5929,1),(847,7),(539,11),(121,49),(77,77)]
6084->[(6084,1),(3042,2),(2028,3),(1521,4),(1014,6),(676,9),(507,12),(468,13),(338,18),(234,26),(169,36),(156,39),(117,52),(78,78)]
6241->[(6241,1),(79,79)]
6400->[(6400,1),(3200,2),(1600,4),(1280,5),(800,8),(640,10),(400,16),(320,20),(256,25),(200,32),(160,40),(128,50),(100,64),(80,80)]
6561->[(6561,1),(2187,3),(729,9),(243,27),(81,81)]
6724->[(6724,1),(3362,2),(1681,4),(164,41),(82,82)]
6889->[(6889,1),(83,83)]
7056->[(7056,1),(3528,2),(2352,3),(1764,4),(1176,6),(1008,7),(882,8),(784,9),(588,12),(504,14),(441,16),(392,18),(336,21),(294,24),(252,28),(196,36),(168,42),(147,48),(144,49),(126,56),(112,63),(98,72),(84,84)]
7225->[(7225,1),(1445,5),(425,17),(289,25),(85,85)]
7396->[(7396,1),(3698,2),(1849,4),(172,43),(86,86)]
7569->[(7569,1),(2523,3),(841,9),(261,29),(87,87)]
7744->[(7744,1),(3872,2),(1936,4),(968,8),(704,11),(484,16),(352,22),(242,32),(176,44),(121,64),(88,88)]
7921->[(7921,1),(89,89)]
8100->[(8100,1),(4050,2),(2700,3),(2025,4),(1620,5),(1350,6),(900,9),(810,10),(675,12),(540,15),(450,18),(405,20),(324,25),(300,27),(270,30),(225,36),(180,45),(162,50),(150,54),(135,60),(108,75),(100,81),(90,90)]
8281->[(8281,1),(1183,7),(637,13),(169,49),(91,91)]
8464->[(8464,1),(4232,2),(2116,4),(1058,8),(529,16),(368,23),(184,46),(92,92)]
8649->[(8649,1),(2883,3),(961,9),(279,31),(93,93)]
8836->[(8836,1),(4418,2),(2209,4),(188,47),(94,94)]
9025->[(9025,1),(1805,5),(475,19),(361,25),(95,95)]
9216->[(9216,1),(4608,2),(3072,3),(2304,4),(1536,6),(1152,8),(1024,9),(768,12),(576,16),(512,18),(384,24),(288,32),(256,36),(192,48),(144,64),(128,72),(96,96)]
9409->[(9409,1),(97,97)]
9604->[(9604,1),(4802,2),(2401,4),(1372,7),(686,14),(343,28),(196,49),(98,98)]
9801->[(9801,1),(3267,3),(1089,9),(891,11),(363,27),(297,33),(121,81),(99,99)]

 

[FactChecker]

I don't know if you would consider this easier. Certainly the logic is more complicated than brute force.
Get the list of primes less or equal to n. Combine them and ignore the combinations that multiply greater than n. Separate the set with two of each factor (counting multiplicity) into i and j.

 

[Mark44]

1->[(1,1)]
4->[(4,1),(2,2)]
9->[(9,1),(3,3)]
.
.
.

There is some symmetry here that you are ignoring. The pairs (tuples) in brackets are (i, j) pairs such that their product is the square at the start of the row.
So I would think that for 4, you would have the two you list, as well as (1, 4), and similar for 9.

For 36, you show 36->[(36,1),(18,2),(12,3),(9,4),(6,6)]
For completeness, there are also, (4, 9), (3, 12), (2, 18), and (1, 36)

 

[willem2]

What you need is the prime factorization of k^2. (which is really easy to find from the factorization of k)
If you know k^2 = 2^4 * 3^2 for example, all the divisors in k^2, can be produced by multiplying all combinations of powers of 2 that are <= 2^4 and powers of 3 that are <= 3^2.

To find the prime factorization of k, there are a lot of advanced methods, but trial division will be ok if k<1000000. (max 168 primes to test)

 

[Baluncore]

What you need is the prime factorization of k^2. (which is really easy to find from the factorization of k)

Correct.

Place all the prime factors of k in a pool, then duplicate the pool contents since you need all the prime factors of k².
Draw unique selections of factors from the pool. Multiply each selection to get a different i.
Divide k² by i, to get j, which is also the product of the un-selected prime factors in the pool.

 

[.Scott]

Here are the basic steps using k=63 as an example:
prime list (created at initialization time):
·· 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, ...
k factorization:
·· 2*2<63 so 63/2 - doesn't work
·· 3*3<63 so 63/3 = 21
·· 3*3<21 so 21/3 = 7
·· 3*3>7 so 7 is prime and we are done.
·· 0, 2, 0, 1, 0, 0, 0, ...
k*k factorization (double each number):
·· 0, 4, 0, 2, 0, 0, 0, ...
now process this sequence as if you were counting using digits that were different bases depending on their position - with the "ones" position on the left:
·· 0000 = 3^0*7^0 = 1
·· 0100 = 3^1*7^0 = 3
·· 0200 = 9
·· 0300 = 27
·· 0400 = 81 (but this is greater than k, so skip it. It will be handled by 0020 = 49)
·· 0001 = 7
·· 0101 = 21
·· 0201 = 63
·· 0301 = 189 (>k, so skip to next digit increment)
·· 0002 = 49
·· 0102 = 147 (>k, so skip to next digit increment, which ends the count)