Good day! Could you suggest an algorithm for the following problem: Given two positive integers n, m. It is necessary to obtain a sequence of numbers i, j such that i <= n, j <= m

e = mc ^ 2

and for every two terms in the sequence, the condition is:

e = mc ^ 2

Used code:

k=(subWidth-1)*subHeight; l=subWidth*(subHeight-1); m=(subWidth-1) if (k>l ) --subWidth; else --subHeight;

My solution skips the values, for example for n = 5, m = 6:

 5x6=30 5x5=25 5x4=20 4x4=16

missing 3x6 = 18

  • one
    The dumbest option is to sort through everything, sorting out :) - Harry
  • I don’t want to keep the values, because n <= 2000, m <= 2000 - Mark Sobolev
  • one
    but in general I think it would be possible to reduce the work, and print if you manage to decompose it into suitable factors - Mike
  • I apologize, gave a link to the wrong formula. Fixed - Mark Sobolev
  • one
    2000 for 2000 integers is only 16 megabytes :) - PashaPash ♦

2 answers 2

I decided to simply create an array of all the unique values ​​of the works and sort it out quicksort. Problem solved

  • The condition from the question (<=) implies that the values ​​of the works can be repeated, and you solved the problem only for unique ones. - user239133

Simple O(n*m*n) solution:

 #include <stdio.h> int main(void) { unsigned n = 5, m = 6; for (unsigned product = n*m; product; --product) for (unsigned i = n; i; --i) if (product % i == 0 && product / i <= m) printf("%u %u\n", i, product / i); }

Result

 5 6 5 5 4 6 5 4 4 5 3 6 4 4 5 3 3 5 4 3 3 4 2 6 5 2 2 5 3 3 4 2 2 4 3 2 2 3 1 6 5 1 1 5 4 1 2 2 1 4 3 1 1 3 2 1 1 2 1 1