How to decompose an integer in two for grid creation

Answer 1

A = B = ceil (sqrt N)

Answer 2

Easy.

In pseudocode

a = b = floor(sqrt(N))

if (a * b >= N) return (a, b)

a += 1
if (a * b >= N) return (a, b)

return (a, b+1)

and it will always terminate, the distance between a and b at most only 1.

It will be much harder if you relax second constraint, but that's another question.

Edit: as it seems that the first condition is more important, you have to attack the problem a bit differently. You have to specify some method to measure the badness of not being square enough = 2nd condition, because even prime numbers can be factorized as 1*number, and we fulfill the first condition. Assume we have a badness function (say a >= b && a <= 2 * b), then factorize N and try different combinations to find best one. If there aren't any good enough, try with N+1 and so on.

Edit2: after thinking a bit more I come with this solution, in Python:

from math import sqrt

def isok(a, b):
  """accept difference of five - 2nd rule"""
  return a <= b + 5

def improve(a, b, N):
  """improve result:
    if a == b:
       (a+1)*(b-1) = a^2 - 1 < a*a
    otherwise (a - 1 >= b as a is always larger)
      (a+1)*(b-1) = a*b - a + b - 1 =< a*b

    On each iteration new a*b will be less,
    continue until we can, or 2nd condition is still met
  """
  while (a+1) * (b-1) >= N and isok(a+1, b-1):
    a, b = a + 1, b - 1

  return (a, b)

def decomposite(N):
  a = int(sqrt(N))
  b = a

  # N is square, result is ok
  if a * b >= N:
    return (a, b)

  a += 1

  if a * b >= N:
    return improve(a, b, N)

  return improve(a, b+1, N)

def test(N):
  (a, b) = decomposite(N)

  print "%d decomposed as %d * %d = %d" % (N, a, b, a*b)

[test(x) for x in [99, 100, 101, 20, 21, 22, 23]]

which outputs

99 decomposed as 11 * 9 = 99
100 decomposed as 10 * 10 = 100
101 decomposed as 13 * 8 = 104
20 decomposed as 5 * 4 = 20
21 decomposed as 7 * 3 = 21
22 decomposed as 6 * 4 = 24
23 decomposed as 6 * 4 = 24

Answer 3

I think this may work (your conditions are somewhat ambiguous). this solution is somewhat similar to other one, in basically produces rectangular matrix which is almost square. you may need to prove that A+2 is not optimal condition

A0 = B0 = ceil (sqrt N)
A1 = A0+1
B1 = B0-1
if A0*B0-N > A1*B1-N: return (A1,B1)
return (A0,B0)

this is solution if first condition is dominant (and second condition is not used)

A0 = B0 = ceil (sqrt N)
if A0*B0==N: return (A0,B0)
return (N,1)

Other conditions variations will be in between