Представить правильную дробь в виде суммы простейших

Простейшие - это биология.. .
А числа, наверное, вы, имели ввиду - взаимно простые. Это когда целые числа не имеют общих делителей, кроме ±1. А может быть простые числа, которые делятся только на единицу и сами на себя. Я не уверен, но рискну предположить.. .
3747 / 4301 = 3 / 11 + 5 / 17 + 7 / 23
Заодно и код модно проверить.. .
;-)

Решение в лоб на scala. Правда, из-за крайне ноптимального рекурсивного вызовова оно падает при хоть скольнибудь серьезных значениях. Но для простых случаев работает =)

case class Rat(n:Int, d:Int) {
def gcd(x:Int, y:Int): Int = {
if (x == 0) y
else if (x < 0) gcd(-x, y)
else if (y < 0) -gcd(x, -y)
else gcd(y % x, x)
}

val nom = n / gcd(n, d)
val denom = d / gcd(n, d)

def -(other:Rat) = {
val nom = this.nom * other.denom - other.nom * this.denom
val denom = this.denom * other.denom
Rat(nom, denom)
}

def >(other:Rat) = {
(this - other).nom >= 0
}

def <(other:Rat) = {
! (this > other)
}

override def toString() =
"Rational: [" + nom + " / " + denom + "]"
}

def simplify(x:Rat):List[Rat] = {
def innerSimplify(x:Rat, currentDenom:Int):List[Rat] = {
x match {
case Rat(0,m) => Nil
case Rat(1,n) => Rat(1,n) :: Nil
case Rat(m,n) if x < Rat(1, currentDenom) => innerSimplify(x, currentDenom + 1)
case Rat(m,n) => Rat(1, currentDenom) :: innerSimplify(Rat(m,n) - Rat(1, currentDenom), currentDenom + 1)
}
}
return innerSimplify(x, 2)
}

simplify(Rat(3,5)) // case class Rat(n:Int, d:Int) {
def gcd(x:Int, y:Int): Int =
{
if (x == 0) y
else if (x < 0) gcd(-x, y)
else if (y < 0) -gcd(x, -y)
else gcd(y % x, x)
}

val nom = n / gcd(n, d)
val denom = d / gcd(n, d)

def -(other:Rat) = {
val nom = this.nom * other.denom - other.nom * this.denom
val denom = this.denom * other.denom
Rat(nom, denom)
}

def >(other:Rat) = {
(this - other).nom >= 0
}

def <(other:Rat) = {
! (this > other)
}

override def toString() =
"Rational: [" + nom + " / " + denom + "]"
}

def simplify(x:Rat):List[Rat] = {
def innerSimplify(x:Rat, currentDenom:Int):List[Rat] = {
x match {
case Rat(0,m) => Nil
case Rat(1,n) => Rat(1,n) :: Nil
case Rat(m,n) if x < Rat(1, currentDenom) => innerSimplify(x, currentDenom + 1)
case Rat(m,n) => Rat(1, currentDenom) :: innerSimplify(Rat(m,n) - Rat(1, currentDenom), currentDenom + 1)
}
}
return innerSimplify(x, 2)
}

simplify(Rat(3,5)) // => List(Rational: [1 / 2], Rational: [1 / 10])
simplify(Rat(2,9)) // => List(Rational: [1 / 5], Rational: [1 / 45])
simplify(Rat(9, 984)) // => List(Rational: [1 / 110], Rational: [1 / 18040]