Given a matrix, cell is call good cell if row divides column

Question

Given a n*m matrix, a cell is called good cell if row number (i) divides column number (j)

Example : 2*3 matrix => cells are {1,1}, {1,2}, {1,3}, {2,1}, {2,2}, {2,3} from which good cells can be defined as {1,1}, {1,2}, {1,3}, {2,2}

So the output is 4

I have figure out the logic for this, row 1 has all cells as good cells, row 2 has m/2 good cells, row 3 has m/3 good cells. (I am using just the integer dividend)

 m/1 + m/2 + m/3 + ........ + m/n;

For which my code looks like =>

long count=1;
 long answer = 0;
 while(count<=n){
    answer=answer + m/count;
    count++;
 }

But this code is getting timed out when I am submitting my solution. Need help to find better approach for this. PS: Coding challenge is already over.

Answer 1

Try this one,

for(int i = 0 ; i < n; i++)
{
   for(int j = 0; j < m; j += i) // j += i will save unwanted loops
   {
       // rest of your logic  
   }
}

As the value of i gets higher and higher nested loop will become more efficient

edit

The below code will be more efficient & correct than above. Now nested loop starts with the value of i instead of 0

for(int i = 0 ; i < n; i++)
{
   for(int j = i; j < m; j += i) //j = i & j += i will save unwanted loops
   {
       // rest of your logic  
   }
}

Answer 2

as noted by n pronouns m this post incorrect since it only considers the case n==m

You may have a look at the Dirichlet divisor problem

One attempt is the formula of Benoit Cloitre:

(below octave implem)

function s = sumit(n)
    s = 0;
    for i = 1:n
        s += floor(n/i);
    end
end
n = 1e6
expect = sumit(n)

%A006218
u = floor(sqrt(n));
res = 2*sum(floor(n./(1:u))) - u^2

Where you avoid summing quite some terms.